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

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

Итак, начнем…

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

Если район точки А равен району точки Б, то путь строить можно. Иначе Б достичь нельзя. Кстати, невозможность достичь точки Б не означает, что к ней не нужно двигаться, но об этом речь пойдет позже.

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

Теперь приступим к определению районов. Для этого пробегаем по всем клеткам карты и для каждой из них выполняем следующее:

int индекс_района = 1;
for (int x = 0; x < длина_карты; x++)
 for (int y = 0; y < высота_карты; y++)
 if (поле[x][y].район != 0 && поле[x][y] != препятствие)
 {
 // для данной клетки надо определить район
 // это делаем методом заливки
 Fill(x, y, индекс_района);
 индекс_района++;
 }

Функция Fill(int x, int y, int индекс_района) должна работать по аналогии с обычной цветовой заливкой. Т.е. заполнять для клеток переменную "район" цифрой "индекс_района". Естественно, что во время заливки те клетки, на которые нельзя "наступить" должны служить границей.

Пример быстрого и простого метода заливки…

Предлагаемый мной метод очень прост и обычно не требует никакой отладки. Эту простую мысль мне подкинул мой друг Роман Коваленко в далеком 1993 году. В те времена я с PC компьютерами вообще не был знаком, мы программировали на самодельных Spectrum-ах, на чистом ассемблере. Тогда одиночка-программист был "один в поле воин", а сейчас… к сожалению, без коллектива никуда. Скучно всё это…

Ну, вернемся к теме статьи. Значит так…

Создаете 2 одинаковых массива большой длины (чтобы не переполнились), в которые будут складываться координаты x, y. Чтобы начать заливку занесите в первый массив координату начала.

Сам цикл заливки выглядит так:

for (i = 0; i < количество_координат_в_массиве1; i++)
{
 int x = массив1[i].x;
 int y = массив1[i].y;
 поле[x][y].район = индекс_района;
 // теперь надо проверить все соседние клетки на возможность заливки
 // соседних клеток будет либо 8 либо 4, в зависимости от того, умеют ли ваши
 // юниты протискиваться в щель по диагонали.
 ……………………………
 ……………………………
 
 ……………………………
 ……………………………
 // если соседняя клетка подходит для заливки (на нее можно встать, она не
 // выходит за поле и пока не была залита), то заносим ее координаты в массив2:
 массив2[количество_координат_в_массиве2].x = x_соседа;
 массив2[количество_координат_в_массиве2].y = y_соседа;
 количество_координат_в_массиве2++;
}

Далее следует точно такой же цикл, только уже по массиву2, но он уже заносит координаты соседей в массив1.

Оба эти цикла надо крутить пока в один из массивов не будет занесено ни одной координаты, что и будет означать, что заливка района закончена, т.е. return.

После определения всех районов массив1 и массив2 можно удалить. Но зато теперь каждая клетка приписана к своему району. Неприписанными останутся только клетки, на которые нельзя встать (район=0) из-за какого либо препятствия.

Желательно, но необязательно…

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

1. Золотая руда, которая раньше не позволяла соединиться двум районам была добыта, т.е. теперь эти 2 района надо бы объединить.
2. В узком проходе игрок построил здание и разделил район на 2 части. Уничтожение здания тоже может иногда объединить районы.
3. Мы определили районы только для юнитов, которые занимают 1 клетку. А ведь где пройдет человек, там катапульта может и не проехать. Т.е. в идеале нужно бы еще определять районы для объектов разного размера.

То, в какой степени необходимо доводить районы до совершенства, во многом зависит от особенностей игры. Если препятствия на игровом поле состоят в основном из леса, который легко добывается рабочими, то, возможно, что пункт 1 реализовать просто необходимо. Что касается моей реализации в игре "Земля онимодов", то я всех этих доработок не делал и, признаться, не жалею. Однако при определении районов я сделал следующее допущение: считал ресурсы и здания (т.е. то, что может исчезнуть с карты) пустым место, т.е. они не препятствовали объединению районов.

Далее я вынужден в 2-х словах остановиться на общеизвестном волновом алгоритме поиска пути, так как, возможно, что кто-то про него не знает или наши представления несколько расходятся. Значит так…

Логика волнового алгоритма аналогична логике заливке, которая была применена выше для определения районов. Т.е. начинаем заливку из точки А и заканчиваем ее, когда эта "волна" достигнет точки Б. Чтобы потом вытащить из волны сам путь нужно просто дополнительно запоминать для каждой клетки, ту клетку, из которой в нее пришла волна. Т.е. надо будет пройтись по этой цепочке назад от точки Б до точки А - это и будет искомый путь. Дополнительно можно делать всякие полезности, например, ввести для каждой клетке "стоимость" прохода. Тогда можно будет для болота назначать высокую стоимость, что позволит алгоритму обходить такие места, если имеется более дешевый путь.

Алгоритм можно оптимизировать, если пускать сразу 2 волны: и из точки А, и из точки Б. В этом случае, надо отлавливать момент, когда волны столкнутся, а далее соединять 2 цепочки в один путь.

Достоинства волнового алгоритма:

1. Путь будет найден всегда и причем самый лучший.
2. Возможность введения стоимости клетки.
3. Возможность построение пути не к одной цели, а сразу к нескольким, т.е. практически происходит поиск ближайшей цели.
4. Понятность и простота алгоритма.

Теперь как всегда немного дегтя…

Использование подобного решения в стратегической игре, где предполагается большое количество юнитов - верный провал. Почему? Да потому, что процессор просто "выдохнется" пытаясь двигать несколько сотен юнитов по игровому полю 256х256. Не буду ничего утверждать по поводу DOOMообразных игр, возможно, что там это и потянет, так как одновременно двигается очень мало объектов и на короткие расстояния.

Давайте лучше подумаем над тем, как из этой красивого, но совершенно неэффективного метода создать то, что действительно будет возможно применить на практике в супербатальной RTS. Значит так… проблема в том, что волна ползет во все стороны и при этом практически "обшаривает" огромное количество клеток, которые впоследствии будут просто отброшены. Например, в моей игре "Земля онимодов", максимальный размер карты 504х504 (почему такие странные цифры объясню потом), т.е. если я отправлю всего лишь одного воина в противоположный угол карты то вполне возможно, что волна посетит примерно половину всех клеток на игровом поле, а это будет: (504 * 504) / 2 = 127008. Только представьте, какое это огромное количество. А ведь юнитов у вас будет много и построение пути будет происходить постоянно. Вопрос… как сократить это количество, причем так, чтобы алгоритм потерял свои черепашьи качества, но при этом мог всегда добраться до цели?

Итак…

Самый ключевой момент

Разбиваем всё наше игровое поле на более крупные клетки. Давайте я назову эти клетки дискретными. В "Земле онимодов" я использовал дискретными клетки с размером 6х6, т.е. в каждой клеточке у меня находится аж 36 обычных клеток. Я выбрал 6 из-за особенностей строения игрового поля в моей игре, вы можете выбрать, например, 8. Размеры вашего игрового поля должны быть кратны размерам дискретной клетки. Поэтому у меня максимальные размеры поля 504х504.

Значит так… суть в следующем: нужно искать путь не по обычным клеткам, а по дискретным. В этом случае для предыдущего примера получим такие результаты: ((504 / 6) * (504 / 6)) / 2 =3528. Т.е. теоретическая оптимизация с 127008 до 3528, а это в 36 раз. Только вместо обычных клеток мы получим путь из дискретных клеток. Ну и что! Теперь можно будет соединять дискретные клетки волной, которая будет строиться по обычным клеткам, а так как дискретные клетки всегда будут соседями, то это будет происходить быстро.

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

Самое главное - дискретная клетка разбивается внутри на районы. Т.е. внутри нее может быть несколько районов, которые не будут соединяться. Очень важно, что соединяться районы не будут только внутри дискретной клетки, а при помощи соседних дискретными клеток они соединяться могут, но всё равно будут считаться разными районами. Это самый важный момент. Еще раз… Дискретная клетка как бы по аналогии со всем игровым полем делится на районы. Районы эти не замыкаются именно внутри дискретной клетки, но могут замыкаться через соседние дискретные клетки.

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

Волну, которая будет строить путь по дискретным клеткам, назовем "дискретной волной". В дискретной волне, в отличие от обычной, принцип определения соседней клетки будет отличаться. Давайте разберемся…

Если обычная волна просто "растекается" по всем 8 соседям клетки, то дискретная волна имеет более сложный алгоритм определения соседей. Это связано с тем, что район практически играет роль 3-ей координаты. Т.е. говорить о дискретной клетке с координатами 100, 100 бессмысленно, так как не хватает еще номера района. Каждый район должен иметь в своем составе список доступных соседей.

Для примера рассмотрим ситуацию с желтой дискретной клеткой. Она состоит из 3-х районов, каждый из которых может соединяться с одним или несколькими районами других дискретных клеток.

Желтый 1: Красный 1
Желтый 2: Зеленый 1, Малиновый 1
Желтый 3: Зеленый 2, Малиновый 1, Голубой 1

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

Обратите внимание еще на один маленький нюанс. Малиновый 1: Желтый 2, Желтый 3, Голубой 1, Голубой 2, Зеленый 2, … т.е. связь с желтой и голубой клетками происходит сразу по 2-м районам.

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

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

Примерная структура дискретной клетки:

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

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

Подготовьте дискретные клетки перед запуском карты. Возможно, вам понадобится 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. Достигнута ли цель? Достижение цели определяется по расстоянию от нашего юнита до цели. Всегда должно быть известно расстояние, которое является достаточным для достижения цели. Например, если юнит двигается к ресурсу, то расстояние будет 1, а если хочет подстрелить врага, то расстояние равно радиусу стрельбы.

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

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

Первым делом, проверяем "может цель уже достигнута?" Скорее всего "нет"…

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

Реально под целью может подразумеваться:

1. Пустое место.
2. Подвижный юнит.
3. Здание, ресурс или какой-нибудь камушек.
4. Непостроенное здание, т.е. реально его еще нет, но надо подвести к нему работника для строительства.

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

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

Пункт в) и г) тоже схожи, но здесь под целью уже подразумевается некая область - рамка вокруг цели. Как быть в этом случае? Очень просто - можно пустить вторую волну сразу из каждой клетки, которая входит в рамку. Т.е. для каждой клетки, которая входит в рамку, определяем дискретную клетку и район, а затем заносим их в массив волны 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 будет примерно полсекунды-секунда, далее все юниты спокойно направятся в указанное место уже без каких-либо притормаживаний.