Алгоритмы преследования

Вне зависимости от жанра игры всегда существуют случаи, когда необходимо заставить неигровых персонажей (non player character – далее npc) преследовать игрока, либо наоборот, убегать он него. Этот класс задач решают алгоритмы преследования/бегства <ref> Bourg D., Seeman G AI for Game Developers. — O’Relly, 2004. — 400 с.</ref>. Алгоритмы преследования и бегства рассматриваются в совокупности, так как, по сути, отличаются только знаком и легко преобразуются один в другой. Далее если речь идет об алгоритме преследования, то подразумевается также и алгоритм бегства. Проблема преследования/бегства состоит из трех частей:

• Принятие решения о начале преследования.
• Оценка эффективность преследования, т.е. насколько быстро хищник догонит жертву и как это будет выглядеть визуально;
• Решение проблемы обхода препятствий во время преследования.

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

Базовый алгоритм преследования

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

В этом примере хищник находится в точке с координатами predatorX, predatorY, а жертва – в точке с координатами preyX, preyY. В процессе игрового цикла происходит сравнение координаты X хищника и жертвы: если координата хищника больше, чем координата жертвы, то координата хищника уменьшается, иначе увеличивается. Аналогично проверяется положение по координате Y.

Как видно по рисунку, сначала преследователь двигается по диагонали, а когда разница по одной координате исчезает, то продолжает движение уже по прямой линии. Хотя результат достигается, но визуально это выглядит неестественно.

Преследование в прямой видимости

Как было сказано выше, игровая карта разделена на ячейки. Это накладывает определенные ограничения на движение npc, которых нет в непрерывных средах. В частности, npc имеет ограниченное число направлений движения (4, 8 и т.д.), что делает невозможным построение вектора, соединяющего хищника и жертву. Поэтому необходимо построить видимую линию, проходящую через некоторое количество ячеек, соединяющую хищника и жертву. Базовый алгоритм не способен на это, что иллюстрирует рисунок.

Для построения такой линии можно воспользоваться алгоритмом Брезенхема. Он является одним из наиболее эффективных методов построения линий в дискретной среде. Главным его свойством является то, что он никогда не построит двух смежным пикселей по более короткой координатной оси. Сначала алгоритм проверяет, по какой оси координат расстояние между объектами больше. Если по оси Х, то выполняется первая часть начального условия, иначе вторая. Далее вычисляется поправка

fraction = deltaRow∙2 - deltaCol,

где deltaRow – разница между координатами между жертвой и хищником по Y;

deltaCol – разница между координатами между жертвой и хищником по Х. Если поправка больше или равна нулю, то происходит увеличение координаты по оси Y, а затем после выхода из второго условного оператора увеличение координаты по Х. Если же поправка отрицательна, то изменение произойдет только по X. Т.е. за один шаг алгоритм может построить либо смежную ячейку, либо диагональную. Результат работы алгоритма прямой видимости представлен на рисунке.

Алгоритм на основе потенциальной функции Ленарда-Джонса

В физике формула Ленарда-Джонсона представляет потенциальную энергию притяжения и отталкивания между молекулами:

<math>U = -\frac{A}{r^n} + \frac{B}{r^m}</math>,

где U – межмолекулярная потенциальная энергия;

A, B, n, m параметры, которые подбираются экспериментально,

r – расстояние между молекулами.

Первая возможность, которую позволяет реализовать данная функция, это притяжение npc к жертве, т.е. реализация преследования. Изменяя параметры в формуле можно изменять скорость преследования, форму траектории преследования, а также заставить npc убегать от игрока. Также задавая объектам различные веса, можно сделать их более и менее «притягательными» для npc. Вторая возможность – это реализация обхода препятствий. Мы можем использовать эту же формулу, так как она состоит из двух частей: первая отвечает за отталкивание, а вторая за притяжения. Таким образом, меняя коэффициенты можно заставить npc отталкиваться от каких-либо объектов, т.е. реализовать обход препятствий. Необходимо отметить, что здесь подразумевается обход одиночных препятствий, таких как деревья и т.п. Также данный подход позволяет группировать npc и заставлять их действовать в группе на основе притяжения и отталкивания между ними. Однако данный алгоритм достаточно сложно реализовать в дискретной среде, а также в условиях лабиринта, так как отталкивание от стен будет неэффективным.

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

В первом приближении поиск пути – это простой процесс перемещения позиции npc из начальной точки в точку назначения. Это работает по такому же принципу, который был использован в базовом алгоритме преследования. Таким же образом можно использовать алгоритм преследования в прямой видимости, для построения более естественного пути. Рассмотренные методы достаточно производительны и их необходимо использовать когда представляется возможность, однако у этих алгоритмов есть недостаток. Все их выгодны сводятся на нет, как только они натыкаются на препятствие. Для обхода препятствий необходимо либо модифицировать данные алгоритмы, либо воспользоваться алгоритмами поиска пути. Данные алгоритмы можно модифицировать, чтобы позволить им обходить препятствия. Один из способов это случайное изменение координаты преследователя при столкновении с препятствием. Однако данный метод эффективен только при одиночных препятствиях, например если на пути хищника встало дерево, то любое изменение его координаты приведет к обходу этого дерева и позволит продолжить преследование. Также существует способ трассировки вокруг препятствия. Данный метод позволяет обходить достаточно большие препятствия, с которыми бы не справился первый алгоритм. Данный алгоритм способен обходить любые одиночные препятствия, однако в рамках лабиринта данный подход не может быть эффективным, так как в лабиринте разумно спланировать весь путь перед началом перемещения, а трассировка вокруг препятствий далеко не всегда приведет к цели.

Алгоритм поиска в ширину

Среди множества алгоритмов поиска пути <ref>Stout B. Алгоритмы поиска пути.</ref> можно выделить несколько основных:

• трассировка вокруг препятствия;
• поиск в ширину (двунаправленный поиск в ширину);
• алгоритм Дейкстры;
• поиск в глубину;
• А*.

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

Суперэвристический алгоритм

Рассмотрим ситуацию, когда при преследовании алгоритм натыкается на препятствие. Так как алгоритм преследования не способен сам обойти препятствие, необходимо воспользоваться каким-либо другим алгоритмов, который может найти путь, что позволит достигнуть целевой точки. Можно, например, опять воспользоваться алгоритмов А*, однако цель курсовой работы – найти какую-либо альтернативу А*, поэтому предлагается использовать алгоритм поиска в ширину. Данный алгоритм будет являться суперэвристическим, так как содержит в себе несколько алгоритмов, выполнение которых происходит при определенных условиях.

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

Итоги и перспективы

В процессе выполнения исследования были рассмотрены алгоритмы преследования и выбран наиболее подходящий из них для реализации, также были проанализированы алгоритмы поиска пути и реализован суперэвристический алгоритм на основе выбранного алгоритма преследования и поиска пути. В ходе работы были программно реализованы базовый алгоритм поиска пути и алгоритм преследования в прямой видимости, приведены графические результаты работы данных алгоритмов, т.е. траектории преследования. Данное приложение можно скачать по приведенной в начале статьи ссылке. Для работы приложения необходимы .NET Framework 3.5 и XNA Framework. Результатом исследования является разработанный суперэвристический алгоритм и его программная реализация в видеоигре PacLight. Дальнейшие планы исследования - анализ суперэвристического алгоритма, подбор и тестирование различных эвристик при переходе от одного алгоритма к другому и временная оценка алгоритма.

Список использованных источников

<references />