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

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

отказ

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

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

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

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

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

{ A(0) }

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

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

Cost_of_Edge + Cost_of_previous_Node

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

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

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

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

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

{ E(3), C(4) }

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

{ C(4), F(10) }

Далее мы рассмотрим 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 * будет (благодаря эвристике) искать в направлении цели.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. A * в Википедии
2. A * Java демонстрация

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

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

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

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

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