Роман Будкеев
В 2004-2005 самостоятельно разрабатывал проект "Война культур", который был выставлен на Ярмарке проектов КРИ-2005. С 2005 по январь 2007 года - главный программист в Киевской компании Bird's Eye View Games.
Вступление
Поиск пути - обязательная часть любой игры жанра RTS (другие жанры в рамках этой статьи нам неинтересны). Для некоторых игр подходят простые алгоритмы, но для моего проекта мне понадобился поиск пути, похожий на тот, что WarCraft 3. Не имея сведений об алгоритме обхода препятствий, мне пришлось разрабатывать и реализовывать его самому, и в итоге он оправдал все надежды. Эта статья содержит описание алгоритма и его реализации, ошибки, с которыми я столкнулся. К статье прилагается готовая реализация этого алгоритма с закрытым кодом (DLL) для свободного использования в любых целях и утилита для тестирования алгоритма.
Определения
Для удобства все выведенные определения вынесены в начало статьи:
- Старт - точка начала пути.
- Финиш - точка конца пути.
- Решение - точка (кроме старта и финиша), гарантированно входящая в путь, или ее отсутствие, если на пути нет препятствий.
- Карта проходимости - карта/массив, хранящий уровень проходимости участков игровой карты. В самом простом случае - карта, хранящая бинарный лабиринт.
- Опорная точка - центр объекта; точка местонахождения объекта.
- Левая/правая рука - "человек", двигающийся в лабиринте, держась за стену левой/правой рукой.
- Техника - живые или механические большие юниты. Катапульты, слоны и т.п.
Когда у меня возникла необходимость написать алгоритм поиска путей, я не искал готовых решений в Интернете из-за отсутствия возможности ими воспользоваться. Пришлось разрабатывать все самому. В дальнейшем, уже после разработки и реализации алгоритма, я изучал вопрос глубже. В русскоязычном Интернете мне не удалось найти описание такого алгоритма - встречались похожие, но более простые, не отвечающие нужным требованиям.
Из различных стратегий наиболее похожим на желаемый поиск пути был в игре WarCraft 3. В дальнейшем я буду сравнивать свой pathfinding с поиском пути из этой игры.
После анализа желаемого поведения юнитов в игре были выведены требования к поиску путей:
- Высокая скорость расчета: многотысячные армии; сотни солдат должны рассчитывать себе путь каждую секунду;
- Большие пространства: большая игровая карта, преодолеваемая солдатом за большое время;
- Движение в любом направлении, остановка в любом месте: отсутствие видимых ячеек карты, свободное движение солдат. Солдат может находиться в любом месте ячейки;
- Погрешность: допустима погрешность в найденном пути, но она не должна быть значительной;
- Прямые пути: рассчитанный путь представляет собой ломаную линию;
- Солдат безразмерный: солдат занимает минимальный размер - 1 ячейку;
- Поиск пути для техники: алгоритм, аналогичный поиску пути для солдат. Техника, в отличие от солдата, имеет определенный размер;
- Разные уровни проходимости: пехота может проходить сквозь пехоту и мелкую растительность. Техника движется только сквозь мелкую растительность. Амфибии рассчитывают путь, как по земле, так и по воде;
- Достаточное расстояние до цели: расстояние до финиша, которое преодолевать необязательно. Рабочему, идущему строить здание, не нужно доходить до здания (до опорной точки, центра здания) расстояние равное радиусу здания;
- Случаи невозможных путей: в случае невозможности рассчитать путь к финишу найти ближайшую доступную точку к финишу;
- Один слой проходимости: юниты не могут двигаться один над другим (не считая летающих юнитов). Если можно двигаться по мосту, значит нельзя под мостом.
- Динамическая перестройка пространства: карта проходимости может существенно изменяться каждый такт игры.
Простой поиск пути (слева) и сложный поиск пути (справа)
Недостатки различных алгоритмов для данных требований
Волновой алгоритм и его модификации
- Большое время расчета;
- Ограниченное количество направлений движения.
- Недостаточно быстрое время расчета;
- Большой объем памяти для хранения списков.
- Низкая скорость расчета пути для большого числа юнитов разных размеров и огромной карты проходимости;
- Постоянно изменяющаяся карта проходимости требует регулярного пересчета графа.
- Перерасчет графа при изменении карты проходимости.
Наилучшим алгоритмом, удовлетворяющим всем условиям, оказался обход препятствий по контуру. В большинстве случаев обход препятствий исследует значительно меньшее пространство, и при этом гарантированно находит путь, если он существует. Для такого алгоритма не важно как часто и интенсивно меняется карта проходимости. Так же не имеет значения размер юнита. Этот алгоритм не универсальный и имеет ряд ограничений, но для множества игр жанра RTS он подходит очень хорошо. Его можно использовать как сам по себе, так и в сочетании с другими алгоритмами поиска пути.
Общая идея. Алгоритм
Общая идея алгоритма
Задать отрезок между стартом и финишем - это лучшее возможное решение. Найти на этом отрезке первый вход в препятствие. По правилу обхода лабиринта, если, входя в лабиринт, держаться рукой за стенку и не отпускать ее, то обязательно найдешь выход. Здесь правило похожее - если держаться рукой за стенку, то обязательно вернешься в точку, откуда начал обход препятствия. Обход может быть двух типов: обход препятствия, движение внутри замкнутого пространства вдоль стены. Во втором случае решения нет - точка финиша недоступна. В первом случае есть два варианта: во время обхода препятствия было обнаружено место выхода отрезка из препятствия, и точки выхода обнаружено не было. Если точки не было, значит, финиш находится внутри препятствия, а попасть туда невозможно - решения нет. Если точка была обнаружена, значит продолжить поиск, обходя следующее препятствие. Обходить каждое препятствие следует с двух сторон.
Все препятствия преодолены. Точка решения найдена.
Обойдя по контуру все препятствия на пути, можно уверенно сказать, что среди всего маршрута обхода присутствует одно место, которое точно входит в самый кратчайший путь - это было бы лучшим решением. Все остальные места обхода так же могут считаться решениями пути, но не лучшими. Теперь нужно найти это лучшее решение, что непросто. Будем считать, что лучшее решение - это точка обхода, наиболее далеко лежащая от заданного отрезка. Но бывают случаи, когда эта точка далека от лучшего решения. В моей реализации лучшее решение ищется только в обходе руки, первой пришедшей к финишу, и всех обходов ее предков (см. реализацию). Найденная точка считается решением пути и делит путь на 2 части. Далее для каждой части пути нужно снова рекурсивно выполнить поиск.
Если после обхода не удалось найти выход из последнего препятствия, значит, решения нет, и построить путь к финишу невозможно. В таком случае следует найти точку обхода, наиболее близко расположенную к финишу. Далее нужно выполнить поиск пути к этой точке.
Руки встретились; Найдена ближайшая точка (слева)
Движение внутри замкнутого пространства (справа)
Алгоритм поиска пути
- Задать точки старта и финиша, скорость движения юнита и его уровень проходимости, достаточное расстояние до финиша;
- Если юнит заперт со всех сторон и не может двигаться ни в одном направлении, то нет ни одного решения. Поиск окончен;
- Если скорость движения юнита высокая, то делить ее пополам до тех пор, пока она не будет превышать установленный предел. Это необходимо для того, чтобы, имея высокую скорость движения, юнит не перескакивал через небольшие препятствия;
- Провести условный отрезок из старта в финиш. Этот отрезок может быть самым коротким путем;
- Трассировать луч по этому отрезку, проверяя через каждый шаг юнита, не наступил ли он на непроходимую область. Если вступил в непроходимую зону, то точку входа в препятствие запомнить, и продолжить трассирование. Так же запомнить точку выхода из препятствия. Последнего выхода из препятствия может не быть, если финиш находится внутри него;
- Запомнить все точки входов в препятствия и выходов из них. Запомнить значения карты проходимости в точках выхода, а в эти ячейки записать индексы точек выхода;
- Если точек входа нет, значит, на пути нет препятствий. Путь между точками прямой. Поиск окончен;
- В первой точке входа создать левую и правую руку. Обнулить счетчик шагов;
- Провести условные оси точки финиша: вертикаль и горизонталь;
- Лучшим решением не считать никакое (ни одного кандидата на лучшее решение еще нет, поиск не начался);
- Все руки двигаются по периметру своего препятствия на один шаг. Левые руки двигаются против часовой стрелки, правые - по часовой;
- Если какая-либо рука наступила на ось (см. пункт 9) или повернула, встретив препятствие спереди, то считать эту точку кандидатом на ближайшую к финишу точку. Если этот кандидат находится на достаточном расстоянии к точке финиша, то дальнейших кандидатов игнорировать;
- Если какая-либо рука повернула из-за того, что отпустила стену, то считать эту точку кандидатом на лучшее решение;
- Если встретились две любые разные руки (левая с правой), уничтожить обе руки. Если не осталось ни одной руки, то перейти к пункту 19;
- Если какая-либо рука наступила на точку выхода, где еще никакая другая рука не была (точки выхода изначально имеют индекс, а после посещения рукой, точка выхода помечается специальным образом, запоминая, левая или правая рука туда пришла), то перейти к пункту 17. Если рука пришла в точку выхода, где уже побывала другая рука, то, если тут побывала такая же рука, продолжить обход этой руки, иначе уничтожить руку (далее будет описано, зачем необходимо такое усложнение). Если не осталось ни одной руки, то перейти к пункту 19;
- Увеличить счетчик шагов. Если счетчик шагов превысил допустимое количество, то перейти к пункту 20, иначе перейти к пункту 11;
- Уничтожить руку. Пометить точку выхода, куда пришла рука, специальным образом в зависимости от того, левая или правая рука туда пришла. Если это последняя точка выхода, и далее нет точки входа - прекратить обход и перейти к пункту 18. Иначе в следующей точке входа создать правую и левую руку и перейти к пункту 11;
- Путь к финишу есть. Отследить родительскую историю руки, которая пришла к последней точке выхода (родитель руки - рука, в результате обхода которой была создана данная рука). Среди всех кандидатов на лучшее решение этой руки и всех ее предков выбрать лучшее решение (для каждой руки достаточно хранить в памяти одного, лучшего кандидата). Лучшим решением считается точка, наиболее далеко лежащая от точек старта и финиша. Поиск окончен;
- Пути к финишу нет. Среди всех кандидатов на ближайшую точку к финишу выбрать лучшего - самого ближнего (это лучше делать по мере обнаружения новых кандидатов). Поиск окончен;
- Время на поиск пути вышло. Решением считать лучшего кандидата на ближайшую точку к финишу. Поиск окончен.
- Точка старта заперта со всех сторон. Решения нет;
- Препятствий нет, путь прямой;
- Путь к финишу есть. Решение - точка, гарантированно входящая в путь. Отрезок разбит на 2 отрезка. Для каждого отрезка следует снова выполнить поиск пути, если это необходимо;
- Пути к финишу нет. Решение - ближайшая к финишу доступная точка. Для полученного отрезка нужно снова выполнить поиск пути;
- Время на поиск пути вышло. Возможно, лучшее решение еще не найдено. Лучшим решением объявляется ближайшая к финишу доступная точка среди всех проверенных. Если необходимо, можно повторить поиск с большим временем поиска;
- Вылет с ошибкой;
- Зависание.
Реализация. Особенности реализации
Существует две системы координат: игровая и путевая. Игровая - это система координат и размеров, принятая в игре. Путевая - система координат для карты проходимости. При инициализации карты проходимости следует указать границы игрового пространства и размер карты проходимости. Независимо от размера, карта проходимости будет накрывать полностью все указанное игровое пространство. Также нужно указать максимальное время поиска пути.
Важно, чтобы размеры мира были пропорциональны размерам массива. Для преобразования координат из одной системы в другую доступны специальные функции. После инициализации создается однобайтовый массив указанного размера. Доступ к нему можно получить напрямую, а можно заполнять его через функции. После окончания работы приложения, карту нужно выгрузить.
Вся техника представляется в форме квадратов. Расчет круглых форм был бы значительно дороже. Прямоугольные формы не подходят из-за того, что юнит может поворачиваться, а поворачивать вслед за ним прямоугольник невозможно.
Размер техники должен быть строго по размеру ячеек карты проходимости. Для преобразования свободного размера, в ближайший допустимый размер предоставлена специальная функция.
Масштаб
Размер карты проходимости следует тщательно подбирать. Слишком большая карта займет много памяти, а расчеты путей на ней будут долгими. Слишком малая карта даст эффект ячеек - визуально юнит будет занимать меньше места, чем на карте проходимости или визуально юнит будет вылезать за пределы своей зоны на карте проходимости.
Размеры юнитов в WarCraft 3
К примеру, в WarCraft 3 максимальный размер карты - 256 на 256 ячеек карты. Каждая такая ячейка содержит 4 на 4 ячейки карты проходимости. Т.е. максимальный размер карты проходимости - 1024 на 1024. Размер мелкого юнита - 2 на 2, размер героя или крупного юнита - 3 на 3.
Уровни проходимости. Пример уровней проходимости
Всего предусмотрено до 16 уровней проходимости. Их назначение может быть любое. Вот мой пример уровней проходимости:
0. склон/техника/строения/стены;
1. вода;
2. легкие заборы;
3. пехота;
4. средние объекты и крупная растительность;
5. малый склон;
6. мелкие объекты и малая растительность;
7. пусто.
Здания можно строить на уровнях 5-7.
Солдаты бегают по уровням 3-7.
Техника передвигается по уровням 2-7.
Амфибии преодолевают уровни 1-7.
Оптимизация. Кэширование
После реализации, тестирования и исправления всех обнаруженных ошибок, была проведена работа над оптимизацией. Среди разных алгоритмических ухищрений основной оптимизационной частью стало добавление кэширования. Каждый расчет пути и его решение запоминаются. Если в следующий раз нужно будет рассчитать такой же путь, или очень похожий на этот, то вместо расчета пути заново будет выдано решение, найденное в прошлый раз. Для разных ситуаций это дает разный прирост скорости. Каждый раз после изменения карты проходимости кэш следует очищать, так как некоторые хранящиеся там решения станут ошибочными. Оптимально очищать кэш один раз за один шаг игры. Кэширование не работает для коротких путей.
Выявление ошибок
На определенном этапе была разработана утилита для тестирования алгоритма. С помощью нее было обнаружено много ошибок, которые встречались и не встречались ранее. Все ошибки были устранены. Теперь для выявления ошибок, которые могут случайно встречаться в игре, доступен режим логгирования (по умолчанию выключен). В этом режиме все вызовы функций, изменяющих карту проходимости, и вызовы функций поиска пути сохраняются в указанный файл. После любого ручного изменения карты проходимости следует вызвать функцию, сохраняющую в файл всю карту. В случае возникновения ошибки в поиске пути, этот файл можно просмотреть в утилите.
Также этот файл можно использовать для анализа карты проходимости в игре и определения различных значений: средняя длина пути, среднее время расчета пути, эффективность кэширования и т.д.
Ошибки и их решения
Основным типом ошибок были проблемы с числами типа float и округлением. Вылавливать такие ошибки было очень тяжело.
Другие основные ошибки:
- Точки выхода из препятствий не были расставлены по карте проходимости. При создании рука запоминала точку, куда она должна прийти. Это вызывало ошибки для путей, где рука приходит не в следующий выход (например, если на пути кольцо). Решением стало расставление точек выходов на карте проходимостей с индексацией их;
Рука, созданная во входе 0, приходит в выход 1 - Отсутствие параметра step, определяющего шаг трассировки отрезка от старта к финишу. При разном шаге путь может встретить или не встретить препятствие, например, наскочив на уголок препятствия. Таким образом, юнит рассчитывал для себя путь с фиксированным шагом, и мог пропустить микропрепятствия, с которыми потом сталкивался при движении;
При разном шаге юнит наступает на разные препятствия - "Использованные" точки выхода помечались как "точка выхода, куда пришла рука". Таким образом, другая рука, пришедшая в эту точку, уничтожалась независимо от того, какая она. В редких местах это вызывало ошибку, когда вновь созданная рука почти сразу наступала на такую точку выхода и уничтожалась (см. рисунок). Для решения этой проблемы "использованные" точки выхода стали помечаться в зависимости от руки, которая туда пришла (например, "точка выхода, куда пришла правая рука"). В зависимости от того, как помечена точка выхода, она уничтожала лишь определенные руки;
Левая рука, сделав один шаг, наступает на точку выхода
и уничтожается; неудачное решение нашла правая рука - Одной из целей был поиск путей для танков сквозь вражескую пехоту, но при этом свою пехоту они должны объезжать. Так же за свою пехоту должна считаться пехота союзников. Решение этой задачи существенно повышало объем вычислений за счет постоянной проверки, является ли солдат в данной ячейке своим или вражеским. От такого решения пришлось отказаться, так как оно нарушало требование №1;
- Размер техники был свободным (например, 2.5х2.5). Таким образом, в зависимости от положения юнита, он мог занимать разное количество ячеек. Это вызывало массу ошибок с типом float и округлением: прохождение рук мимо друг друга, отрыв руки от стены и т.п. От произвольного размера пришлось отказаться. Теперь размер юнита следует нормировать до допустимого.
Утилита поиска путей. Wouw PathFind v1.3
Утилита была разработана для отлаживания алгоритма. Теперь она служит для демонстрации работы алгоритма и замеров времени расчета путей.
Карта пути загружается из файла map.bmp и отображается в правой части утилиты. Там же показываются построенные пути. Левой кнопкой мыши задается точка старта, правой - точка финиша. Уровень красного цвета на карте проходимости определяет уровень проходимости (см. требование №8).
В левой панели:
- Вид пути - выбор алгоритма поиска пути: для пехоты, для техники и для танков (в.т. автомобилей т.п.). Третий режим не закончен и работает так же как второй;
- Параметры - набор параметров юнита, требуемых для вычисления пути;
- Тест на скорость - набор режимов теста на скорость. Случайные пути - точка старта и точка финиша задаются случайным образом на карте. Они могут быть и на препятствиях. Похожие пути - пути, где точка старта и точка финиша задаются случайным образом неподалеку от заданной точки старта и финиша. Этот режим похож на ситуацию, когда требуется рассчитать путь для сгруппированного отряда. Если "Случайные пути" или "Похожие пути" не включены, то тест будет проводиться для указанного пути. Кэширование - включает режим кэширования. Кнопка "Запустить тест" запускает тест с указанным режимом. "Запустить все тесты" - проводит тесты со всеми возможными режимами. По результатам каждого теста выводит среднее время расчета одного пути для каждого вида пути (пехота, техника, танки) и эффективность кэширования;
- Загрузить карту - открывает диалог загрузки карты проходимости из файла;
- Глубина просчета пути - глубина рекурсии, с которой выполняется поиск пути. При значении 0 ищет решение заданного пути, при значении 1 ищет решение каждого полученного отрезка и т.д;
- Уровень проходимости - параметр, определяющий уровень проходимости юнита, для которого делается поиск пути (см. требование №8);
- Визуальный поиск пути - включает режим визуализации процесса работы алгоритма. Обход препятствий показывается белыми линиями. Важно: после работы "визуального поиска пути" значение глубины устанавливается на 0 автоматически;
- Окно отчета содержит координаты точек пути, эффективность кэширования, результаты тестов. Если кликнуть на координаты точки, то старт переместится в эту точку, с нажатым ctrl переместится финиш;
- Сохранить путь - сохранить параметры поиска пути в файл;
- Загрузить путь - загрузить параметры поиска пути из файла и построить путь.
Библиотека поиска путей. WouwPathFind.dll
В комплект идут файлы:
- WouwPathFind.dll - библиотека поиска путей;
- WayMap.h - заголовочный файл для C++;
- WayMap.pas - заголовочный файл для Delphi;
- Readme.txt - описание типов, функций и их параметров.
- Различные дополнительные оптимизации;
- Функционирование третьего типа пути (танки) на основе алгоритма А* с использованием предварительного поиска пути типа "техника";
- Поиск пути для танков через вражескую пехоту;
- Два режима поиска пути: обычный и поиск пути сквозь динамически объекты. До тех пор, пока юнит движется, он ищет путь сквозь динамические объекты. Это даст возможность юнитам двигаться друг за другом, не пытаясь рассчитать путь в объезд впереди движущегося юнита. Если юнит упирается в другой динамический юнит, то дальнейший путь он себе просчитывает в объезд всех препятствий (обычный поиск пути). Такой или похожий механизм использован в WarCraft 3;
- Несколько слоев проходимости;
- Что-нибудь еще...
Оригинал:
http://dtf.ru/articles/read.php?id=46788
http://dtf.ru/articles/read.php?id=46788&page=2
