Navegación AI alrededor de un mapa 2d - evitando obstáculos

Question

Sé que mi pregunta parece bastante vaga, pero no puedo pensar en una mejor manera de decirlo, así que comenzaré explicando lo que estoy tratando de hacer.

Actualmente estoy trabajando en un proyecto por el cual me dieron un mapa y estoy codificando un 'Critter' que debería poder navegar por el mapa; el bicho tiene varias otras funciones, pero esas no son relevantes para la pregunta actual. Todo el programa y la solución se escriben en C#.

Puedo controlar la velocidad de la criatura, y recuperar su ubicación actual en el mapa al devolver su posición X e Y actual, también puedo establecer su dirección cuando colisiona con el terreno que la bloquea.

El único problema que tengo es que no se me ocurre una forma de navegar inteligentemente por el mapa; Hasta ahora, he estado basándome en la dirección en que se encuentra la criatura cuando colisiona con el terreno, ¡y esta no es una buena manera de moverse por el mapa!

No soy un programador de juegos, y esto es para una asignación de software, así que no tengo ni idea de las técnicas de IA.

Aquí hay un enlace a una imagen de lo que los mapas y bichos parecen:

Map and Critter image

estoy de ninguna manera busca de alguien que me diera una solución completa, sólo una pulsación de la general dirección en la navegación del mapa.

Answer 1

Me gustaría utilizar un enfoque orientado a los objetivos. Su pregunta establece que el objetivo es explorar el mapa y evitar obstáculos, de modo que eso es lo que hacemos nuestro objetivo. ¿Pero cómo exploramos todo el mapa? Exploramos lo inexplorado.

Desde el principio solo tiene un área inexplorada, el cuadrado en el que se encuentra. El resto del mapa está marcado como inexplorado. Eliges una ubicación inexplorada y haces que tu objetivo sea explorarla. ¿Pero cómo llegas allí? Crea un subforo para explorar la ubicación junto a él. ¿Y cómo lo hace? Explore la casilla al lado de eso, y así sucesivamente, hasta que su objetivo original se descompone en una secuencia de exploraciones, comenzando desde su casilla actual y navegando hasta el cuadrado objetivo.

Al tocar obstáculos y descubrir características del mapa, es posible que deba cambiar algunos de los objetivos intermedios. P.ej. Cuando tocas una pared, se debe limpiar el subgrupo para explorar esa casilla y crear un nuevo plan para encontrar una ruta alternativa. Esto se conoce como retroceso.

Eso es básicamente para la descripción de alto nivel. ¡Espero que ayude!

Answer 2

A * Buscar

Tome una mirada en el algoritmo de búsqueda de caminos A*. Básicamente es el enfoque estándar para cosas como esta.

Amit Patel escribe en pathfinding for games tiene una muy buena introducción a A *, así como las variantes populares del algoritmo.

Encontrará una C# aplicación here y here

dinámico A *

Digamos que el terreno no se sabe de antemano que va a busca, sino que se descubre como el agente explora su entorno. Si su agente encuentra un obstáculo previamente desconocido, puede actualizar el mapa del terreno del agente y luego volver a ejecutar A * para buscar un nuevo camino hacia el objetivo que se dirige alrededor de la obstrucción.

Si bien es una solución viable, volver a ejecutar el algoritmo de planificación desde cero cada vez que encuentre un nuevo obstáculo resulta en una cantidad considerable de cálculos redundantes. Por ejemplo, una vez que estás cerca del obstáculo, es posible que la ruta más eficiente hacia el objetivo siga la que planeas tomar antes de descubrir el obstáculo. Con solo volver a ejecutar A *, deberá volver a calcular esta sección de la ruta anterior.

Puede evitar esto usando Dynamic A* (D*). Como realiza un seguimiento de las rutas calculadas anteriormente, cuando el agente encuentra un nuevo obstáculo, el sistema solo necesita calcular nuevas rutas en el área alrededor del obstáculo. Después de eso, solo puede reutilizar las rutas existentes.

Answer 3

Si el único conocimiento del entorno que tiene es la posición de su critter y su velocidad, lo mejor que puede hacer es un algoritmo de seguimiento de pared, creo. Si puede detectar algunas de las otras cosas en su entorno, tiene muchas más opciones.

Algunos de los más populares tipos algoritmo son ...

• A * Búsqueda (el clásico)
• Visibility Graphs
• Voronoi Diagrams (similar to the above)
• Potential Fields

campos potenciales es una una forma elegante de decir que cada obstáculo o pared tiene una "fuerza de repulsión" mientras que todos se van al tiene una "fuerza atractiva". La fuerza de la fuerza se basa en la distancia del objeto y la "severidad" del objeto. (Un pozo de lava es mucho más severo para atravesarlo que una carretera con baches) Después de construir los campos de fuerza, el algoritmo ingenuo se reduce a seguir el camino de menor resistencia. Las mejores versiones pueden detectar mínimos y máximos locales y escapar de esos pozos.

Critter 
    -----\ /-------\ 
      \/  \ 
      \/   \ 
    Local Minima Trap  \ 
          \ 
          \ 
          Goal 

Answer 4

Parece que llego tarde a la fiesta. Si tu criatura tiene un GPS y el mapa completo a mano, lo correcto es definitivamente A *, y si el mapa es lo suficientemente pequeño, un BFS simple también lo haría si no deseas codificar A * (A * tiene bastantes casos de esquina que desea manejar bien).

Sin embargo, una pregunta diferente es ¿qué pasa si su criatura solo conoce la dirección de la meta y solo puede observar localmente qué hay alrededor? ¿Qué pasa si tu criatura no conoce el mapa completo?

En este caso, querrá implementar el "algoritmo de error" para la navegación. Enlace: http://www.cs.cmu.edu/~./motionplanning/lecture/Chap2-Bug-Alg_howie.pdf

Es una linda pieza de algoritmo que funciona para todos los mapas desconocidos, usted tendría una explosión de codificación, estoy seguro.