Иерархический поиск пути

Для разработки небольшой компьютерной игры зачастую применяются базовые алгоритмы поиска пути (алгоритм Дейкстры, А*), которых вполне достаточно для игрового поля не слишком больших размеров. Однако как же решить задачу о поиске пути на громадных игровых пространствах в играх жанра RTS или RPG? Ведь в виду значительного потребления памяти и ресурсов процессора базовые алгоритмы не подходят. О решении этой проблемы (а также нескольких других) и пойдет речь дальше в статье.

HPA*

Рассмотрим первую проблему, а именно поиск пути на огромных пространствах. Иерархический подход довольно сильно напоминает то, как путь строит сам человек. В случае если надо добраться в другой город, сначала строиться путь по городам (верхняя иерархия), а потом уже прокладывается детальный путь учитывая улицы городов, через которые предстоит пройти (нижняя иерархия). Примерно таким же способом работает алгоритм HPA*:
— Разбиваем карту на зоны
— Строим граф из глобальных зон учитывая проходы между ними
— Ищем путь сначала по зонам, а дальше в каждой отдельной зоне
Так имея такую карту:

формируем карту проходимости (где указываем проходимые/непроходимы ячейки) и разбиваем все на зоны

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

Если ширина прохода небольшая, то выбираем одну точку посредине прохода которая попадет в граф. Если же ширина большая, то весь участок прохода можно разделить на несколько единичных точек прохода (к примеру на два точки по краям).
Для определения связанности точек в отдельно взятой зоне, можно использовать базовые алгоритмы поиска.
Примечание: На небольших участках, в которых алгоритм поиска должен пройти большую часть участка, алгоритм Дейкстры может оказаться более оптимальным за А*.
Рассмотрим зону с уже найденными точками проходов. Перебирая по очереди все входы в зону (они также являются выходами) ищем путь к всем другим точкам входа. Построенный путь можно запомнить для использования в детальном поиске пути, хотя для глобального графа вполне хватит и значения длины пути между входами.
В конце получим такую часть графа для этой зоны, где грани указывают на присутствие прохода между входами и длину пути между ними:

Конечный граф прохода по зонам будет выглядит следующим образом:

Для поиска пути по такой карте, сначала определяем стартовую и конечную точку:

Далее ищем пути от интересующей точки ко всем входам зоны в которой точка находиться:

Таким образом имея начальные входные и выходные точки уже можно найти путь по глобальному графу определяя зоны которые предстоит посетить.

Как и ранее для поиска пути по графу можно использовать базовые алгоритмы Дейкстры или А*.
Все что останется, это найти более детальные проходы по зонам.

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

К преимуществам алгоритма HPA* можно отнести:
— Простоту в реализации
— Не больше потребление памяти
— Скорость работы
Из недостатков же отметим:
— Путь рассчитываться только для юнитов одного размера
— Не учитывается разная проходимость карты
— Не самый оптимальный путь, хотя для игры вполне достаточный

АА*

Проблема с поиском пути для юнитов разного размера решаться алгоритмом АА* (Annotated A*). Для учитывания разных размеров проще всего построить карту проходимости — сетку (по которой двигаются юниты), каждая ячейка которой будет указывать на максимальный размер юнита, который там может поместиться. Соответственно путь для конкретно юнита строиться только по тем ячейкам, значение проходимости которых больше или равно размеру самого юнита:

На изображении указан путь для юнита размером в 1:

Схематически поиск пути юнита размером 2 выглядит не сложнее:

Есть несколько способов построения карты проходимости — от банального перебора каждой ячейки и поиска ближайшего к ней препятствия, до некоторого варианта «размытия» препятствий.
В случае разного типа поверхности (земля, вода, либо юниты способный передвигаться как по земле, так и по воде) необходимо строить отдельную карту проходимости для каждой поверхности.
Прохождение для воды (синие ячейки):

Прохождение для земноводного юнита:

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

HAA*

Итак, имея карту проходимости для отдельных зон (как и в HPA* все игровое пространство разделяется на зоны), осталось только построить глобальный граф проходимости между зонами:

Рассмотрим проход между зонами С1 и С3:

Как видим, здесь есть проход для наземного юнита размером не более 2 ячеек (Е1), водного юнита размером в одну ячейку (Е2), и земно-водного юнита размером 5 ячеек (Е3). Эта информация и служит для построения графа проходов между зонами. Далее используя АА* следует определить все возможные пути (учитывая разные размеры и типы поверхности) между входами для каждой зоны. Запоминаем информацию о том, какой тип юнита может пройти по построенному локальному пути (как и саму длину пути):

В даном случае получаем часть глобального графа, по которой видно, что зона С1 имеет 3 входа с разной проходной возможностью между ними для разных типов юнитов. Полный граф переходов для всех зон будет выглядеть примерно так:

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

Поиск самого пути осуществляется так же как и в HPA*: ищем пути к входам зоны в которой находиться стартовая/конечная точка, строим путь между зонами, учитывая размер юнита и проходимость разных типов поверхности.

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

Полезные ссылки:
— Иллюстрации к статье взяты из этой презентации:
harablog.files.wordpress.com/2009/06/beyondastar.pdf
— Описание еще одного алгоритма поиска пути для стратегической игры:
astralax.ru/articles/pathway
— Доклад Андрея Плахова «Алгоритмы иерархического поиска пути в играх»:
www.kriconf.ru/2003/index.php?type=thesis