Как найти самый «естественный» прямой маршрут, используя A-star (A *)

Question

Я реализовал алгоритм A * в AS3, и он отлично работает, за исключением одной вещи. Часто полученный путь не идет по самому «естественному» или плавному пути к цели. В моем окружении объект может перемещаться по диагонали так же недорого, как и горизонтально или вертикально. Вот очень простой пример; начальная точка отмечена буквой S, а конечная (или конечная) - буквой F.

 | | | | | | | | | |
 |S| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

Как вы можете видеть, в течение 1-го раунда поиска все узлы [0,2], [1,2], [2,2] будут добавлены в список возможных узлов, поскольку все они имеют оценку Н. Проблема, с которой я столкнулся, возникает в следующий момент, когда я пытаюсь решить, с какого узла продолжить работу. В приведенном выше примере я использую возможный узел [0], чтобы выбрать следующий узел. Если я изменю это на возможный узел [возможный узел [длина 1]], я получу следующий путь.

 | | | | | | | | | |
 |S| | | | | | | | |
 | |x| | | | | | | |
 | | |x| | | | | | |
 | | | |x| | | | | |
 | | |x| | | | | | |
 | |x| | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

И затем с возможнымиNextNodes [Math.round (возможныйNextNodes.length / 2) -1]

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

Все эти пути имеют одинаковую стоимость, поскольку все они содержат одинаковое количество шагов, но в этой ситуации наиболее разумный путь будет следующим:

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

Существует ли формально принятый способ придания пути большей осмысленности, нежели математически правильного?

Answer 1

Вам нужно добавить Tie-breaker в вашу эвристическую функцию. Проблема здесь в том, что есть много путей с одинаковыми затратами.

Для простого прерывателя связи, который предпочитает прямой маршрут, вы можете использовать перекрестный продукт. То есть если S - начало, а E - конец, а X - текущая позиция в алгоритме, вы можете вычислить перекрестные произведения SE и XE и добавить штраф к эвристике, чем дальше он отклоняется от 0 (= прямой маршрут ).

В коде:

 dx1 = current.x - goal.x
 dy1 = current.y - goal.y
 dx2 = start.x - goal.x
 dy2 = start.y - goal.y
 cross = abs(dx1*dy2 - dx2*dy1)
 heuristic += cross*0.001

См. Также http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12,, который является отличным учебником об A * в целом.

Answer 2

Если вы хотите, чтобы пути выглядели естественно, вы должны убедиться, что ваши затраты соответствуют длине в декартовой системе координат. Это означает, что стоимость перемещения по диагонали должна быть в 2 раза больше стоимости перемещения по вертикали или горизонтали.

Answer 3

Вы можете добавить «контроль усилий» к расчетам стоимости для каждого квадрата. Актер будет стараться не поворачивать и не менять направление слишком сильно, так как это добавит стоимость пути:

http://angryee.blogspot.com/2009/03/better-pathfinding.html

Answer 4

Если я правильно помню, уловка заключается в том, чтобы добавить дополнительный параметр к функции стоимости (для каждого шага между соседними узлами или квадратами в вашем случае), который штрафует повороты немного больше, чем обычно ( например, имея относительную стоимость больше чем sqrt(2) для ходов дигональной). Теперь, вероятно, есть тонкая грань между сглаживанием пути и фактическим уменьшением оптимальности маршрута (его удлинением), и вы не сможете этого избежать. Есть определенный компромисс, который вам нужно найти, специфичный для вашего собственного приложения, и это может быть реально достигнуто только путем тестирования.

На сайте разработчиков игр, я полагаю, была статья, в которой подробно рассказывалось, как это можно сделать, но сейчас я не могу ее найти. В любом случае, поэкспериментируйте с вашей функцией стоимости и посмотрите, какие результаты вы получите - я уверен, что так и будет.

Answer 5

Что является более «разумным»? Straighter? Вам нужно правильно определить его количество, если алгоритм собирается что-то с этим сделать.

Поскольку перемещение по диагонали столь же недорого, как и перемещение по горизонтали / вертикали, все пути эквивалентны по всем критериям, доступным для A *. Если вы хотите более «осмысленный» путь, вам нужно указать алгоритму, что некоторые пути более желательны, чем другие, эффективно взвешивая горизонталь / вертикаль как «лучше», чем диагональ. Насколько я понимаю, это изменило бы параметры вашей среды.