Как работает поиск путей в Navigation Mesh?

27

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

algorithm path-finding Пожар
источник
Это обнаружилось в ходе моих утренних странствий по Интернету: aigamedev.com/open/reviews/alienswarm-node-graph Возможно, стоит прочитать :-)
coderanger
Этот учебник может быть полезен для пользователей Unity, которые сталкиваются с этим сообщением: binpress.com/tutorial/unity3d-ai-navmesh-navigation/119
MichaelHouse

Ответы:

6

Это то же самое, что и нахождение путевых точек, только вместо путевых точек у вас есть путевые полигоны, и из него вы можете сделать несколько выводов о навиме:

  • путевые полигоны - это области, в которых сущности могут безопасно ходить
    • другие области, вероятно, не должны рассматриваться
    • путевые точки должны совершить прыжок веры в пространство между ними; помните NPC, застрявшие в стенах? Это было в местах, где две путевые точки не были напрямую связаны.
  • Потенциально меньше узлов (потому что многоугольники больше)
    • Поэтому скорее всего быстрее
    • Поэтому у него потенциально меньшие требования к памяти
  • Это более реалистично (потому что область многоугольника содержит в теории бесконечное количество точек)
    • На полигонах Вы можете сделать несколько стайных действий, чтобы избежать столкновений между NPC.
user712092
источник
2

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

coderanger
источник
Разве это не график путевых точек, кроме как на упрощенной сетке? Я думал, что навигационные сетки позволяют вам создавать пути на полигоне.
Пожар
Упрощенный график позволяет вам прокладывать пути на большие расстояния, а на короткие расстояния обычно обрабатываются другим способом. Похоже, что система Valve использует данные сетки для обоих, просто по-разному (маршрутизация суперузла против локальных ограничений).
Coderanger
Простой набор соединений - это не навигационная система? Я думал, что это называется navmesh, потому что вы делаете путь на полигонах.
Огонь
Я не думаю, что здесь важна локальная или глобальная навигация.
Огонь
1
Множество соседних полигонов по-прежнему является графиком, как и заданные путевые точки, и вы можете сделать A * для него таким же образом. Разница лишь в том, что когда вы знаете, через какие полигоны вы будете двигаться, вы по-разному рисуете линии.
Coderanger
0

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


источник