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

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

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

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

Золотая руда, которая раньше не позволяла соединиться двум районам, была добыта, т. е. теперь эти 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 малиновой клетки дискретная волна должна будет проследовать в пять направлений сразу: два раза в желтую клетку, два раза в голубую и один раз в зеленую.

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

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

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

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

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

Маркер

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

Источник волны

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

Стоимость

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

Время создания

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

Важно!

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

Построение пути из дискретных клеток с помощью дискретной волны.
Объединение пути из дискретных клеток с помощью обычной волны.

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

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

Поле Маркер:

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

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

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

Начнем с того, что перед очередным шагом нужно всегда убеждаться в двух вещах:

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

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

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

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

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

Целью может являться:

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

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

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

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

Можно и не мудрить со второй волной, а просто нанести рамку в качестве цели и проверять одной волной на достижение этой цели.

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

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

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

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

Значит так: В вашего пехотинца попал снаряд от вышки. Что делать?

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

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

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

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

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

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

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

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

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

Путь из дискретных клеток строится заранее, т. е. пока юнит движется по нему, ситуация может сильно измениться, например, на пути движения может быть построено новое здание. Для отслеживания таких изменений юнит, перед тем как наступить на очередную дискретную клетку, должен определять, а не была ли обновлена на ней информация. Для этого каждая дискретная клетка должна иметь поле Время создания, в котором хранится время ее обновления (построения областей). А каждый юнит должен запоминать время, когда был построен дискретный путь. Если вдруг оказывается, что путь построен раньше, чем обновилось содержимое дискретной клетки, то юниту необходимо перестроить весь путь полностью.
Когда юнит шагает, то он постоянно сталкиваться с другими юнитами. Для начала надо определить, чем занят мешающий юнит. Если он движется или ожидает движения, то можно тоже подождать (из-за этого в стратегиях юниты часто вытягиваются в цепочку). Если ждать бессмысленно (юнит стоит или ждет нашего юнита), то можно построить связывающий путь еще раз.
Иногда плотность юнитов так велика, что не получается построить связующий путь к следующей дискретной клетке. Это самый сложный момент в управлении маршрутом, ведь в этой толчее, практически, невозможно определить: сто́ит ли чего-то ждать или надо пойти другим путем? Еще хуже то, что наш юнит может запросто сам создавать затор. Иногда ситуацию получается расхлебать, если «разогнать» юнитов в произвольных направлениях. Чтобы пойти другим путем можно заблокировать для дискретного волнового алгоритма ту дискретную клетку, на которую не получается попасть. В «Онимодах» я блокирую до трех таких клеток подряд, после чего строю весь дискретный путь с самого начала. Для блокировки дискретной клетки достаточно указать в ней, что волна ее уже посещала, тогда волна туда второй раз не пойдет (если, конечно, вы не используете такое понятие, как «стоимость клетки»).
Если целью является другой юнит, то он может постоянно перемещаться. Т. е. вам придется постоянно полностью перестраивать весь путь. Как же определить момент, когда нужно это сделать? Я делаю так: определяю примерное направление к целевому юниту (т. е. направо, налево, налево-вверх, направо-вверх, …) и, если оно меняется, то перестраиваю путь полностью. Таким образом, если целевой юнит находится далеко, то направление будет меняться редко, а если близко, то путь будет строиться быстро.
Желательно вести счет тактов, в течение которых, юнит не смог сдвинуться с места. Если этот счетчик начнет превышать какое-то число, то это будет сигналом к принятию экстренных мер, таких как построение обходного пути, перемещение в случайном направлении или прерывание выполнения команды.
Самое главное — используйте периодичность. Например, если юнит ждет, когда ему освободят дорогу, то совсем не обязательно осуществлять эту проверку постоянно. Это можно делать периодически, а это замедление реакции на треть секунды играющий даже не заметит. Проверки по периоду во всей игре — это как раз то, что позволяет проводить массу дорогостоящих по времени проверок и при этом сохранить высокую скорость.

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