Как найти самый «прямой» маршрут с помощью A-star (A *)

Question

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

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

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

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

А потом с possibleNextNodes [Math.round (possibleNextNodes.length/2) -1]

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

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

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

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

Answer 1

Для эвристической функции вам необходимо добавить тай-брейк. Проблема здесь в том, что существует много путей с одинаковыми затратами.

Для простого таймера, который поддерживает прямой маршрут, вы можете использовать кросс-продукт. То есть если 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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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