En un juego como Warcraft 3 o Age of Empires, las formas en que un oponente de AI puede moverse por el mapa parecen casi ilimitadas. Los mapas son enormes y la posición de otros jugadores cambia constantemente.¿Cómo funciona Pathfinding en los videojuegos RTS?
¿Cómo funciona la búsqueda de ruta de la IA en juegos como estos? Los métodos de búsqueda de gráficos estándar (como DFS, BFS o A *) parecen imposibles en dicha configuración.
Esto es un poco de un ejemplo sencillo, pero demuestra que se puede hacer que la ilusión de AI/Indepth Pathfinding de un conjunto no complejo de reglas: Pac-Man Pathfinding
Esencialmente, es posible que la IA para conocer información local (cercana) y tomar decisiones basadas en ese conocimiento.
A* es un algoritmo de ruta común. Este es un tema popular de desarrollo de juegos: debería poder encontrar numerosos libros y sitios web que contienen información.
Tome lo siguiente con un grano de sal, ya que no tengo experiencia en primera persona con pathfinding.
Dicho esto, es probable que haya diferentes enfoques, pero creo que los métodos estándar de búsqueda de gráficos, especialmente (variantes de) A * son perfectamente razonables para los juegos de estrategia. La mayoría de los juegos de estrategia que conozco parecen estar basados en un sistema de fichas, donde el mapa está compuesto de pequeños cuadrados, que se pueden mapear fácilmente en un gráfico. Un ejemplo sería StarCraft II (Screenshot), que seguiré usando como ejemplo en el resto de esta respuesta, porque estoy más familiarizado con él.
Mientras que A * se puede utilizar para los juegos de estrategia en tiempo real, hay algunos inconvenientes que tienen que ser superados por ajustes en el algoritmo básico:
A * es demasiado lento
Como un RTS es por definición "en tiempo real", esperar a que el cálculo termine frustrará al jugador, porque las unidades se retrasarán. Esto puede remediarse de varias maneras. Una es usar Multi-tiered A*, que calcula un curso aproximado antes de tener en cuenta los obstáculos más pequeños. Otra optimización obvia es agrupar las unidades dirigidas al mismo destino en un pelotón y solo calcular una ruta para todas ellas.
En lugar del ingenuo enfoque de hacer que cada mosaico sea un nodo en el gráfico, también se podría construir navigation mesh, que tiene menos nodos y podría buscarse más rápido; esto requiere ajustar un poco el algoritmo de búsqueda, pero aún así ser A * en el núcleo.
A * es estática
A * trabaja en un gráfico estático, por lo qué hacer cuando los cambios en el paisaje? No sé cómo se hace esto en los juegos reales, pero imagino que el recorrido se hace de forma repetida para hacer frente a nuevos obstáculos o eliminar obstáculos. Tal vez están usando un incremental version of A* (PDF).
Para ver una demostración de cómo hacer frente a StarCraft II, vaya a 7:50 en this video.
A * tiene información perfecta
Una parte de muchos juegos de estrategia en tiempo real es un terreno inexplorado. Como no puedes ver el terreno, tus unidades tampoco deberían saber dónde caminar, pero a menudo lo hacen de todos modos.Un enfoque es penalizar el caminar a través de terrenos inexplorados, por lo que las unidades son más reacias a aprovechar su omnisciencia, otra es quitar la omnisciencia y simplemente asumir que el terreno inexplorado es manejable. Esto puede resultar en que las unidades tropiecen en callejones sin salida, a veces los que son obvios para el jugador, hasta que finalmente exploran un camino hacia el objetivo.
Niebla de guerra es otro aspecto de esto. Por ejemplo, en StarCraft 2 hay obstáculos destructibles en el mapa. Se ha demostrado que puedes ordenar que una unidad se mueva a la base enemiga, y comenzará por un camino diferente si el obstáculo ya ha sido destruido por tu oponente, por lo que te dará información que no deberías tener.
En resumen: Puede usar algoritmos estándar, pero puede que tenga que usarlos inteligentemente. Y como último extra: he encontrado Amit’s Game Programming Information interesante con respecto a la ruta. También tiene enlaces para seguir discutiendo el problema.
Echa un vistazo a los gráficos de visibilidad. Creo que eso es lo que usan para encontrar rutas.
buena pregunta. Quizás sería mejor publicarlo en http://gamedev.stackexchange.com/ –