Поиск пути

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Эквивалентные пути между A и B в двухмерном пространстве
Пример A*-поискового алгоритма:
зелёный: начальная точка
красный: путь
синий: пункт назначения
серый: препятствие

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

В играх[править | править вики-текст]

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

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

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

Алгоритмы[править | править вики-текст]

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

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

Маршрутный алгоритм[править | править вики-текст]

Маршрутный алгоритм подразделяется на следующие алгоритмы[5][6]:

  • основанные на вычислении расстояния между точками;
  • основанные на рекуррентном соотношении.

Данный алгоритм осуществляет формирование фронта и прокладывание трассы одновременно. Источником волны на каждом шаге является конечный элемент участка трассы, проложенной ранее.

Маршрутный алгоритм, основанный на вычислении расстояния между точками[править | править вики-текст]

Работа этого алгоритма начинается с начального элемента. Возле него рассматривается окрестность с восемью элементами. От каждого из них до конечного элемента оценивается длина пути. Расстояние между точками можно вычислить по следующей формуле: C=|Ai-AD|+|Bi-BD|, где (Ai, Bi) — координаты точки окрестности, (AD, BD)- координаты последнего элемента. Из всех найденных значений выбирается наименьшее. В качестве элемента трассы здесь выбирается элемент, расстояние от которого оказалось минимальным. Вокруг этого элемента опять рассматривается окрестность с восемью элементами. Процесс заканчивается, если пришли к конечному элементу. При условии возникновения на пути препятствия в виде запрещенного элемента, обход препятствия производится по усмотрению создателя. При этом задаются направления обхода препятствия.

Маршрутный алгоритм, основанный на рекуррентном соотношении[править | править вики-текст]

Маршрутный алгоритм можно также построить на основе следующего рекуррентного соотношения: у(х) = 2у(х + g) + у(х + 2g) + f, где х, у(х) — абсцисса и ордината элемента занимаемого трассой на данном шаге, (х + g) — ордината элемента занимаемого трассой на предыдущем шаге, (х + 2g) — ордината элемента отстоящего от вычисляемого на 2 шага, g — величина изменения абсциссы на каждом шаге, f — это функция определяющая вид трассы.

Когда f = 0, строится прямолинейная трасса; когда f = const, строится параболическая трасса. Ордината следующего элемента трассы рассчитывается по рекуррентной формуле, а абсцисса рассчитывается по формуле: C = An = An-1 + g. Знак «+» или «-» в рекуррентной формуле выбирается в зависимости от того, от какого элемента начинается построение трассы (от начального или от конечного). Например, для того чтобы найти 3-й элемент трассы по этой формуле, необходимо указать два предыдущих. Первым является элемент X(AX, BX). Ордината второго вычисляется по формуле: B(A) = B(AX) + ((B(AX) - B(AY)) / (AX - AY)) * g. Если на пути встречается запрещенный элемент, то его обход так же, как и в алгоритме, основанном на вычислении расстояния между точками, осуществляется по усмотрению разработчика.

Главное достоинство данного алгоритма — простота, а также возможность движения по диагонали.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Внешние ссылки[править | править вики-текст]

Англоязычные
Русскоязычные