Вопросы с собеседования: поиск пути и навигация

Это четвертая часть вопросов. Все вопросы можно найти здесь.

(4a) Расскажите об алгоритме A*. Сравните его с другими алгоритмами, почему его обычно используют в играх с расчетами в реальном времени? В каких случаях у A* низкая производительность?

A* - алгоритм поиска на графе с эвристикой.
Алгоритм A* для новичков - простое и наглядное описание.
У него хорошая производительность, эвристику можно потюнить если чего.
Хуже всего отрабатывает тогда, когда пути для цели нет. Перебирает все возможные узлы графа и может сожрать много памяти.

(4b) Назовите как минимум 3 способа представить пространство поиска так, чтобы на нем можно было делать поиск пути. Каковы достоинства и недостатки каждого из этих подходов, когда какой из них вы будете использовать?

Можно разделить на клеточки: квадратные, шестиугольные. Плохо подходят для трехмерных миров. Занимают много памяти. Требуют дополнительной интерполяции пути юнитов, иначе юниты, которые ходят по клеточкам, будут выглядеть глупо. Но зато есть random access look-up.
Waypoints. Найденный путь не всегда оптимальный. Хорошо работает в трехмерных играх.
Navigation mesh. Нужно хранить большое количество полигонов, если мир сложный. Хорошо работают как на открытых пространствах, так и в закрытых. Можно генерировать автоматически. Но сложно.
Использование сильно зависит от задачи.
Все это подробно и с картинками изложено здесь: Pathfinding: Search Space Representations

(4c) Назовите все способы, какие знаете, для оптимизации поиска пути без потери качества найденного пути. Перечислите все дополнительные расходы (например, увеличившийся расход памяти) для каждой из этих оптимизаций.

Речь будет идти про А*, поскольку он самый популярный.
Оптимизировать можно двумя путями: пространство поиска и сам алгоритм. Сначала про пространство поиска:
Можно разделить пространство поиска на клеточки покрупнее, алгорим будет работать быстрее.
Есть HPA* (hierarchical pathfinding A*) - Иерархию двух пространств поиска. Грубо говорят - клеточки покрупнее, которые делятся на клеточки поменьше. Сначала ищем по крупным клеточкам, потом, когда путь найден, уточняем по мелким. Больше двух никто не делает - получается сложно, выигрыш маленький, не нужно это.
Оптимизация самого алгоритма:
Играем с эвристикой.
Если идет несколько поисков одновременно, можно запоминать промежуточные данные одного поиска и использовать их в другом.
Можно аллоцировать необходимую для алгоритма память заранее.

Также см. Game Parogramming Gems, глава A* Speed Optimizations

(4d) Ваша система поиска пути была написана с расчетом на солдата, и она хорошо работает для солдат. Посередине разработки дизайнеры решают добавить 3 новых типа юнитов: инопланетянина ростом 15 футов, который не пролезает через большУю часть дверей в игре, очень широкую машину на воздушной подушке, которая не пролезает в узкие коридоры и через маленькие двери, и солдата на мотоцикле, который довольно медленно поворачивает( например, 15 градусов в секунду на любой скорости). Какие изменения вы внесете в свой AI, чтобы они все заработали нормально?

(4e) У вас есть система поиска пути, которая отлично работает, но она не умеет работать с динамическими объектами (ящиками, бочками, машинами, другими юнитами). Игрок играет супергероем, который может использовать суперспособность "бросить автомат с газировкой на пути юнита". ИИ-юнит не может подвинуть или уничтожить этот автомат. Когда юнит видит, что автомат заблокировал его путь, какими способами он может найти способ обойти его, при этом придерживаясь своего начального направления движения и дойдя до цели? Что будет, если автомат сбросили на точку назначения? Что если автомат заблокировал дверь, через которую юнит должен пройти согласно своему предрассчитанному пути?

Ставим автомату вектор отталкивания, соответственно модифицируем вектор движения нашего юнита.
Если закрыло точку назначения - встаем до нее, чего делать.
Если заблокировало дверь - пересчитываем путь, когда в эту дверь упремся.
Подробнее здесь: Avoiding Dynamic Obstacles and Hazards

(4f) Вы работаете над игрой от первого лица, мир трехмерный. Поиск пути в игре использует навигационную сетку. Внезапно дизайнеры решают, что они хотят, чтобы юниты в игре могли использовать лестницы, чтобы взбираться на стены, спрыгивать с небольшой высоты, перепрыгивать через небольшие трещины и все это должно стать частью поиска пути. Расскажите, как вы реализуете такую системы, и как она будет связана с существующей навигационной сеткой. Также расскажите, какие утилиты вы предоставите дизайнерам (если предоставите).

(4h) Вы делаете шутер по мотивам Второй Мировой со сражениями на улицах Берлина. Дизайнер хочет, чтобы в определенные моменты игры нацисты, котролируемые компьютером, обходили игрока с флангов, т.е. чтобы небольшие отряды нацистов подходили с разных сторон, с боковых улиц и дворов. Допустим, жульничать нельзя (т.е. нельзя просто телепортировать юнитов туда, где они должны оказаться) и мы предполагаем, что дизайнеры не могут сделать это с помощью скрипта. Опишите как минимум 2 пути реализовать такую систему.

(4i) Ваш дизайнер поиграл в игру, где он видел отряд юнитов двигающихся по коридору таким образом, что только один их них двигался в каждый момент времени, а остальные его прикрывали (т.е. юнит из тыла всегда двигается вперед). Он впечатлен и он хочет такое же. Опишите пути реализации такой системы. Каким образом ИИ будет понимать, когда ему двигаться, когда остановиться, когда открывать заградительный огонь?