Русская Википедия:Поиск пути

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Pathfinding 2D Illustration.svg
Эквивалентные пути между A и B в двухмерном пространстве
Файл:Pathfinding A Star.svg
Пример A*-поискового алгоритма:
зелёный: начальная точка
красный: путь
синий: пункт назначения
серый: препятствие

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

В играх

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

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

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

Алгоритмы

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

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

См. также

Примечания

Шаблон:Примечания

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

Англоязычные
Русскоязычные
Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 1,2 1,3 Ошибка цитирования Неверный тег <ref>; для сносок dtf1 не указан текст
  2. ↑ Ошибка цитирования Неверный тег <ref>; для сносок dtf2 не указан текст
  3. ↑ Ошибка цитирования Неверный тег <ref>; для сносок pmg_stout не указан текст
  4. ↑ Ошибка цитирования Неверный тег <ref>; для сносок stout не указан текст
  5. ↑ Ошибка цитирования Неверный тег <ref>; для сносок firststeps не указан текст
  6. ↑ Ошибка цитирования Неверный тег <ref>; для сносок delphisite не указан текст
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Поиск_пути&oldid=10612333