Алгоритмы иерархического поиска пути в играх Андрей Плахов andrey.plakhov@nival.com. - презентация

1 Алгоритмы иерархического поиска пути в играх Андрей Плахов

2 Три метода поиска пути (По возрастанию сложности и эффективности) Эмпирический обход препятствий A* и распределенный А* Подробнее тут: Иерархический поиск пути Алгоритмы поиска пути Андрей Плахов

3 Стратегические правила Никогда не используйте сложный метод, если можно обойтись простым! Заставьте геймдизайнеров иногда думать о поиске пути! Алгоритмы поиска пути Андрей Плахов

4 Иерархический поиск пути Как ищут путь люди? Как использовать в играх похожие алгоритмы? Алгоритмы поиска пути Андрей Плахов

5 Иерархический поиск пути Вот что такое граф областей Алгоритмы поиска пути Андрей Плахов

6 Иерархический поиск пути Поиск происходит в 2 этапа Алгоритмы поиска пути Андрей Плахов

7 Иерархический поиск пути Что входит в систему иерархического поиска? Предварительное построение карты Создание графа областей Поиск в графе областей Окончательный поиск с ограничениями Пересчет областей, если карта изменилась Алгоритмы поиска пути Андрей Плахов

8 Граф областей Разобьем карту на «квадратики». Регулярное разбиение Сторона квадратика – степень двойки (4 или 8) Каждая область будет целиком входить в один из квадратиков Алгоритмы поиска пути Андрей Плахов

9 Граф областей Выделяем области Как это сделать за 2 прохода по карте? Первый проход: номер области определяется по ближайшим соседям На слайде номер отображается цветом. Внизу нарисована таблица соответствий Алгоритмы поиска пути Андрей Плахов

10 Граф областей Строим граф областей Как это сделать за 2 прохода по карте? Второй проход: области отождествляются Номер области определяется по таблице соответствий Алгоритмы поиска пути Андрей Плахов

11 Граф областей Разметка расстояний Выбор центра области: Ближайшая к центру тяжести точка области Таблица Т: расстояние от каждой точки области до ее центра. Один шаг стоит 2, по диагонали 3 Расстояние между областями: минимум по их общей границе Алгоритмы поиска пути Андрей Плахов

12 Граф областей Пересчет Пересчет должен быть локальным Смена персонажа вызывает такой же пересчет, как и разрушения Таблицу Т нужно сохранить для ускорения пересчетов Алгоритмы поиска пути Андрей Плахов

13 Граф областей. Объединение графов Этажи зданий Вложенные сетки, повернутые на угол, не кратный 90˚ Пещеры, точки телепортации,... Алгоритмы поиска пути Андрей Плахов

14 Двухуровневый поиск пути Поиск пути по графу областей. В итоге – список областей Поиск пути по детальной карте только среди точек, близких к центрам областей из списка Алгоритм А* не используется – здесь алгоритм Дийкстры оказывается быстрее. Алгоритмы поиска пути Андрей Плахов

15 Алгоритм Дийкстры Напоминаем: Поиск пути основан на очереди с приоритетами На каждом шаге обрабатывается первый узел в очереди. Его необработанные соседи попадают в очередь с приоритетом, равным суммарной стоимости пути до них В итоге для каждой обработанной позиции в хэш- таблицу или 2d-массив попадает ее предок и стоимость пути до нее Алгоритмы поиска пути Андрей Плахов

16 Быстрый алгоритм Дийкстры Эмпирическое отбрасывание ложных смен поз Стоимость хода – целое число, меньшее N. Для скорости полезно N – степень двойки. Очередь с приоритетами моделируется при помощи N массивов фиксированной длины. Скажем «Нет» операциям с памятью! Будьте осторожнее с STL, обращайте внимание на неявное выделение памяти Алгоритмы поиска пути Андрей Плахов

17 Быстрый алгоритм Дийкстры Очередь с приоритетами как N массивов После N-того массива опять следует первый Каждый массив свернут в кольцо Алгоритмы поиска пути Андрей Плахов Пусть обрабатывается массив с номером Х. В массиве с номером (X+С) mod N находятся все ждущие обработки позиции стоимостью на С больше текущей.

18 Быстрый алгоритм Дийкстры На С++ полезно писать такой алгоритм как template Cпециализаторы: тип «позиция»; таблица, хранящая информацию о стоимости и позиции- предке; число N Алгоритмы поиска пути Андрей Плахов Красный крест: позиция обработана Выделенная стрелкой позиция обрабратывается Позиции с рамкой будут добавлены на текущем шаге

19 Способы оптимизации метода Кэшируйте результаты Запоминайте расстояние в графе областей от начальной области до остальных. 90% вызовов поиска пути начинаются с той же области, что и предыдущий вызов Используйте предварительные вычисления: считайте, пока есть время Не используйте отложенные вычисления Алгоритмы поиска пути Андрей Плахов

20 Вот о чем мы поговорили: Три способа организации поиска путей: какой использовать? Иерархический поиск пути: построение и перерасчет графа областей Двухуровневый иерархический поиск Быстрый алгоритм Дийкстры Как оптимизировать эти методы? Алгоритмы поиска пути Андрей Плахов

21 Алгоритмы поиска пути Андрей Плахов