Нахождение пути: Раз и навсегда (pathfinding)

[DeusModus]

материал является вольным переводом статьи от PaulT

Насколько мне известно, большинство игр используют совокупность связанных путевых точек(waypoint graphs) для нахождения пути. И по-моему мнению такой подход устарел. Ниже я изложу ограничения данного подхода.

Было время, когда подобный способ был актуален. Где-то в 80-х, 90-х разработчики сталкивались с серьезными аппаратными ограничениями и им приходилось срезать углы. Но теперь вокруг нас многомиллиардная индустрия. Нашими целевыми платформами являются многоядерные монстры с постоянно растущими объемами памяти и настал момент, когда мы можем позволить себе реализовать нахождение пути правильно.
Есть поговорка среди программистов, занимающихся Искусственным Интеллектом: "Поиск пути реализован". У нас имеется множество подходов к каждой проблеме. Мы просто не всегда их используем.

Нет причины по которой нахождение пути не может присутствовать в каждой игре.

Почему путевые точки не предназначены для нахождения пути

Давайте я покажу, как выглядит типичная совокупность связанных путевых точек. Вот небольшой кусочек города Штормград из World of Warcraft:

Рисунок 1. Часть Штормграда в World of Warcraft.

Вот так примерно выглядит совокупность связанных путевых точек в этой области.

Рисунок 2. Часть Штормграда в World of Warcraft с примерным построением waypoint graphs.

Есть и другой способ, включающий использование выпуклых многоугольников(convex polygons) для описания мест, в которых подконтрольные искусственному интеллекту объекты могут передвигаться.
Вот так примерно выглядит навигационная сетка(navigation mesh):

Рисунок 3. Часть Штормграда в World of Warcraft с примерным построением navigation mesh.

Есть пять причин, почему путевых точек оказывается недостаточно для корректного нахождения пути.

1. Некоторые игры требуют нелепого количества путевых точек.

Для огромных открытых зон обычно требуются тонны путевых точек, щедро усыпанных по всему игровому миру для достижения адекватного передвижения.
С другой стороны, для таких зон навигационной сетке требуются лишь пара больших полигонов, найти пути через которые гораздо быстрее.

Пример.

На рисунке снизу изображен город Halaa из игры World of Warcraft. Он довольно большой, в основном состоящий из открытого пространства по которому необходимо перемещаться неигровым персонажам.

Рисунок 4. Город Халаа из World Of Warcraft, видел сверху (слегка измененный)

С системой на основе путевых точек нам необходимо много точек для достижения полного охвата зоны. Но даже количества точек как на картинке снизу будет недостаточно для передвижения неигровых персонажай без зигзагов.

Рисунок 5. Город Халаа с совокупность. путевых точек.

Однако, используя навигационную сетку мы можем описать этот район горсткой выпуклых полигонов:

Рисунок 6. Город Халаа с навигационной сеткой.

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

2. Они заставляют персонажей ходить зигзагами.

Совокупность связанных путевых точек принуждает персонажей придерживаться графов. Это означает, что персонажи адекватно движутся по рельсам, но почти никогда не находят оптимального пути из точки А в точку Б, потому что самый прямой путь почти никогда не соответствует графу.
Это вызывает неестественные артефакты при поиске пути, в частности персонажи ходят зигзагами справа налево.

Пример. Скажем, мы хотим чтобы персонаж переместился из точки А в точку Б.

Рисунок 7. Две точки в Халаа.

Вот так будет выглядеть путь при использовании совокупности связанных точек, которые я привел ранее.

Рисунок 8. Навигация из точки А в точку Б с использованием waypoint graphs.

Как видите, искусственный интеллект будет много раз поворачивать, как будто он едет по железной дороге.
В идеале, после того как мы создали путь, мы должны как-то уровнять его чтобы добиться плавности, возможно путём создания сплайна Катмулла-Рома вдоль пути.
Проблема состоит в том, что сеть путевых точек не имеет никакакой информации о том, что творится вне сети и это делает невозможным сглаживание и выравнивание пути.
Как можно создать сплайн, если сплайн будет находится вне совокупности связанных путевых точек и передвижение по кривой может стать причиной падения с моста?

Рисунок 9. Навигация из точки А в точку Б с использованием navigation mesh.

Так как мы располагаем информацией о безопасных для персонажа местах, мы можем сгладить путь как угодно, пока путь находится внутри навигационной сетки.

("Да," слышу я, "но я могу просто добавить больше соединений между путевыми точками и здоровски сгладить путь! Я соединю все возможные узлы в городе так, чтобы персонаж мог ходить между ними по прямой линии."
"Но это произведет экспотенциальный взрыв", отвечу я... "Вы говорите о сорока или пятидесяти дополнительных соединениях в этом простом примере. Количество соединений, которое вы хотите установить между всеми узлами приблезительно равно O(N^2), а ведь мы говорим о облостях больших размеров"
"Ну ладно," слышу я, "в таком случае я просто помечу каждую область между любым набором из трёх взаимно прилегающих точек как "открыто" и разрешу искусственному интеллекту ходить внутри этой области."
"Это делается полигонами.. и вы только что придумали навигационную сетку", отвечу я).

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

Возвращаясь к примеру со Штормградом, вот путь построенный по путевым точкам(красная линия) и сглаженный путь внутри навигационной сетки(синяя линия).

Рисунок 10. Движение по путевым точкам(красный цвет) и путь по навигационной сетке(синий цвет).

продолжение следует...