Реклама:

Прежде чем разбирать сами алгоритмы, сделаем важное замечание. Все алгоритмы поиска путей работают или с массивом, который отождествляет игровой мир, или со списком опорных точек — так называемых "waypoints". Первый способ подходит для движков, у которых все объекты стоят строго в узлах воображаемой сетки и имеют одинаковые или кратные размеры. К ним относятся почти все тайтловые движки, движки разных классических игр и головоломок и даже движки стратегий с простой геометрией объектов. В них во всех карту игры можно представить в виде массива:

Мар:аггау[1. .М, 1. -N] of integer;

где MxN — размер карты в ячейках, а в каждой ячейке содержится цифра, соответствующая типу территории. Например: 1 — стена, пройти невозможно; 2 — ограда, пройти невозможно, но можно стрелять сквозь нее; 3 — забор, можно сломать и пройти, но на это затратится 5 элементарных единиц времени; 4 — болото, можно пройти, но за 3 единицы времени на каждую клетку; 5 — ровная дорога, можно пройти за 1 единицу времени на каждую клетку и т.д.

Для стратегий с объектами сложной формы и всех нормальных "экшенов" карта представляется в виде совокупности waypoints. Каждую опорную точку можно представить так.

PWaypoint=~TWaypoint;

TWaypoint=record

Position:TGLCoordinates;

Connections:array of PWaypoint;

Territory:integer;

Radius:double;

end;

Первая строчка объявляет тип указателя на TWaypoint. В самой записи TWaypoint поле Position — координаты опорной точки, Connections — динамический массив с указателями на ближайшие опорные точки, в которые можно без препятствий дойти из этой точки, Territory— тип территории, на которой стоит опорная точка. Впрочем, этот параметр необязателен. Вы можете симулировать его, например, высотой того места, на котором стоит опорная точка. Последний необязательный параметр Radius показывает зону действия опорной точки, т.е. на каком максимальном расстоянии может находиться юнит, чтобы считать себя стоящим на ней.

Все опорные точки для одной карты лучше хранить в списке или динамическом массиве. Как создавать эти опорные точки —

вопрос особый. Вы можете предусмотреть для этого специальный инструмент в редакторе карт, чтобы дизайнеры уровней расставляли их вручную. Вы можете рассчитывать положение опорных точек автоматически при загрузке уровня, но дело это довольно сложное. Где ставить опорные точки — вопрос не менее интересный. У каждого из углов объекта, как внутренних так и внешних, чтобы юниты могли легко его огибать. В тупиках, узких проходах между объектами, в местах смены одного типа территории на другой — словом, везде, где нормальный человек сначала подумал бы, прежде чем идти дальше. Наконец, в центре больших открытых пространств, причем параметр Radius ставьте таким, чтобы он перекрывал большую часть этого пространства. В пределах этого круга юниты могут передвигаться свободно, по кратчайшей прямой, так как препятствий там нет. Теперь давайте перейдем к самим алгоритмам.

На гребне волны...

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


⇐ Предыдущая страница| |Следующая страница ⇒