¿Cómo funciona el pathfinding en los juegos RTS?

42

[cruzado desde stackoverflow]

En un juego como Warcraft 3 o Age of Empires, las formas en que un oponente de IA puede moverse por el mapa parecen casi ilimitadas. Los mapas son enormes y la posición de otros jugadores cambia constantemente.

¿Cómo funciona la búsqueda de rutas de IA en juegos como estos? Los métodos estándar de búsqueda de gráficos (como DFS, BFS o A *) parecen imposibles en dicha configuración.

mantas
fuente
2
¿Por qué A * no funcionaría en este gráfico?
user712092
Blog relacionado: ai-blog.net/archives/000152.html
diez de
1
@tenfour, el enlace está roto ahora.
Montreal

Respuestas:

29

En la mayoría de los casos, el uso de A * sobre una malla de navegación (comúnmente conocido como "navmesh") es la solución de búsqueda de rutas que utilizan los RTS comerciales. Hay una explicación detallada de cómo funcionan navmeshes, por lo que son una solución mejor que los sistemas de puntos de recorrido, y enlaces a recursos de implementación, aquí .

Si está planeando desarrollar modos de juego especiales (captura de puntos / nodos) o unidades que patrullan, se cubren, etc., es probable que desee implementar una capa de punto de referencia sobre su navegador, para controlar el comportamiento de la IA ( no la búsqueda de rutas ).

Ari Patrick
fuente
17

Consulte el algoritmo Flowfield utilizado en Supreme Commander 2. Hace un trabajo mucho mejor que la mayoría de los sistemas de búsqueda de rutas RTS (pase a 0:50 para ver algunos ejemplos).

ZorbaTHut
fuente
44
esa es una demostración realmente genial pero no me dice nada sobre la implementación en sí misma
MetaGuru
44
Mencionaron en una oración: se basa en la investigación de flujo de multitudes de UW, que puede encontrar en grail.cs.washington.edu/projects/crowd-flows .
El algoritmo de campo de flujo parece bastante interesante, y definitivamente parece hacer un trabajo de ruta mucho mejor que la mayoría de los algoritmos, pero desearía que hubiera documentación pública sobre cómo funciona el sistema en sí, no solo cómo funciona el sistema en el que se basa. Naturalmente, hay muchas preguntas que los desarrolladores deberían hacer antes de implementar un sistema central como este, pero, en este caso, parece que la única forma de responder esas preguntas es implementar primero el sistema. :(
Ari Patrick
2
@Kragen: Realmente solo necesitas dos unidades antes de que A * (especialmente señalado) haga que se choquen entre sí una y otra vez, y necesitas algún tipo de sistema para solucionarlo.
55
Según el video, la búsqueda de caminos de Starcraft 2 se ve así. ¿SC2 usa el campo de flujo?
Chris Bui
7

Muchos juegos antiguos usan A *. El Starcraft original usaba A *; lo que condujo a algunos problemas al tratar con la colisión. Starcraft 2 maneja muy bien la colisión, utilizando un comportamiento de swaming / flocado para mantener el control fluido de grupos grandes. Este artículo de gamedev analiza cómo se podría lograr esto.

phillipwei
fuente
2

Ya estoy de acuerdo con las otras respuestas, pero también trato de pensar en WoW / Warcraft3 como mundos 2D reales. No son tan diferentes de los azulejos, son solo los azulejos.

También podría pensar en cómo un GPS encuentra el mejor camino? Hay un montón de algoritmos para encontrar rutas a través de mapas vinculados.

Creo que algunos de los primeros scripts de "Quake bots" también podrían ayudarlo, ya que fueron desarrollados para trabajar en "áreas desconocidas" porque podríamos diseñar nuestros propios niveles desde cero.

En general, mi forma personal de lidiar con un mapa de este tipo sería pensar en él como el pathfinder A *. Pero primero haría un cálculo previo de cada "punto de mosaico" e indexaría todo esto con el "vecino más cercano", etc. Luego, cuando un objeto necesitara ir de A a B, luego simplemente buscar en B, ver qué está conectado y seguir repitiendo hasta que alcanzar la meta.

Según el tipo de juego y el paisaje / escenario, también pueden ser útiles diferentes tácticas de preescaneo. Algunos juegos tienen obstáculos muy pequeños y estos pueden ser movimientos de "línea recta" + algunos "cómo me desplazo" para los objetos.

Espero que esto tenga un poco de sentido y quizás te haya dado algunas ideas para trabajar.

BerggreenDK
fuente
1

La mayoría de los juegos usan algún tipo de Algoritmo de búsqueda o A * para encontrar rutas en un mapa. La IA se modifica en algunos aspectos, obviamente, por razones de rendimiento.

Notarás esto en Starcraft 2, donde Zerglings obviamente no funciona bien en absoluto, sería una pesadilla de CPU hacer eso para Zerglings. Simplemente hacen lo posible para llegar de A a B y ni siquiera intentan encontrar el mejor camino. Se acercarán lo más posible y luego el cuello de la botella en los estranguladores o rampas.

Bryan Harrington
fuente
1

El mapa es una cuadrícula. La cuadrícula es un gráfico. A * funciona en gráficos, es un algoritmo de búsqueda de gráficos. A * debería buscar algunos nodos del gráfico.

Como se ha mencionado, pueden usar la malla de navegación. Pero la A * (o algo similar) estará encima de esa malla de todos modos, porque los polígonos de esta malla son solo nodos de un gráfico; A * buscará la ruta de un polígono a otro polígono.

No estoy seguro sobre Warcraft o juegos comerciales, pero también existe una técnica llamada Difusión colaborativa y es muy simple; generalmente se realiza en cuadrícula. También existe una técnica llamada Campos potenciales , que es muy similar a la anterior si no es la misma.

También puedes probar:

  • si algunos de estos juegos tienen código fuente disponible
  • si algunos de los clones de estos juegos tienen fuente disponible
  • si SDK o los editores no sugieren algo
  • pregunte a los empleadores de las compañías que hacen estos juegos, algunos de ellos podrían estar dispuestos a compartir
usuario712092
fuente
0

No tengo mucha experiencia, pero creo que una buena solución se basa en la heurística, no en una verificación completa del mapa conocido. La heurística que se me ocurre está basada localmente y basada en la experiencia. Los controles locales pueden basarse en la verificación del terreno local y los obstáculos, manteniéndose en movimiento hacia la dirección requerida. Creo que la mayoría de los mapas no requieren movimientos complejos tipo laberinto, pero están bastante conectados. Otra heurística es utilizar rutas conocidas anteriores (exploradas por otras unidades o explícitamente por el usuario) para mover unidades a posiciones conocidas o casi conocidas. Pero estoy hablando de moverme en mapas grandes, no realmente en espacios cerrados como dijo ZorbaTHut. En casos de hacinamiento, el algoritmo puede ser más complejo, requiriendo tipos de "predicción", coordinación entre unidades del mismo equipo o simplemente estrategias de espera similares a semáforos. También,

Creo que los algoritmos heurísticos son buenos porque generalmente proporcionan una buena solución en grandes espacios con un tiempo de cálculo razonable (lo que importa, cuando se mueven muchas unidades).

Lo siento si esta es una respuesta genérica: trabajé con multitudes, pero el espacio era bastante peculiar y no puedo explicar exactamente cómo funcionaba el algoritmo (de todos modos, estaba basado en agentes, no definido globalmente). Espero que pueda obtener algunas ideas útiles de mi respuesta.

AkiRoss
fuente
Mmmh, me pregunto qué estuvo mal en lo que dije ... ¿Fue demasiado difícil dejar un comentario?
AkiRoss el
Por cierto, me gustaría destacar que A * utiliza un enfoque heurístico. Gracias por el -2.
AkiRoss el
Su respuesta es: "Zanja A * y es como tirar y tirar la tuya". Ese puede ser el comienzo de una respuesta razonable, pero proporciona muy poca información además de la sugerencia. Piensa que la razón de la votación negativa es que no deja en claro lo difícil que sería implementar su solución. No dudo que un súper genio con un tiempo ilimitado podría codificar / ajustar un algoritmo de ruta para un RTS dado que sería superior a A * en un navegador. Pero "genio" e "ilimitado" son muy difíciles de encontrar.
deft_code
Correcto. Pensé que el chico quería una respuesta genérica, ya que no preguntó cómo hacerla, sino cómo funcionan en general. De todos modos, no soy un experto como dije: solo estaba dando información sobre las soluciones que conozco sobre la exploración de grandes espacios en una aplicación de IA general. Gracias por tu comentario.
AkiRoss