Каковы недостатки и / или ограничения навигационных сеток? [закрыто]

8

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

Конечно, это не совсем «волшебная» техника, которая представляет себя без каких-либо недостатков? Может ли кто-нибудь объяснить, какие существуют ограничения и недостатки использования навигационной сетки, скажем, на графике, состоящем из путевых точек? Или укажете мне правильное направление?

Рэй Дей
источник

Ответы:

8

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

Единственное практическое преимущество использования графиков путевых точек - это то, где вы действительно хотите ограничить движение точными линиями, а не областями. Графы путевых точек = бесконечно малые точки и линии, тогда как навигационные сетки - это почти то же самое, только с (выпуклыми) полигональными областями, которые описывают допустимое пространство, которое считается «территорией этой ячейки». В любом случае вы интерполируете положение объекта ИИ от одного узла к другому; единственная разница с навигационными сетками состоит в том, что вы делаете это из одного локуса точек в другой, тогда как с помощью графиков путевых точек вы делаете это из одной точки в другую и, возможно, уделяете должное внимание узлам, разделяющим ребра A и B. И, конечно, с точки зрения сложности, легко увидеть, что графики путевых точек умеренно дешевле в эксплуатации.

С течением времени улучшения приходят, казалось бы, «бесплатно» (с индивидуальной точки зрения). Вот почему компьютер, который вы покупаете сегодня за $ X, во много раз быстрее, чем компьютер, который вы могли купить десять лет назад за ту же цену. Дело в том, что это не совсем бесплатно - кто-то где-то вложил в это усилия НИОКР. То же самое с алгоритмами. И именно поэтому старые технологии в основном отстают.

инженер
источник
3
Ваш ответ в основном хороший, но мне бы очень хотелось увидеть цитату «даже на уровне нейронов животных, [поиск пути] представлен как своего рода график, связывающий идею одного места с идеей другого посредством ассоциации, и скоро." Это очень сильное утверждение, которого я раньше не слышал.
1
«Представимы» и «представлены» - это совсем не одно и то же. Связь между мышлением и структурой нейронов не является прямым отображением (очевидно, что нейроны, сигнализирующие о красном, сами по себе не являются красными). В любом случае, ваши правки - гораздо более прямое утверждение.
Спасибо за информативный ответ. Я понимаю, что все практические примеры поиска путей используют графики и предположили, что может быть проблема сложности времени / памяти. Тем не менее, мне было интересно, был ли крайний случай, когда вы не могли эффективно использовать навигационную сетку - задним числом, я думаю, я мог обдумать это. Вопрос об ограничениях навигационных сеток - это, скорее всего, вопрос об ограничениях графа как формы представления мира. Еще одна вещь, если бы вы могли сослаться на пример Collaborative Diffusion, я был бы очень признателен! Еще раз спасибо.
Рэй Дей
-1, потому что ты не ответил на вопрос. Вы сказали, что навигационные сетки - это качественное улучшение, но оригинальный постер хотел знать, что это были за качества.
Kylotan
@Kylotan: Нет, на самом деле, вопрос гласит: «У меня много материалов о навигационных сетках [и] их преимуществах».
0

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

Тузик
источник