Модуль поиска путей в игровом движке Владимир Олейник loki@mistgames.ru. - презентация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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