Mapa de juego parcialmente observable: ¿es apropiado A *?

16

Sé muy poco sobre el desarrollo de juegos y estoy tratando de entender los algoritmos de búsqueda de caminos.

Considere esta configuración: un agente está en un mapa 2D y debe encontrar el camino más corto hacia un objeto conocido globalmente, pero solo tiene información sobre los obstáculos en su alcance de visión local (es decir, solo se conocen los obstáculos inmediatos, se desconoce el diseño general del mapa )

Además, cada movimiento a un cuadrado adyacente es costoso y el algoritmo de búsqueda de ruta debe minimizar el número de movimientos.

La eficiencia computacional también es de suma importancia y más importante que la precisión.

¿Es A * apropiado para este caso de uso?

algorithm path-finding maps David Chouinard
fuente

Respuestas:

19

Debe usar el algoritmo D * , que está diseñado para este escenario exacto. Específicamente, la implementación de D * Lite es la variante más eficiente y simple.

jmegaffin
fuente
2
Muy relevante . Comprender D * -lite es simple una vez que comprende LPA * (el algoritmo D * -lite se basa en) , pero LPA * en sí mismo es bastante complejo. Entonces, si planea implementar realmente D * -lite, el documento sobre LPA * sería el lugar para comenzar (suponiendo que ya comprenda A *, eso es)
BlueRaja - Danny Pflughoeft
3

Muchas implementaciones de IA de juegos en esa situación elegirán hacer trampa, y se darán un conocimiento completo del mapa, donde su oponente humano no tiene eso. Luego puede simplemente aplicar A * al mapa completo.

Lo sensato que esto parezca para las unidades controladas por computadora dependerá de cosas como el laberinto como son los mapas, y si es probable que el jugador aprenda los diseños de mapas con el tiempo.

Si esto es para unidades controladas por jugadores, también puede evitar que el jugador seleccione un destino que aún no han explorado, para obligarlos a explorar manualmente.

Adán
fuente
2
Buenas sugerencias, no apropiadas para mi caso de uso, pero podrían ser útiles para otros. (Estoy desarrollando una IA para competir en una simulación de juego)
David Chouinard
También hay juegos que utilizan la implementación de búsqueda de ruta supone que las áreas inexploradas son cruzables, mientras que las áreas visitadas previamente no habían tenido ningún cambio en la capacidad de cruce desde la última visita (es decir, no sabrían que un muro puede haber sido destruido o construido hasta que visita el área de nuevo).
Lie Ryan