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

В практике компьютерных игр часто возникает необходимость проложить курс от пункта A в пункт Б на игровом поле с отмеченными непроходимыми областями. Это может быть нужно например при движении бота к персонажу игрока. В зависимости от типа игрового мира к поиску пути применяются разные подходы. 
 В одном случае карту мира можно представить в виде дискретной сетки. перемещение по нему сводится к перемещению по клеткам карты. Тогда математической моделью может служить ориентированный граф вершины которого соответствуют клеткам, а рёбра возможностям перехода из одной клетки в другую. В другом - же случае мир непрерывен и положение объектов определяется их геометрической формой и взаимным расположением. Часто применяется и комбинированный подход 
 Если мир дискретен найти путь значит найти последовательность клеток перемещаясь по которым можно перейти из одного положения в другое. Когда — же мир непрерывен, найти путь значит найти функции линейного и углового ускорения от координат. Таким образом алгоритмы поиска пути делятся на дискретные и непрерывные. В статье [3] также предлагается деление на алоритмы локального и глобального поиска. При этом, под алгоритмами локального поиска автор понимает поиск пути в непосредственной близости от цели, соответственно, под алгоритмами глобального поиска понимается поиск на некотором протяжённом расстоянии. Однако, такое деление представляется достаточно условным так как в различных ситуациях один и тот — же алгоритм может использоваться как вблизи, так и на большом расстоянии от цели.

Алгоритм A*

 Алгоритмы поиска на дискретной карте сводятся к поиску пути на графе. Существует несколько алгоритмов поиска пути. Среди них чаще всего используется алгоритм А со звездой или A* - поиск по первому наилучшему совпадению. Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)). 
Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. Этот алгоритм был впервые описан в 1968 году Питером Хартом Нильсом Нильсоном и Бертраном Рафаэлем. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.
 A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а неf(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью. от предыдущей, как в жадном алгоритме).
В начале работы просматриваются узлы, смежные с начальной; выбирается тот из них, который имеет минимальное значение 

Ввиду большой важности рассмотрим данный алгоритм более подробно. Пусть есть ориентированный граф вершинами которого являются клетки карты а рёбрами пути из клетки в клетку в случае если такой путь существует. Каждому ребру припишем некоторое число - стоимость перехода от клетки в клетку. 
Алгоритм оперирует двумя списками: сортированным (далее open), в котором хранятся вершины, ребра которых еще не были обработаны (узлы сортируются по оценке расстояния до конечного узла от наиболее близкого), и не сортированный (далее close) с обработанными узлами. Изложим принцип работы данного алгоритма в виде диаграммы деятельности.

Алгоритм A* является полным в том смысле, что он всегда находит решение, если таковое существует. Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, или преемственной эвристикой. Свойство монотонности означает, что если существуют пути A—B—C и A—C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше либо равна сумме оценок путей A—B и B—C. A* также оптимально эффективен для заданной эвристики h. Это значит, что любой другой алгоритм исследует не меньше узлов, чем A* (за исключением случаев, когда существует несколько частных решений с одинаковой эвристикой, точно соответствующей стоимости оптимального пути). В то время как A* оптимален для «случайно» заданных графов, нет гарантии, что он сделает свою работу лучше, чем более простые, но и более информированные относительно проблемной области алгоритмы. Например, в некотором лабиринте может потребоваться сначала идти по направлению от выхода, и только потом повернуть назад. В этом случае обследование вначале тех вершин, которые расположены ближе к выходу (по прямой дистанции), будет потерей времени.

Проблемы возникающие при реализации A*

Скорость выполнения алгоритма

Основная сложность с реализацией A* состоит в увеличении скорости вычислений. Действительно, с ростом количества одновременных поисков и размеров карты вычисления занимают всё больше машинного времени. Как известно, основное время в поиске пути занимает работа с Open и Closed списками. Хорошо продумав алгоритмы поиска и вставки элементов можно существенно увеличить скорость работы А*. К сожалению правильной реализации собственно поиска может оказаться недостаточно в случае очень большой карты или большого количества одновременных поисков. Кроме того, следует учитывать особенности реализации структур данных для выбранной платформы. Поэтому на практике применяют ряд подходов, которые позволяют уменьшить применение А*. Некоторые из них описаны ниже.

Уменьшение точности поиска.

В случае, когда расстояние между пунктами, для которых необходимо проложить путь весьма велико, не имеет смысла находить путь с точностью до клетки. Достаточно разделить карту на непересекающиеся области или локации и в начале поиска определить последовательность локаций пройдя которые можно очутиться в исходной точке. Далее, определив необходимую локацию и соседнюю с ней, можно искать путь лишь по клеткам смежных локаций.
Остановимся подробнее на требованиях, которые налагаются на локации. В большинстве случаев путь от точки А к Б ищется для того, чтобы произвести определённые действия, к примеру бот ищет путь к персонажу игрока для того, чтобы атаковать его. Понятно, что для атаки в большинстве случаев необходимо, чтобы игроки были видимы друг другу, или говоря иными словами между ними не должно быть непроходимых областей, или клеток, если речь идёт о двумерной карте. Т.е. между центрами клеток в которых находятся персонажи A и Б можно провести прямую так, чтобы она не пересекала непроходимых клеток. Таким образом мы видим, что локация является частным случаем выпуклого множества [2] и задача разбиения карты на локации сводится к разбиению на выпуклые множества.

Предварительный расчёт пути.
Для крупных областей речь о которых шла в предидущем пункте имеет смысл расчитать оптимальные пути до начала игры. В этом случае мы экономим достаточно большое количества времени, в то — же время объем памяти необходимых для хранения матрицы путей незначителен.

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

Проблема неестественной траектории

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

Представлена ситуация Case 1 в которой найдены два эквивалентных с точки зрения длинны поиска пути, однако очевидно, что ломаная с большим числом углов выглядит неестественно.
Далее, в ситуации Case 2 показана траектория движения соединяющая центры клеток. Понятно, что более естественной траекторией была — бы гладкая кривая обозначенная пунктиром.
В ситуации Case 3 оптимальной траекторией была — бы прямая обозначенная пунктиром. Однако, в следствие квантизации пространства, путь который нужно пройти по клеткам покрывающим её будет эквивалентен показанным сплошной линией ломаным траекториям.
Одним из путей решения проблемы естественности пути является интерполяция траектории сплайном. Другим путём решения проблемы будет предварительная проверка существуют — ли непроходимые клетки между исходной клеткой и целью. Если таких клеток нет, в использовании A* нет необходимости.

Метод потенциальных полей.
Другим часто применимым методом поиска является метод потенциальных полей. В соответствии с этим методом каждое препятствие имеет вокруг себя отталкивающее потенциальное поле сила которого обратно пропорционально расстоянию до него. Также существует однородная сила притяжения к цели. Через близкие постоянные интервалы времени вычисляется сумма притягивающих и отталкивающих векторов и объект передвигается в этом направлении.
Таким образом, отталкивающая сила будет равна


Где - искомая ф — ция дающее направление движения в данной точке карты, - сила притяжения к цели - сумма сил отталкивания от препятствия соответственно.
Очевидно, что возможны случаи, когда значение равна нулю, а значит направление движения неопределено. Эта проблема называется проблемой локальных минимумов.
Существует ряд способов её решения. Так например пытаются подобрать ф — ции, которые не имеют локальных минимумов. Другое решение состоит в том, чтобы при попадении в локальный минимум временно изменить цель, по достижении этой временной цели двигаться по направлению к главной. Данный способ выхода из локального минимума называется методом виртуальных локальных целей и изложен в [4].
Вариацией метода потенциальных полей является метод виртуальных отталкивающих клеток изложенный в [5]. Его суть состоит в том, что игровое поле разделяется на клетки (поля) и если клетка содержит препятствие, она обладает отталкивающим потенциалом. Объект, для которого нужно найти путь представляется находящимся в центре квадрата стороны которого параллельны клеткам игрового поля. Если клетка с препятствием попадает внутрь квадрата, она производит отталкивающее действие, иначе нет. Результирующая сила вычисляется как сумма отталкивающих сил от клеток с препятствиями и притягивающей к цели силе. Таким образом устраняется влияние удалённых препятствий и отдалённых частей препятствий большого размера. В следствие этого, траектория движения получается более плавной.
Иллюстрация метода представлена на рисунке.


Метод точек видимости
Данный метод всегда применяется в комбинации с методом поиска пути на графе и часто с методом потенциальных полей. Суть его в том, что вокруг неподвижных препятствий, на достаточном от них удалении чтобы избежать столкновений, расставляются точки видимости. Две точки считаются соединёнными если они видимы между собой, то есть отрезок прямой между ними не пересекает неподвижных препятствий. Математической моделью в данном случае является неориентированный граф вершины которого соответствуют точкам видимости. Две вершины соединены если соединены две соответствующие точки. Движение между двумя соседними точками можно осуществлять с помощью метода потенциальных полей. В этом случае другие объекты для которых ищется путь могут рассматриваться как препятствия. Например, когда требуется найти путь для нескольких роботов противника движущихся к роботу игрока.

Литература
1.Принцип работы алгоритма поиска пути Астар (A*) http://www.gamedev.ru/articles/?id=70121
2.Материалы сайта http://dic.academic.ru/
3.The long and short of steering in computer games Simon L. Tomlinson 2 Campden Way, Handforth, Cheshire. SK9 3JA, United Kingdom e-mail: DrSimonT@iclway.co.uk
4.ISSN 1009 - 3095 Journal of Zhejiang University SCIENCE V. 4, No. 3,P. 264-269, May- June, 2003 http://www. zju.edu.cn/jzus; http: //www. periodicals, com. en; jzus@zju. edu. en
Virtual local target method for avoiding local minimum in potential field based robot navigation ZOU Xi-yong( Ä ! )+, ZHU Jing( Ü ft ) ( College of Electrical Engineering National Laboratory of Industrial Control Technology » Zhejiang University * Hangzhou 310027» Chinai 'E- mail : zouxiyong @ 163 . net Received June 3» 2002; revision accepted Aug. 10» 2002
5.Applying an Enhanced Path Finding Avatar for a Virtual Environment Jui-Fa Chen, Wei-Chuan Lin*, Li-Hao Yang Department of Computer Science and Information Engineering, TamKang University, Danshui, Taiwan 25137, R.O.C E-mail: alpha@mail.tku.edu.tw Department of Information Technology, Tak-Ming College, E-mail: wayne@takming.edu.tw