Поиск пути

Эквивалентные пути между A и B в двухмерном пространстве

Пример A*-поискового алгоритма:
зелёный: начальная точка
красный: путь
синий: пункт назначения
серый: препятствие

Поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который означает определение компьютерной программой наилучшего, оптимального маршрута между двумя точками.

В играх

Поиск пути в контексте компьютерных игр касается пути, на котором движущийся объект ищет путь вокруг препятствий. Наиболее часто задача поиска пути возникает в стратегиях реального времени, в которых игрок даёт задание игровым юнитам (единицам) двигаться через игровой уровень, который содержит препятствия. Кроме стратегий, задача поиска пути, так или иначе, в той или иной мере встречается в большинстве современных игровых жанров. Так как игры становятся всё сложнее, то поиск пути также эволюционирует и развивается вместе с ними.

Стратегии реального времени обычно содержат большие территории с открытым ландшафтом, в которых поиск пути обычно является простой задачей. Однако в большинстве случаев по карте перемещается не один юнит, а несколько, что создаёт потребность в различных и намного более сложных алгоритмах поиска пути для избежания пробок в узких областях игрового ландшафта. В стратегиях игровой уровень делится на тайлы (англ. tiles), которые действуют как узлы (англ. nodes) в алгоритме поиска пути[1][2].

В жанре 3D-шутеров используются намного более ограниченные пространства, которые не так легко разделить на узлы. Здесь взамен узлов используются так называемые waypoints (дословно с англ. — «точки пути»). Waypoints — это нерегулярные и вручную установленные узлы, которые содержат информацию о том, к каким другим узлам возможно добраться от данного.

Алгоритмы

По своей сути алгоритм поиска пути ищет на графе, начиная с одной (стартовой) точки и исследуя смежные узлы до тех пор, пока не будет достигнут узел назначения (конечный узел). Кроме того, в алгоритмах поиска пути в большинстве случаев заложена также цель найти самый короткий путь. Некоторые методы поиска на графе, такие как поиск в ширину, могут найти путь, если дано достаточно времени. Другие методы, которые «исследуют» граф, могут достичь точки назначения намного быстрее. Здесь можно привести аналогию с человеком, идущим через комнату. Человек может перед началом пути заранее исследовать все характеристики и препятствия в пространстве, вычислить оптимальный маршрут и только тогда начать непосредственное движение. В другом случае человек может сразу пойти в приблизительном или предполагаемом направлении цели и потом, уже во время пути, делать корректировки своего движения для избегания столкновений с препятствиями.

К самым известным и популярным алгоритмам поиска пути относятся такие алгоритмы[3][4]:

• Алгоритм поиска A*
• Алгоритм Дейкстры
• Волновой алгоритм
• Маршрутные алгоритмы[5][6]
• Навигационная сетка (Navmesh)[1]
• Иерархические алгоритмы[1]
• Обход препятствий[1]
• Разделяй и властвуй
• Алгоритм поворота Креша

См. также

• Игровой искусственный интеллект

Примечания

1. Роман Будкеев. Поиск пути в игре жанра RTS Страница 1 из 2  (неопр.). bimedev.ru (29 июня 2007). Архивировано из оригинала 22 августа 2012 года.
2. Роман Будкеев. Поиск пути в игре жанра RTS Страница 2 из 2  (неопр.). bimedev.ru (29 июня 2007). Архивировано из оригинала 22 августа 2012 года.
3. Bryan Stout (оригинальная статья) Maxim Kamensky (перевод). Алгоритмы поиска пути  (неопр.). pmg.org.ru (5 декабря 2000). Дата обращения: 22 июля 2009. Архивировано 29 апреля 2012 года.
4. Bryan Stout. Smart Moves: Intelligent Pathfinding (англ.) (1997). Дата обращения: 8 августа 2013. Архивировано 9 февраля 1999 года.
5. Нахождение пути на карте  (неопр.). Дата обращения: 8 августа 2013. Архивировано 1 августа 2013 года.
6. Поиск пути на карте  (неопр.). Дата обращения: 8 августа 2013. Архивировано 17 мая 2013 года.

Внешние ссылки

Англоязычные

• Amit. Amit’s A* Pages (англ.). theory.stanford.edu. Дата обращения: 1 мая 2010. Архивировано 4 апреля 2012 года.
• Argorha pathfinding (англ.). SourceForge.net. Дата обращения: 1 мая 2010. Архивировано 4 апреля 2012 года.
• PaulT. Fixing Pathfinding Once and For All (англ.). www.ai-blog.net (26 июля 2008). Дата обращения: 1 мая 2010. Архивировано из оригинала 4 апреля 2012 года.

Русскоязычные

• Bryan Stout (оригинальная статья) Maxim Kamensky (перевод). Алгоритмы поиска пути  (неопр.). pmg.org.ru (5 декабря 2000). Дата обращения: 22 июля 2009.
• Patrick Lester (автор), Morpher (перевод). Алгоритм A* для новичков  (неопр.). policyalmanac.org (26 июля 2004). Дата обращения: 1 мая 2010. Архивировано из оригинала 4 февраля 2012 года.
• George Judkin. Алгоритм поиска пути на карте (англ.). Королевство Delphi (28 марта 2005). Дата обращения: 22 июля 2009. Архивировано 4 апреля 2012 года.
• John Christian Lonningdal (оригинальная статья) Анисимов С.Ю. (перевод). Поиск пути: описание волнового алгоритма и других  (неопр.). www.iskint.ru (декабрь 1996). Дата обращения: 22 июля 2009. Архивировано из оригинала 30 декабря 2008 года.
• Поиск пути: исходные коды программ  (неопр.). www.iskint.ru. Дата обращения: 22 июля 2009. Архивировано из оригинала 24 июля 2010 года.
• Алексей Седов «onimod_land». Алгоритм построения пути в стратегической игре  (неопр.) 2. UralDev (7 сентября 2006). Дата обращения: 3 апреля 2010. Архивировано 4 апреля 2012 года.