Бесплатная реклама

Автор: Алексей Седов «onimod_land»

Опубликовано: 07.09.2006

Изменено: 07.09.2006

Постоянная ссылка

Комментарии [1]

Алгоритм построения пути в стратегической игре





Страницы: 1 2

Подготовка дискретных клеток

Подготовить дискретные клетки совсем не так просто, как может показаться.
Примерная структура дискретной клетки:

  1. Двумерный массив 6х6 байт, где нужно хранить номера районов. Для чего он вообще нужен? Дело в том, что обычные координаты в дискретные перевести очень просто (разделить на 6), а вот определить номер района внутри дискретной клетки – дело совсем непростое. Поэтому для оптимизации это лучше сделать заранее.
  2. Каждый имеющийся район должен иметь список связей с другими дискретными клетками, причем помимо координат, должен еще быть указан номер района. Вместо координат лучше использовать код направления (влево, вверх и т.д.).
  3. Также каждый район должен иметь нижеописаные поля.

Маркер - будет использоваться в момент построения волны, чтобы определить, посещала ли волна это место ранее. Кроме того, Маркер используется для маркировки целей, т.е. точки Б.

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

Стоимость – это поле может быть применено для некоторой оптимизации пути, но обязательным не является.

Время создания – это поле относится не к каждому району, а целиком к дискретной клетке. Требуется для того, чтобы юниты корректно воспринимали ситуацию, когда содержимое дискретной клетки изменяется.

ВАЖНО!
Обычно в стратегиях бывают юниты больших размеров. Например, танк почти гарантированно будет иметь размер 2х2. Если у вас есть большие юниты, то вам придется сделать дискретные клетки дважды, ведь будет совершенно невозможно, использовать районы юнитов 1х1 под юнитов 2х2. К сожалению, при определении районов под 2х2 существует много всяких мелочей, которые поначалу труднозаметны. Например, сбоку дискретной клетки имеется свободная линия шириной в одну клеточку (т.е. танк 2х2 туда не лезет). Однако если половина танка будет находиться на соседней клетке, то он вполне может своей второй половиной быть на этой линии. А отсюда вывод – эта линия вполне нормальный район для объектов 2х2, хотя они там и не умещаются.
Существуют и другие тонкости...

Подготовьте дискретные клетки перед запуском карты. Возможно, вам понадобится 2 вида дискретных клеток из-за юнитов размером 2х2 или один вид дискретных клеток, но с двумя видами районов внутри. Лично я использовал второй вариант. Прежде чем делать районы типа 2х2 рекомендую взять бумагу и карандаш, и заняться более детальным изучением этого вопроса, а, именно, моделированием разных ситуаций. Мелкие ошибки в построении районов выловить совсем непросто, так как ответить на вопрос: "почему танк поехал к цели в объезд?" не всегда является возможным. Частично в этой ситуации может помочь функция, которая будет записывать в удобном виде содержимое дискретной клетки в BMP-файл. Это позволит увидеть глазами содержание проблемной дискретной клетки (пример записи BMP-файлов можно найти в MSDN).

Обновление дискретных клеток во время игры

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

ВАЖНО!
Вы должны обновить не только те дискретные клетки, которые непосредственно были затронуты изменением, но еще и на некотором расстоянии, иначе будет происходить порча связей между районами. В "Земле онимодов" я увеличивал эту площадь на 3 клетки с каждой стороны.

Необязательно, но желательно.
Чтобы не проверять во время игры координаты клеток на выход за пределы поля, очень неплохо бы обнести поле невидимым "забором", т.е. реально поле должно быть немного пошире и подлиннее (в моем случае на 6*2=12), а весь периметр надо заполнить непроходимостями. Это избавит вас от постоянных проверок типа:
    if (x>=0 && x<длина_карты && y>=0 && y<высота_карты)

Реализация алгоритма поиска пути

Теперь у нас есть подготовленные заранее дискретные клетки. Но что же делать дальше? Как же организовать волновой алгоритм на практике?

Итак, полный алгоритм построения пути состоит из 2-х частей:
    1) Построение пути из дискретных клеток с помощью дискретной волны;
    2) Объединение пути из дискретных клеток с помощью обычной волны.

Организация дискретного волнового алгоритма

Давайте сначала разберемся с некоторыми аспектами организации. При описании структуры дискретной клетки добавлены некоторые поля, которые используются только в момент построения волны. Давайте посмотрим на поле Маркер.

Когда волна расползается нужно как-то помечать те места, которые она уже успела обойти. Но подумайте вот над чем - если вы будете помечать "обойденные/не обойденные" места по принципу "0/1", то тогда после каждого построения вам придется подчищать все единицы. Поэтому поступим по-другому - введем понятие Маркер.

Представьте, что мы вызываем дискретную волну в первый раз (Маркер=0). Тогда мы сразу можем пометить точку Б числом Маркер+1 (1), а саму волну числом Маркер (0). Когда мы будем вызывать дискретную волну 2-ой раз, то перед этим выполним такой простой ход: Маркер=Маркер+2. Т.е. мы будем помечать и волну и цель уже другими числами (3 и 2), что позволит избежать чистки поля от действий предыдущий волны. Когда Маркер исчерпает вместимость переменной типа WORD, то произведем полную очистку маркировки всех дискретных клеток любым числом большим 1 и запишем в Маркер 0.

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

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

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

Сначала надо определить, нужно ли подходить к цели вплотную или только на расстояние выстрела.

Надо подойти вплотную

Первым делом, проверяем «может цель уже достигнута?» Скорее всего «нет»...
Тогда проверяем, можно ли достичь цели, т.е. применяем районы игрового поля, о которых я говорил в самом начале. Если цели достичь нельзя, то просто ищем, начиная от цели, ближайшую точку, которую достичь можно – она теперь и будет целью.
Реально под целью может подразумеваться:
  а) Пустое место
  б) Подвижный юнит
  в) Здание, ресурс или какой-нибудь камушек
  г) Непостроенное здание, т.е. реально его еще нет, но надо подвести к нему работника для строительства>

Во всех этих случаях можно пустить навстречу друг другу сразу 2 волны. Т.е. одна волна расходится из текущего положения юнита, другая из положения цели, каждая проверяет на столкновение с другой волной через поле Маркер. При столкновении - путь построен и остается только вытащить его через поля Источник волны.
Пункты а) и б) ничем не отличаются с точки зрения построения дискретной волны. Здесь целью является одна точка, точнее один район в одной дискретной клетке. Пункт в) и г) тоже схожи, но здесь под целью уже подразумевается некая область – рамка вокруг цели. Как быть в этом случае? Очень просто – можно пустить вторую волну сразу из каждой клетки, которая входит в рамку. Т.е. для каждой клетки, которая входит в рамку, определяем дискретную клетку и район, а затем заносим их в массив волны 2 (только дублировать не нужно). Волна будет расползаться совершенно также.
Можно и не мудрить со второй волной, а просто нанести рамку в качестве цели и проверять одной волной на достижение этой цели.

Надо подойти на расстояние выстрела

Первым делом, проверяем «возможно цель уже достигнута?»
Здесь я хочу разобрать самую сложную ситуацию, которая может возникнуть. Из нее, я надеюсь, станет многое понятно, и вы заранее узнаете о некоторых «граблях», которыми густо усеян путь разработчика. Ситуацию я постараюсь разобрать полностью, т.е. не только с позиций алгоритма пути, а с позиций игры в целом. Представьте, что ваши миротворческие силы победоносным маршем направляются по узкому ущелью в лагерь противника. Но злые недруги построили по краям ущелья несколько оборонительных вышек, которые находятся вне досягаемости вашего отряда, т.е. дойти до вышек пешком невозможно. Зато вышки предательски открывают огонь справа и слева по вашим храбрым воинам, которые, вытянувшись в шеренгу, уверенно маршируют вперед.

Например, в вашего пехотинца попал снаряд от вышки. Что делать?
Конечно, в идеале надо ответить на агрессию и более того, подвергшийся атаке пехотинец должен бы «позвать на помощь» ближайших друзей. Как раз это мы и делаем, но... Сначала проверяем, находится ли вышка в зоне поражения пехотинца? Если «да», то открываем ответный огонь. А вот если «нет»? Ведь вышка наверняка стреляет дальше, чем пехотинец. Тогда надо сначала подойти к вышке на расстояние выстрела. Но тут надо проверить, а можно ли к вышке подойти? Ведь она у нас находится там, куда не забраться, что легко можно установить через сравнение районов пехотинца и вышки (определением районов мы занимались в самом начале статьи). Если дойти можно (это не наш случай), то пехотинец устремляется в атаку на вышку и за ним бегут его друзья по оружию. В нашем случае мы определяем, что дойти нельзя. Что же делать? Да ничего. Надо бежать дальше, так как останавливаться и «толпиться под вышкой» совершенно неразумно. НО! «Звать на помощь» наш пехотинец всё равно может и должен, т.е. он записывает в свою переменную Мой убийца указатель на вышку. Далее пехотинец периодически «зовет на помощь в борьбе против вышки», для чего ищет ближайших союзных воинов и предлагает им в качестве цели вышку. Что должен делать воин, который получает такой призыв о помощи? Для начала проверить, а не занят ли он уже в какой-то перестрелке? Если «да», то нужно оценить эффективность новой цели (вышки) по сравнению с текущей целью. Например, если наш танк занимался расстрелом вражеских рабочих, проходивших мимо, то он должен понять, что уничтожение вышки цель более благородная. Но тут опять возникает необходимость в дополнительных проверках.
Ситуаций несколько:
  1) Танк находится в том же районе, что и вышка – надо просто атаковать вышку.
  2) Танк находится в том же районе, что и пехотинец, а вышка в другом – необходимо сравнить дальнобойность танка и дальнобойность вышки, и если танк стреляет дальше, то атаковать. Если же пехотинец сам атакует вышку, то можно сравнить дальнобойность танка с дальнобойностью пехотинца, так как если достает пехотинец, то и танк сможет дострельнуть.
  3) Танк находится в каком-то своем районе – проверить, не находится ли вышка уже в зоне поражения, если «да», то атаковать.

Как же лучше всего построить путь к вышке, которую реально достичь нельзя?
Самый простой вариант выглядит так. Наносим на дискретные клетки цель в виде окружности вокруг вышки (Маркер+1). Радиус окружности будет равен радиусу стрельбы воина. Теперь строим одну дискретную волну от воина до этой самой окружности. Если окружность достижима, то остается только вытащить путь через поля Источник волны. Если по какой-то причине цель не может быть достигнута, то нужно определять ближайшую дискретную клетку к цели. Это легко сделать через поле Маркер. Далее эта дискретная клетка и будет считаться конечной дискретной клеткой пути, но путь будет считаться непостроенным.

Связывание пути из дискретных клеток

В результате вызова дискретного волнового алгоритма у вас должен получиться путь из дискретных клеток с номерами районов. Кроме того, надо еще вернуть информацию о том, удалось ли построить путь. Как же заставить юнита действительно начать реально двигаться?
Мы знаем, что наш юнит должен обязательно попасть в требуемый район очередной дискретной клетки. А район этот мы можем нанести уже в обычных координатах как цель для обычной волны, даже весь район наносить не нужно, достаточно только ту его часть, которая лежит на периметре дискретной клетки. Список координат района на периметре можно либо готовить заранее (я делаю так), либо получать проверкой периметра всей дискретной клетки. Далее мы применяем самый обычный волновой алгоритм, без всяких оптимизаций, но на очень близком расстоянии. Еще одна тонкость – теперь клетки занятые другими юнитами нужно считать недоступными и обходить их.
В результате получаем коротенький связующий путь от текущей точки до очередной дискретной клетки. Шагаем юнитом по этому пути и, дойдя до конца, опять строим соединяющий путь, но уже со следующей дискретной клеткой. Здесь всё прекрасно, кроме ситуации с последней дискретной клеткой, так как ее уже не с чем связывать. Поэтому здесь надо строить путь прямо до конечной цели. Если это точечная цель, то проблем нет, а вот если это рамка или окружность для выстрела, то придется их наносить на клетки.

Управление алгоритмом пути

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

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

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

  3) Иногда плотность юнитов так велика, что не получается построить связующий путь к следующей дискретной клетке. Это самый сложный момент в управлении маршрутом, ведь в этой толчее практически невозможно определить: стоит ли чего-то ждать или надо пойти другим путем? Еще хуже то, что наш юнит может запросто сам создавать затор. Иногда ситуацию получается расхлебать, если «разогнать» юнитов в произвольных направлениях.
Чтобы пойти другим путем можно заблокировать для дискретного волнового алгоритма ту дискретную клетку, на которую не получается попасть. В Онимодах я блокирую до 3-х таких клеток подряд, после чего строю весь путь с самого начала. Для блокировки дискретной клетки достаточно указать в ней, что волна ее уже посещала, тогда волна туда второй раз не пойдет (если, конечно, вы не используете стоимость).

  4) Если целью является другой юнит, то он может постоянно перемещаться. Т.е. вам придется постоянно полностью перестраивать весь путь. Как же определить момент, когда нужно это сделать? Я делаю так: определяю направление к целевому юниту (т.е. направо, налево, налево и вверх, ...) и если оно меняется, то перестраиваю маршрут полностью. Таким образом, если целевой юнит находится далеко, то направление будет меняться редко, а если близко, то путь будет строиться быстро.

  5) Желательно вести счет тактов, в течение которых, юнит не смог сдвинуться с места. Если этот счетчик начнет превышать какое-то число, то это будет сигналом к принятию экстренных мер, таких как построение обходного пути, перемещение в случайном направлении или прерывание выполнения команды.

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

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

Эффективность

В конце статьи я скажу пару слов об эффективности данного комплекса решений. К сожалению, оценить быстродействие точными цифрами я не могу. Могу лишь высказать свою личную точку зрения. В качестве тестового стенда опять же использую свою игру "Земля онимодов". Так как игру, наверное, видели далеко не все, то скажу о ней пару слов.
Изометрическая 2D стратегия в реальном времени. Мне самому игра представляется смесью Starcraft и Age of Empires. Максимальный размер игрового поля 504х504.

Основные пункты расходов быстродействия процессора, помимо обслуживания всех имеющихся юнитов:
  1) Вывод 2D-графики на экран.
  2) Поиск каждым воином возможной цели в пределах видимости.
  3) Призыв на помощь. Каждый игровой объект часто просит помощи у других объектов. Например, если какой-то юнит воюет, то он «зовет на помощь своих товарищей» в пределах видимости, в результате, воины начинают подтягиваться к месту боя.
Самым тормозящим является пункт 3, так как обращение здесь идет не только к своей команде, но и к командам союзников, например, союзный рабочий может починить поврежденное здание.

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

В процессе отладки своей игры я использовал следующий прием. На карте размером 504х504 создавал 8 команд и делил их на 2 союза (бой 4 на 4). Чтобы самому не напрягаться включал вместо себя компьютерный интеллект, т.е. живой игрок в игре не участвовал. Обычно такая баталия длится 40-50 минут. Ближе к концу счетчики показывают примерно 500-700 «живых» юнитов и 200-250 зданий. Примерно 10-15% юнитов являются летающими, т.е. алгоритм поиска пути не используют. В этом состояние на процессоре Celeron 1000 (разогнанный 667), играть становится очень некомфортно, но вполне можно. Если поделить команды не на 2 союза, а сделать их «каждый сам за себя», то притормаживание очень заметно снизится. Ускорение происходит за счет пункта 3.
На более современных процессорах типа Pentium-4 1700 какого-то серьезного снижения скорости не чувствуется.

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

Алексей Седов
http://www.astralax.ru/projects/others/onimod
support@onimodland.com
onimod_land@mail.ru

Земля Онимодов

 

Страницы: 1 2