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

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

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

Изменено: 07.09.2006

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

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

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


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



Страницы: 1 2

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

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

Подготовка

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

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

Если район точки А = району точки Б, то путь строить можно, иначе Б достичь нельзя. Кстати, невозможность достичь точки Б не означает, что к ней не нужно двигаться, но об этом речь пойдет позже.
Разделить игровое поле на районы очень просто. Для этого достаточно для каждой клетки поля завести еще одну переменную, в которой и будет храниться номер района. Далее нужно во всех клетках проинициализировать район числом 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) из-за какого либо препятствия.

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

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

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

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

Волновой алгоритм и как победить его неэффективность

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

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

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

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

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

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