¿Cuáles son las desventajas y / o limitaciones de las mallas de navegación? [cerrado]

8

Tengo muchos materiales sobre mallas de navegación, cuáles son, sus ventajas sobre los gráficos compuestos por waypoints, etc. Sin embargo, no he visto mucha información sobre las limitaciones y las desventajas de usar mallas de navegación, aparte del tiempo obvio toman para ser creados manualmente (lo cual es relativamente resuelto por Recast).

¿Seguramente esta no es una técnica completamente "mágica" que se presenta sin inconvenientes? ¿Podría alguien explicar cuáles son las limitaciones y desventajas de usar una malla de navegación sobre, por ejemplo, un gráfico compuesto por puntos de referencia? ¿O señalarme en la dirección correcta?

Ray Dey
fuente

Respuestas:

8

Las mallas de navegación son una mejora cualitativa sobre los gráficos de puntos de referencia, de la misma manera que A * es una progresión natural sobre el algoritmo de Dijkstra. En cada caso, el primero ha evolucionado debido a las deficiencias del segundo, y es un algoritmo completamente más útil para la mayoría de las aplicaciones. La deficiencia es, por supuesto, la complejidad (tiempo y / o espacio). Pero debería decir que la compensación es pequeña para las mallas de navegación frente a los gráficos de puntos de referencia (es decir, la complejidad computacional puede aumentar, pero no en un orden de magnitud).

El único beneficio práctico de usar gráficos de puntos de referencia es donde realmente desea restringir el movimiento a líneas exactas en lugar de áreas. Gráficos de puntos de referencia = puntos y líneas infinitesimales, mientras que las mallas de navegación son casi lo mismo solo con áreas poligonales (convexas) adjuntas que describen un espacio válido considerado como "el territorio de esta celda". De cualquier manera, está interpolando la posición de una entidad AI de un nodo a otro; la única diferencia con navmeshes es que lo está haciendo de un lugar geométrico de puntos a otro, mientras que con los gráficos de puntos de ruta lo está haciendo de un punto a otro, y potencialmente teniendo en cuenta los nodos de separación de bordes A y B. Y, por supuesto, Desde una perspectiva de complejidad, es fácil ver que los gráficos de puntos de referencia son moderadamente más baratos de operar.

A medida que pasa el tiempo, las mejoras aparecen "gratis" (desde la perspectiva individual). Es por eso que una computadora que compra hoy por $ X es muchas veces más rápida que una computadora que podía comprar hace diez años por el mismo precio. El punto es que no es realmente gratis: alguien, en algún lugar, ha puesto el esfuerzo de I + D en eso. Lo mismo con los algoritmos. Y es por eso que la tecnología antigua se queda en el camino.

Ingeniero
fuente
3
Su respuesta es en su mayoría buena, pero realmente me gustaría ver una cita para "incluso a nivel de neurona animal, [pathfinding] se representa como una especie de gráfico que vincula la idea de un lugar con la idea de otro a través de la asociación, y pronto." Es una afirmación muy fuerte que no he escuchado antes.
1
"Son representables" y "están representados" no son lo mismo. La relación entre el pensamiento y la estructura neuronal no es un mapeo directo (obviamente, las neuronas que señalan rojo no son en sí mismas rojas). De todos modos, su edición es un reclamo mucho más directo.
Gracias por la respuesta informativa. Me doy cuenta de que todos los ejemplos prácticos de búsqueda de rutas utilizan gráficos y supuse que puede haber un problema de complejidad de tiempo / memoria. Sin embargo, me preguntaba si había un caso extremo en el que no se podía utilizar una malla de navegación de manera efectiva; en retrospectiva, creo que podría haber pensado demasiado en esto. Preguntar las limitaciones de las mallas de navegación es más probable preguntar las limitaciones de un gráfico como una forma de representación mundial. Solo una cosa más, si pudiera vincular a un ejemplo de Difusión Colaborativa, ¡realmente lo agradecería! Gracias de nuevo.
Ray Dey
-1, porque realmente no respondiste la pregunta. Dijiste que las navajas son una mejora cualitativa, pero el póster original quería saber cuáles eran esas cualidades.
Kylotan
@Kylotan: No, de hecho, la pregunta dice "Tengo muchos materiales sobre mallas de navegación [y] sus ventajas".
0

Las mallas de navegación están restringidas a las superficies, mientras que los puntos de referencia se pueden colocar en cualquier lugar y pueden hacer cualquier cantidad de conexiones (bordes) hacia cualquier dirección. Por lo tanto, los waypoints pueden proporcionar una solución más generalizada y flexible para, por ejemplo, juegos con unidades o entornos abstractos o extraordinarios.

Acey
fuente