AI в играх. Алгоритмы поиска пути


Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Notice: Функция get_currentuserinfo с версии 4.5.0 считается устаревшей! Используйте wp_get_current_user(). in /hlds/web/u138079p19/code4life.ru/htdocs/wp-includes/functions.php on line 3840

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

Терминология

Поиск пути — это поиск компьютерным приложением кратчайшего маршрута между двумя точками. Эта область исследований в значительной степени основана на алгоритме Дейкстры для нахождения кратчайшего пути на взвешенном графе. Кстати у него же можно посмотреть про организацию обратной польской нотации.

Оптимальный (быстрый и логичный в зависимости от необходимой длины) поиск пути возможен только на дискретном пространстве, то есть на том пространстве, которое было поделено специально для поиска пути. Итог дискретизации пространства – граф, читаем здесь.

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

Две основные задачи поиска пути:

  1. поиск пути между двумя узлами в графе;
  2. кратчайший путь — найти оптимальный кратчайший путь.

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

Большая часть разновидностей модификации алгоритмов A* (A star) (вики) и Дейкстры (вики), в основном ищут пути посредством эвристики. Эти алгоритмы являются одними из лучших общих алгоритмов для real-time, которые ищут путь на графе без предварительной обработки.

Эвристика — набор приемов и способов облегчить задачу.

Адаптируя по наш случай, это «примерно прикинул, должно быть нормально».

В случае регулярной сетки, соседние вершины принято классифицировать двумя способами:

  • в окрестности фон Неймана соседними ячейками считаются только 4 ячейки по вертикали и горизонтали,
  • в окрестности Мура — все 8 ячеек, включая диагональные.

Алгоритмы поиска пути

Поиск пути алгоритмом Дейкстры

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

В данном случае длина ребра может быть условной.

A* (A-Star)

модификация алгоритма Дейкстры. A* присваивает вес каждому открытому узлу, равному весу края, этого узла плюс приблизительное расстояние между этим узлом и концом. Это приблизительное расстояние определяется эвристикой и представляет собой минимально возможное расстояние между этим узлом и концом. Это позволяет устранить более длинные пути после обнаружения исходного пути. Если существует путь длины x между началом и концом, а минимальное расстояние между узлом и финишем больше, чем x, этот узел не нужно проверять.

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

F=G + H

где:

G — стоимость передвижения из стартовой вершины к данной, следуя найденному пути к этой клетке.

H — примерная стоимость передвижения от данной вершины до конечной. Это есть эвристическая оценка пути. Стоимость H может быть вычислена множеством способов. Поискав по форумам пришел к выводу что используется метод Манхеттена (Manhattan method), где считается общее количество вершин, необходимых для достижения целевой вершины от текущей, по горизонтали и вертикали (сумма), игнорируя любые препятствия, которые могут оказаться на пути. И умножается на некоторый коэффициент (я умножаю на 10).

Краткое описание (многие нюансы не учтены). Есть закрытый (ячейки которые проанализированы) и открытый (ячейки которые надо анализировать) списки. Просчет начинается со стартовой точки. Каждая клетка имеет родителя (это клетка которая пометила дочернюю клетку), и значения оценки пути F, G, H. Следующая клетка на просчет берется из открытого списка, причем берется та, стоимость которой наименьшая. И опять анализ, и так до тех пор пока не дойдем до конечной точки.

Сборка пути осуществляется движение от конечной ячейки, по родительским ячейкам, в стартовую.

Рекомендую эту статью для изучения, сам по ней делал поиск пути.

Алгоритм трассировки волн (волновой алгоритм)

алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.

Состоит из двух этапов:

  • распространение волны
  • восстановление пути.

Распространение волны начинается от стартовой вершины в соседнюю, при этом проверяется, не принадлежит ли она ранее меченной в пути вершине.

Если вершина не принадлежит к ранее помеченным в пути вершинам, то в ее атрибут записывается число, равное количеству шагов от стартовой вершины. Каждая такая вершина при следующей итерации распространяет свою волну.

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


В общем ничего сложного, главное просто вникнуть в суть. Когда разбирал поиск пути, мы с моделером чертили регулярную сетку на бумаге и вручную карандашом считали все значения для каждой ячейки и помечали. Поначалу была всякая ересь, но к концу дня все прояснилось. В итоге за целый день изучения удалось осилить алгоритм A*. Рекомендую опробовать алгоритм на бумаге))

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*