Contexto
Los viejos juegos de aventuras gráficas de Lucas Arts (era ScummVM) de apuntar y hacer clic utilizaban precalculación de rutas. Aquí hay un bosquejo de la técnica.
Paso 1
El piso de cada habitación estaba dividido en lo que llamaron "cajas de paseo", que eran más o menos equivalentes a los nodos en una malla de navegación, pero limitado a las formas trapezoidales. P.ej:
______ _____ _________ _____
\ A | B | C | D \
\_____| | |_______\
|_____| |
|_________|Paso 2
Un algoritmo fuera de línea (por ejemplo, Dijkstra o A *) calcularía la ruta más corta entre cada par de nodos y almacenaría el primer paso de la ruta en una matriz 2D, indexada en cada dimensión por el nodo inicial y final utilizado. Por ejemplo, usando los cuadros de caminata de arriba:
___ ___ ___ ___
| A | B | C | D | <- Start Node
___|___|___|___|___|
| A | A | A | B | C | ---
|___|___|___|___|___| |
| B | B | B | B | C | |
|___|___|___|___|___| |-- Next node in shortest path
| C | B | C | C | C | | from Start to End
|___|___|___|___|___| |
| D | B | C | D | D | ---
|___|___|___|___|___|
^
|
End NodeComo puede suponer, los requisitos de memoria aumentan rápidamente a medida que aumenta el número de nodos (N ^ 2). Dado que un corto generalmente sería lo suficientemente grande como para almacenar cada entrada en la matriz, con un mapa complejo de 300 nodos que resultaría en el almacenamiento de un extra:
300^2 * sizeof(short) = 176 kilobytesPaso 3
Por otro lado, calcular la ruta más corta entre dos nodos fue extremadamente rápido y trivial, solo una serie de búsquedas en la matriz. Algo como:
// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
Current = LookUp[Current, End]
Path.Add(Current)
ENDWHILEAplicando este algoritmo simple para encontrar la ruta más corta de C a A devuelve:
1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, ExitPregunta
Sospecho que con el potente hardware de hoy, junto con los requisitos de memoria para hacer esto en todos los niveles, cualquier beneficio que alguna vez tuvo esta técnica ahora se ve superado simplemente al realizar una A * en tiempo de ejecución.
También he oído que hoy en día las búsquedas de memoria pueden ser incluso más lentas que el cálculo general, por lo que crear tablas de búsqueda de seno y coseno ya no es tan popular.
Pero debo admitir que todavía no conozco demasiado sobre estos asuntos de eficiencia de hardware de bajo nivel, así que aprovecho esta oportunidad para pedir la opinión de aquellos más familiarizados con el tema.
En mi motor también necesitaba la capacidad de agregar y eliminar dinámicamente nodos al gráfico en tiempo de ejecución ( vea esto ), por lo que la ruta precalculada solo hizo las cosas más complicadas, así que lo descarté (sin mencionar que mi solución de tiempo de ejecución A * ya estaba funcionando perfectamente ) Aún así, me quedé preguntándome ...
En pocas palabras, ¿esta técnica sigue siendo relevante hoy en día en algún escenario?
fuente
Respuestas:
No puedo ver ningún beneficio al usar tal técnica.
Carece de la flexibilidad de un gráfico (puede tener diferentes LOD, no tienen que tener ninguna forma específica, etc.). Además, cualquier usuario de su motor sabrá qué es un gráfico y cómo usarlo. Entonces, si desean agregar una funcionalidad adicional, tendrán que aprender a implementar su extensión utilizando una situación completamente nueva para ellos.
Como mencionaste, parece que se escalaría horriblemente. También vale la pena señalar que si un gráfico encaja en el efectivo y ejecuta todos los resultados de su camino de forma consecutiva, realmente reduce el tiempo de E / S. Parece que su implementación pronto crecerá demasiado para caber en cualquier caché.
A menos que pueda ajustar todo su programa y necesite memoria en la memoria caché, va a embotellar al sacar y sacar cosas de la memoria antes de embotellar el procesador.
También tenga en cuenta que muchos juegos tienen bucles separados para actualizar la IA. Creo que la forma en que está configurado mi proyecto es que hay un ciclo de actualización para la entrada del usuario a 60 hz, la IA es de solo 20 hz y los juegos se dibujan lo más rápido posible.
También como nota al margen, hice algo de programación GBA solo por diversión y nada se transfirió al uso de un dispositivo moderno. Para el GBA, todo se trataba de minimizar la carga de trabajo del procesador (porque era patético). También debe darse cuenta de que la mayoría de los lenguajes de alto nivel C # y Java (no tanto C ++ o C) hacen toneladas de optimizaciones para usted. En cuanto a la optimización de su código, no tiene mucho que hacer aparte de acceder a la memoria lo menos posible y cuando ejecuta tantos cálculos como sea posible antes de traer nueva memoria que la sacará del caché y se asegurará de que esté solo haciendo cosas una vez.
Editar: También para responder a su título, sí lo es. La precomputación de rutas de uso frecuente es una excelente idea y se puede hacer con A * en cualquier lugar fuera de su ciclo de juego. Por ejemplo, desde su base a un recurso en un RTS para que los recolectores no tengan que volver a calcular cada vez que quieran irse o regresar.
fuente