El algoritmo de Dijkstra calcula la ruta más corta a todos los nodos en un gráfico al que se puede acceder desde la posición de inicio. Para su juego moderno promedio, eso sería innecesario e increíblemente costoso.
Hace una distinción entre 2D y 3D, pero vale la pena señalar que para cualquier algoritmo basado en gráficos, el número de dimensiones de su espacio de búsqueda no hace la diferencia. La página web a la que se vinculó analiza los gráficos de waypoint y las mallas de navegación; ambos están basados en gráficos y, en principio, podrían funcionar en cualquier cantidad de dimensiones. Aunque no hay "espacios cuadrados distintos para moverse", son "ranuras" discretas en el espacio al que se puede mover la IA y que los diseñadores del juego han establecido cuidadosamente.
En conclusión, A * es en realidad EL algoritmo para usar en juegos 3D tanto como en juegos 2D. Vamos a ver cómo funciona A *:
- Al principio, conoce las coordenadas de su posición actual y su posición de destino. Se realiza una estimación optimista de la distancia a su destino, por ejemplo, la longitud de la recta entre la posición de inicio y el objetivo.
- Considere los nodos adyacentes en el gráfico. Si uno de ellos es su objetivo (o lo contiene, en el caso de una malla de navegación), ya está.
- Para cada nodo adyacente (en el caso de una malla de navegación, esto podría ser el geometric center del polígono o algún otro tipo de punto medio), estimar el coste asociado de viajar a lo largo de allí como la suma de dos medidas: la longitud de la ruta que habría recorrido tan lejos, y otra estimación optimista de la distancia que aún sería tiene que ser cubierto.
- Ordene sus opciones del paso anterior por su costo estimado junto con todas las opciones que haya considerado anteriormente, y elija la opción con el costo estimado más bajo. Repita desde el paso 2.
Hay algunos detalles que no he discutido aquí, pero esto debería ser suficiente para ver cómo A * es básicamente independiente del número de dimensiones de su espacio. También debería poder ver por qué esto funciona para espacios continuos.
Hay algunos algoritmos estrechamente relacionados que se ocupan de ciertos problemas en la búsqueda A * estándar.Por ejemplo, la búsqueda recursiva best-first (RBFS) y la memoria simplificada A * (SMA *) requieren menos memoria, mientras que el aprendizaje en tiempo real A * (LRTA *) permite que el agente se mueva antes de que se haya calculado una ruta completa. No sé si estos algoritmos se utilizan realmente en los juegos actuales.
En cuanto al redondeo de esquinas, esto se puede hacer con líneas de distancia (donde las esquinas se reemplazan por arcos circulares) o con cualquier tipo de función spline para suavizado de trayectoria completa.
Además, son posibles algoritmos que dependen de un gradiente sobre el espacio de búsqueda (donde cada punto en el espacio está asociado a un valor), en lugar de un gráfico. Probablemente no se apliquen en la mayoría de los juegos porque requieren más tiempo y memoria, pero podría ser interesante conocerlos de todos modos. Los ejemplos incluyen varios hill-climbing algorithms (que son en tiempo real por defecto) y potential field métodos.
También existen métodos para obtener un gráfico de un espacio continuo, por ejemplo cell decomposition, Voronoi skeletonization y probabilistic roadmap skeletonization. El primero produciría algo compatible con una malla de navegación (aunque podría ser difícil hacerlo igualmente eficiente como una malla de navegación hecha a mano) mientras que los dos últimos producirían resultados que se parecerían más a los gráficos de waypoint. Todos estos, así como los métodos de campo potenciales y la búsqueda A *, son relevantes para la robótica.
Fuentes:
Esta sería una buena pregunta para el [Desarrollo de Juegos] (http: // GameDev. stackexchange.com) sitio. – Matthias