Cómo atravesar un laberinto mediante programación cuando llegas a un callejón sin salida

Question

Avanzar por el laberinto es bastante fácil, pero parece que no sé cómo retroceder por el laberinto para probar una nueva ruta una vez que llegas a un callejón sin salida sin retroceder demasiado.

Answer 1

Usar retroceder manteniendo un montón de decisiones de dirección anteriores.

Answer 2

El algoritmo más simple (de implementar) sería simplemente mantener una pila de ubicaciones en las que ha estado y la ruta que tomó desde cada una, a menos que retroceder le brinde esa información.

Para regresar, simplemente saque las ubicaciones antiguas de la pila y verifique si hay más salidas desde esa ubicación hasta que encuentre una ubicación antigua con una salida no probada.

Al probar consistentemente las salidas en el mismo orden cada vez, si sabe que retroceder a una ubicación proviene de abajo (es decir,la última vez que estuvo en la ubicación anterior, bajó), luego simplemente elige la siguiente dirección después abajo.

No estoy del todo seguro de lo que quieres decir con retrocediendo demasiado Sin embargo, supongo que querrás volver al lugar anterior donde tienes rutas no probadas, ¿no es eso lo que quieres?

Tenga en cuenta que, a menos que intente realizar un seguimiento del camino desde el punto de partida hasta su ubicación actual y evite esos cuadrados cuando intente encontrar nuevas rutas, podría terminar yendo en círculo, lo que eventualmente haría que la pila fuera demasiado grande.

Un método recursivo simple que marca el camino que toma y nunca ingresa a las áreas marcadas puede hacer esto fácilmente.

Además, si tu cosa que se mueve a través del laberinto es un poco más inteligente que simplemente poder moverse y golpear (detenerse) en las paredes, ya que puede ver desde su punto actual en todas las direcciones, tengo otros algoritmos que podrían ayudar.

Answer 3

Eric Lippert escribió una serie de artículos sobre la creación de un Implementación C# de A*, que podría ser más eficiente.