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

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

66 голосов | спросил Daniel X Moore 14 J000000Wednesday10 2010, 23:19:35

11 ответов


60

Отказ

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


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

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

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

Иллюстрированная Dijkstra, часть 1

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

{A A (0)}

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

Иллюстрированная Dijkstra, часть 2

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

Cost_of_Edge + Cost_of_previous_Node

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

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

Иллюстрированная Dijkstra, часть 3

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

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

Иллюстрированная Dijkstra, часть 4

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

{E (3), C (4)}

Иллюстрированная Dijkstra, часть 5

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

{C (4), F (10)}

Иллюстрированная Dijkstra, часть 6

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


Алгоритм A *

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

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 12 FebruaryEurope/MoscowbSun, 12 Feb 2012 17:42:16 +0400000000pmSun, 12 Feb 2012 17:42:16 +040012 2012, 17:42:16
25

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

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

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

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

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

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

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

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

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

  • Принимая во внимание различия ландшафта, шероховатость, крутизну и т. д.

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

ответил Sean James 22 J000000Thursday10 2010, 00:21:54
17

Страницы Амита А * были хорошим для меня знакомством. Вы можете найти много хороших визуализаций для поиска алгоритма AStar на youtube.

ответил jdeseno 21 J000000Wednesday10 2010, 23:32:23
13

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

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

  1. A * в Википедии
  2. демонстрация A * Java
ответил David McGraw 15 J000000Thursday10 2010, 00:08:00
6

Вот небольшая статья с анимированным GIF, который демонстрирует алгоритм Дейкстры в движение.

ответил Ólafur Waage 15 J000000Thursday10 2010, 00:29:42
6

Вы можете найти статью ActiveTut на странице Поиск путей . полезно. Он проходит как алгоритм A *, так и Dijkstra's, и различия между ними. Он ориентирован на разработчиков Flash, но он должен дать некоторое представление о теории, даже если вы не используете Flash.

ответил VirtuosiMedia 22 J000000Thursday10 2010, 00:33:47
4

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

ответил Karantza 15 J000000Thursday10 2010, 00:44:03
3

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

ответил coderanger 22 J000000Thursday10 2010, 02:17:45
3

На абстрактном уровне A * работает следующим образом:

  • Вы рассматриваете мир как дискретное число подключенных узлов, например. сетку или график.
  • Чтобы найти путь через этот мир, вам нужно найти список смежных «узлов» в этом пространстве, начиная с начала до цели.
  • Наивный подход будет таким: рассчитать каждую возможную перестановку узлов, которые начинаются с начального узла и заканчиваться на конечном узле, и выбирать самый дешевый. Очевидно, что это займет навсегда все, кроме самых маленьких.
  • Поэтому альтернативные подходы пытаются использовать некоторые знания о мире, чтобы угадать, какие перестановки стоит рассмотреть в первую очередь, и знать, можно ли избить данное решение. Эта оценка называется эвристикой.
  • A * требует эвристики, допустимой допустимой . Это означает, что он никогда не переоценивает.
    • Хорошая эвристика для проблем с поиском путей - это евклидово расстояние, потому что мы знаем, что кратчайший маршрут между двумя точками - прямая. Это никогда не переоценивает расстояние в реальных симуляциях.
  • A * начинается с начального узла и пытается выполнить последовательные перестановки этого узла, а также каждого соседа и соседних соседей и т. д., используя эвристику, чтобы решить, какую перестановку попробовать далее.
  • На каждом шагу A * просматривает наиболее перспективный путь до сих пор и выбирает следующий соседний узел, который кажется «лучшим», исходя из расстояния, пройденного до сих пор, и оценки эвристики о том, как далеко можно было бы оставить перейти от этого узла.
  • Поскольку эвристика никогда не переоценивает, и расстояние, пройденное до сих пор, как известно, является точным, оно всегда будет выбирать наиболее оптимистичный следующий шаг.
    • Если следующий шаг достигнет цели, вы знаете, что он нашел кратчайший маршрут из последней позиции, потому что это была самая оптимистичная оценка оставшихся.
    • Если он не достиг цели, он остается как возможный момент для изучения позже. Теперь алгоритм выбирает следующую наиболее перспективную возможность, поэтому вышеприведенная логика применяется.
ответил Kylotan 13 FebruaryEurope/MoscowbMon, 13 Feb 2012 15:50:13 +0400000000pmMon, 13 Feb 2012 15:50:13 +040012 2012, 15:50:13
2

Меня смутило несколько объяснений A *, прежде чем я нашел этот отличный учебник: http://www.policyalmanac.org/games/aStarTutorial.htm

В основном я упоминал, что когда я написал реализацию A * в ActionScript: http://www.newarteest.com/flash/astar.html

ответил jhocking 15 PMpFri, 15 Apr 2011 22:37:27 +040037Friday 2011, 22:37:27
0

Вот мой любимый: http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

с деталями реализации для платформы cocos2d в языке Objective-C (для iPhone dev): http://www.raywenderlich.com/4970 /как к орудию-а-поиска пути-с cocos2d-учебник

ответил saiy2k 13 FebruaryEurope/MoscowbMon, 13 Feb 2012 08:57:46 +0400000000amMon, 13 Feb 2012 08:57:46 +040012 2012, 08:57:46

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132