Модуль поиска путей в игровом движке Владимир Олейник

КРИ 2006, Москва. © MiST land - South. Требования к модулю поиска путей Работа на больших картах (до 1000х1000 ячеек) Гибкая настройка типов препятствий, и учет типа юнитов при поиске пути Возможность динамического регулирования производительности модуля Поиск не должен занимать ощутимо длительное время

КРИ 2006, Москва. © MiST land - South. Алгоритмы поиска Волновой поиск. (Поиск в ширину) Поиск в глубину Алгоритм лучший - первый Алгоритм Дейкстры АStar

КРИ 2006, Москва. © MiST land - South. Иерархический поиск Проблемы в работе AStar на больших картах

КРИ 2006, Москва. © MiST land - South. Как строится макрограф

КРИ 2006, Москва. © MiST land - South. Как строится макрограф Создание списков соседей Веса макроузлов Стоимость переходов между макроузлами

КРИ 2006, Москва. © MiST land - South. Как перестраивается макрограф

КРИ 2006, Москва. © MiST land - South. Достоинства макрографа Сокращает количество рассматриваемых микроячеек Может сильно сократить худший случай при работе АStar (пути нет)

КРИ 2006, Москва. © MiST land - South. Недостатки макрографа Необходимо перестраивать макрограф при изменении препятствий (тяжелая операция) Оптимальный путь по макрографу не всегда является оптимальным по микрографу

КРИ 2006, Москва. © MiST land - South. Гибкая настройка типов препятствий и учет типа юнитов при поиске пути Классификация препятствий по способности перемещаться. Статические препятствия (вода, горы) Относительно редко меняющиеся (здания) Динамические (техника, солдаты)

КРИ 2006, Москва. © MiST land - South. Путь по макрографу существует, а по микрографу нет

КРИ 2006, Москва. © MiST land - South. Путь по макрографу существует, а по микрографу нет Пробуем искать путь через микроячейки соседних макроузлов Делаем несколько попыток переискать путь через некоторое время Решения:

КРИ 2006, Москва. © MiST land - South. Гибкая настройка типов препятствий и учет типа юнитов при поиске пути Классификация юнитов Наземные (танки, автомобили, пехота) Воздушные (вертолеты, самолеты)

КРИ 2006, Москва. © MiST land - South. Регулирование производительности модуля Получить наилучший узел Проверить всех его соседей (занести в Open List) Поместить узел в Closed List Типичная итерация AStar

КРИ 2006, Москва. © MiST land - South. Регулирование производительности модуля Распределение итераций для запросов может осуществляться разыми способами Линейное распределение (n = N / c) Прогрессивное Приоритетное ВАЖНО: В любом случае необходимо предусмотреть возможность досчёта поиска пути до конца.

КРИ 2006, Москва. © MiST land - South. Учет изменений карты препятствий В процессе распределенного по кадрам поиска пути карта препятствий может измениться Во время движения юнита по пути карта препятствий может измениться Решение: Обрабатываем оба случая на этапе коллизий

КРИ 2006, Москва. © MiST land - South. Поиск не должен занимать ощутимо длительное время Быстрый путь Полный путь. Оптимизированный путь

КРИ 2006, Москва. © MiST land - South. Описание возможностей дальнейшего развития, доработки и оптимизации модуля Различные размеры ячеек для разных юнитов (маленькие, средние, большие) Не хранить в памяти все микроячейки а создавать их по мере необходимости и кэшировать (используя например алгоритм кэширования LRU) Хранить вместо булевского значения (ячейка проходима \ непроходима) маску проходимости (для каких юнитов проходима ячейка). Это позволит объединить несколько слоев проходимости в один а также искать путь в зависимости от размера юнита. Для длинных путей можно использовать предварительно расчитанные пути

КРИ 2006, Москва. © MiST land - South. ?

Источники AI Game Programming Wisdom I, II, Edited by Steve Rabin DTF.RU