Как работает A * pathfinding?

67

Я хотел бы понять на фундаментальном уровне, как работает поиск путей A *. Любой код или реализации псевдо-кода, а также визуализации были бы полезны.

Даниэль Х Мур
источник
Вот небольшая статья с анимированным GIF, в которой показан алгоритм Дейкстры в движении.
Олафур Вааге
Страницы Amit A * были хорошим введением для меня. Вы можете найти много хороших визуализаций в поисках алгоритма AStar на YouTube.
jdeseno
Меня смутил ряд объяснений A *, прежде чем я нашел этот замечательный учебник: policyalmanac.org/games/aStarTutorial.htm Я в основном упоминал об этом, когда писал реализацию A * в ActionScript: newarteest.com/flash /astar.html
джоккинг
4
-1 википедии есть статья о * с объяснением, исходный код, визуализации и ... . Некоторые ответы здесь имеют внешние ссылки с этой вики-страницы.
user712092
4
Кроме того, поскольку это довольно сложный предмет, представляющий большой интерес для разработчиков игр, я думаю, что нам нужна информация здесь. Я вспоминаю, как Джоэл однажды сказал, что он хочет, чтобы StackOverflow был главным хитом, когда люди гуглили вопросы программирования.
Джоккинг

Ответы:

63

отказ

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


Алгоритм Дейкстры

Чтобы понять A *, я предлагаю вам сначала взглянуть на алгоритм Дейкстры . Позвольте мне рассказать вам о шагах, которые алгоритм Дейкстры выполнит для поиска.

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

Иллюстрированный Дейкстры, часть 1

Это наша отправная точка. У нас есть список узлов для изучения, этот список в настоящее время:

{ A(0) }

Aимеет стоимость 0, все другие узлы установлены в бесконечность (в типичной реализации это будет что-то похожее int.MAX_VALUEили похожее).

Иллюстрированный Дейкстры, часть 2

Мы берем узел с наименьшей стоимостью из нашего списка узлов (поскольку наш список только содержит A, это наш кандидат) и посещаем всех его соседей. Мы устанавливаем стоимость каждого соседа:

Cost_of_Edge + Cost_of_previous_Node

и следите за предыдущим узлом (показан в виде маленькой розовой буквы под узлом). Aможет быть помечен как решенный (красный) сейчас, чтобы мы не посетили его снова. Наш список кандидатов теперь выглядит так:

{ B(2), D(3), C(4) }

Иллюстрированный Дейкстры, часть 3

Опять же, мы берем узел с наименьшей стоимостью из нашего list ( B) и оцениваем его соседей. Путь к Dявляется более дорогим, чем текущая стоимость D, поэтому этот путь может быть отброшен. Eбудет добавлен в наш список кандидатов, который теперь выглядит следующим образом:

{ D(3), C(4), E(4) }

Иллюстрированный Дейкстры, часть 4

Следующий узел для проверки сейчас D. Соединение с Cможет быть отброшено, так как путь не короче существующей стоимости. Однако мы нашли более короткий путь E, поэтому стоимость Eи предыдущий узел будут обновлены. Наш список теперь выглядит так:

{ E(3), C(4) }

Иллюстрированный Дейкстры, часть 5

Итак, как мы делали раньше, мы исследуем узел с самой низкой стоимостью из нашего списка, который сейчас есть E. Eимеет только одного неразрешенного соседа, который также является целевым узлом. Стоимость достижения целевого узла установлена, 10а его предыдущего узла - E. Наш список кандидатов теперь выглядит так:

{ C(4), F(10) }

Иллюстрированный Дейкстры, часть 6

Далее мы рассмотрим C. Мы можем обновить стоимость и предыдущий узел для F. Поскольку наш список теперь имеет Fузел с наименьшей стоимостью, мы закончили. Наш путь может быть построен путем возврата предыдущих кратчайших узлов.


Алгоритм *

Так что вы можете спросить, почему я объяснил вам Дейкстру вместо алгоритма A * ? Ну, единственная разница в том, как вы взвешиваете (или сортируете) своих кандидатов. С Dijkstra это:

Cost_of_Edge + Cost_of_previous_Node

С A * это:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Где Estimated_Cost_to_reach_Target_fromобычно называется эвристической функцией. Это функция, которая попытается оценить стоимость достижения целевого узла. Хорошая эвристическая функция позволит достичь меньшего количества узлов, чтобы найти цель. В то время как алгоритм Дейкстры расширится во все стороны, A * будет (благодаря эвристике) искать в направлении цели.

Страница Амита об эвристике имеет хороший обзор общей эвристики.

bummzack
источник
2
Стоит отметить, что эвристика не всегда подталкивает поиск, чтобы найти лучший маршрут. Например, если ваша эвристика - это расстояние до цели, но жизнеспособный маршрут проходит по краю карты - в этом случае поиск будет выполнять поиск по всей карте, прежде чем он получит правильный маршрут. Конечно, вы должны думать, есть что-то, чего я не понимаю? Это не работает! - нужно понимать, что цель эвристики - сократить поиск в большинстве случаев, а ваша задача - найти тот, который является «лучшим» из всех доступных решений для ваших конкретных потребностей.
SirYakalot
2
@AsherEinhorn Это все равно будет лучше (или в худшем случае равным), чем неинформированный поиск, как у Джикстры.
bummzack
да да, ты абсолютно прав. Возможно, мне было неясно, что тот случай, о котором я говорил в предыдущем комментарии, является теоретическим «наихудшим» сенарио для A * с этой эвристикой, НО это то, что Дейкстра будет делать КАЖДЫЙ раз. Большую часть времени A * будет лучше даже с очень простой эвристикой. Моя точка зрения заключалась в том, что эвристика может поначалу сбивать с толку, потому что «расстояние до цели» не всегда имеет смысл для каждого сценария, а главное - для большинства.
SirYakalot
Также смотрите это: qiao.github.io/PathFinding.js/visual
Дэвид Шуинар
Этот ответ может использовать упоминание того, что делает эвристику допустимой, в смысле гарантии того, что A * найдет кратчайший путь. (Вкратце: чтобы быть допустимым, эвристика никогда не должна переоценивать фактическое расстояние до цели. Недопустимые эвристики иногда могут быть полезны, но они могут заставить A * возвращать неоптимальные пути.)
Ильмари Каронен
26

* Поиск пути - это поиск первого типа, который использует дополнительную эвристику.

Первое, что вам нужно сделать, это разделить область поиска. Для этого объяснения карта представляет собой квадратную сетку плиток, потому что большинство 2D-игр используют сетку плиток и потому, что это легко визуализировать. Однако обратите внимание, что область поиска может быть разбита любым удобным для вас способом: возможно, шестнадцатеричная сетка или даже произвольные формы, такие как Risk. Различные позиции на карте называются «узлами», и этот алгоритм будет работать всякий раз, когда у вас есть куча узлов для прохождения и определены соединения между узлами.

В любом случае, начиная с данной стартовой плитки:

  • 8 плиток вокруг стартовой плитки «оцениваются» на основе a) стоимости перехода от текущей плитки к следующей плитке (обычно 1 для горизонтальных или вертикальных перемещений, sqrt (2) для диагонального перемещения).

  • Затем каждому тайлу присваивается дополнительный «эвристический» балл - приблизительная величина относительной ценности перемещения к каждому тайлу. Используются разные эвристики, простейшим из которых является прямолинейное расстояние между центрами данной плитки и конечной плитки.

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

  • Этот процесс повторяется до тех пор, пока не будет достигнут целевой узел или не останется больше открытых узлов (что означает, что агент заблокирован).

Для диаграмм, иллюстрирующих эти шаги, обратитесь к этому хорошему учебнику для начинающих .

Есть некоторые улучшения, которые могут быть сделаны, в основном, в улучшении эвристики:

  • С учетом различий местности, шероховатости, крутизны и т. Д.

  • Иногда также полезно выполнить «зачистку» по сетке, чтобы заблокировать области карты, которые не являются эффективными путями: например, форма U, обращенная к агенту. Без теста развертки агент сначала войдет в U, развернется, затем уйдет и обойдет край U. «Настоящий» интеллектуальный агент заметит U-образную ловушку и просто избежит ее. Подметание может помочь имитировать это.

Шон Джеймс
источник
1
Объяснение с графиком, узлами, ребрами было бы более понятным, чем просто с плитками. Это не помогает понять, что независимо от пространственной структуры вашей игры, вы можете применять один и тот же алгоритм, поскольку у вас есть взаимосвязанная информация о позициях в этом пространстве.
Klaim
Я бы сказал, что на самом деле это будет не так ясно, потому что это сложнее визуализировать. Но да, это объяснение должно упомянуть, что мозаичная сетка не требуется; на самом деле, я отредактирую этот момент.
jhocking
14

Это далеко не самое лучшее, но это была реализация A * в C ++ несколько лет назад.

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

  1. A * в Википедии
  2. A * Java демонстрация
Дэвид Макгроу
источник
4
Ваш пример Python находится на C ++.
Булочки из алюминия
@финиш - Рад видеть, что кто-то ловит это! Повседневная деятельность вращается вокруг Python в эти дни. Спасибо!
Дэвид Макгроу
3
Ваш пример C ++ также может быть C.
deceleratedcaviar
4
Пример также может быть в ассемблере для всей структуры, которую он имеет. Это даже не A *, как это принятый ответ?
4
Извините, это не соответствует требованиям, это была одна из моих первых попыток кодирования, когда я начинал. Не стесняйтесь вносить что-то в комментарии / редактируйте пост, чтобы поделиться своим собственным решением.
Дэвид Макгроу
6

Вы могли бы найти статью ActiveTut о поиске пути полезной. Это касается как алгоритма А *, так и алгоритма Дейкстры и различий между ними. Он ориентирован на разработчиков Flash, но должен дать хорошее представление о теории, даже если вы не используете Flash.

VirtuosiMedia
источник
4

При работе с A * и алгоритмом Дейкстры важно визуализировать то, что A * направлено; он пытается найти кратчайший путь к определенной точке, «угадывая», в каком направлении смотреть. Алгоритм Дейкстры находит кратчайший путь к / каждой точке.

Karantza
источник
1
Это не совсем точное описание разницы между A * и Dijkstra. Это правда, что Дейкстра решает единый источник по всем пунктам, но при использовании в играх он обычно отключается, как только вы находите путь к цели. Реальное различие между ними состоит в том, что A * информируется эвристикой и может найти эту цель с меньшим количеством ветвей.
В дополнение к объяснению Джо: A * найдет путь ко всем точкам, если вы позволите, но в играх мы обычно хотим остановиться рано. A * работает как алгоритм Дийсктры, за исключением того, что эвристика помогает переупорядочить узлы, чтобы сначала изучить наиболее перспективные пути. Таким образом, вы обычно можете остановиться даже раньше, чем с помощью алгоритма Дейкстры. Например, если вы хотите найти путь от центра карты к восточной стороне, алгоритм Дейкстры будет одинаково исследовать все направления и остановится, когда найдет восточную сторону. A * проведет больше времени на востоке, чем на западе, и быстрее доберется
amitp
3

Так что, как первое утверждение, A * является сердцем алгоритма исследования графа. Обычно в играх мы используем плитки или другую геометрию мира в качестве графика, но вы можете использовать A * для других целей. Два ur-алгоритма обхода графа - поиск в глубину и поиск в ширину. В DFS вы всегда полностью исследуете свою текущую ветку, прежде чем смотреть на братьев и сестер текущего узла, а в BFS вы всегда смотрите сначала на братьев и сестер, а затем на детей. A * пытается найти золотую середину между ними, где вы исследуете ветку (более похоже на DFS), когда вы приближаетесь к желаемой цели, но иногда останавливаетесь и пробуете родного брата, если у него могут быть лучшие результаты на его ветке. Фактическая математика заключается в том, что вы ведете список возможных узлов для изучения в следующем, где каждый имеет "доброту" оценка, указывающая, насколько близко (в некотором абстрактном смысле) это к цели, более низкие оценки лучше (0 означает, что вы нашли цель). Вы выбираете, какой из них использовать следующим, находя минимум оценки плюс количество узлов вдали от корня (обычно это текущая конфигурация или текущая позиция в поиске пути). Каждый раз, когда вы исследуете узел, вы добавляете все его дочерние элементы в этот список, а затем выбираете новый лучший.

coderanger
источник
3

На абстрактном уровне A * работает так:

  • Вы рассматриваете мир как дискретное число связанных узлов, например. сетка или график.
  • Чтобы найти путь через этот мир, вам нужно найти список соседних «узлов» в этом пространстве, ведущих от начала к цели.
  • Наивный подход был бы следующим: вычислите каждую возможную перестановку узлов, которые начинаются с начального узла и заканчиваются в конечном узле, и выбирайте самый дешевый. Это, очевидно, заняло бы навсегда все, кроме самых крошечных мест.
  • Поэтому альтернативные подходы пытаются использовать некоторые знания о мире, чтобы угадать, какие перестановки стоит рассмотреть в первую очередь, и узнать, можно ли обойти данное решение. Эта оценка называется эвристической.
  • A * требует эвристики, которая допустима . Это означает, что он никогда не переоценивает.
    • Хорошей эвристикой для задач поиска пути является евклидово расстояние, потому что мы знаем, что кратчайший маршрут между двумя точками - это прямая линия. Это никогда не переоценивает расстояние в реальных симуляциях.
  • * Начинается с начального узла и пробует последовательные перестановки этого узла плюс каждого соседа, соседей его соседа и т. Д., Используя эвристику, чтобы решить, какую перестановку следует попробовать дальше.
  • На каждом шаге A * смотрит на самый многообещающий путь на данный момент и выбирает следующий соседний узел, который кажется «наилучшим», основываясь на пройденном расстоянии и эвристической оценке того, как далеко от него будет идти. узел.
  • Поскольку эвристика никогда не переоценивает, а пройденное расстояние, как известно, является точным, он всегда выберет наиболее оптимистичный следующий шаг.
    • Если этот следующий шаг достигнет цели, вы знаете, что он нашел кратчайший маршрут из последней позиции, потому что это была самая оптимистичная догадка из оставшихся действительных.
    • Если он не достиг цели, его оставляют как возможную точку для дальнейшего изучения. Алгоритм теперь выбирает следующую наиболее многообещающую возможность, поэтому приведенная выше логика все еще применяется.
Kylotan
источник