solving pathfinding algorithm maze

algorithm - pathfinding - Algoritmo para generación de laberinto sin callejones sin salida?



recursion solving a maze (8)

Ahh, he encontrado una manera mucho más fácil de generar un laberinto único.

Comience con una cuadrícula en blanco y llénela con pequeños bucles de 2x2. Si la cuadrícula es impar-par, necesitará mezclar algunos bucles de 2x3, y si es impar-por-impar, tendrá que dejar un solo cuadrado libre - Normalmente dejo una esquina sin llenar.

A continuación, unir arbitrariamente los bucles para formar bucles más grandes, por lo que (por ejemplo) 2 bucles de 2x2 se convierten en un solo bucle de 4x2. Sigue haciendo esto, asegurándote de no unirte a un bucle.

Finalmente, terminará con un solo bucle que utiliza todas las celdas ocupadas por la granja de bucles original. Rompe este bucle en cualquier posición, y tendrás un laberinto único, donde las ubicaciones de inicio y final están una al lado de la otra.

Ahora puede mover los puntos finales alrededor de la cuadrícula formando y rompiendo pequeños bucles, enganche el extremo en otro punto del laberinto y luego rompa el empalme en T en el lado opuesto para volver a formar su pieza única de cuerda con un nuevo ubicación final

Si estás trabajando en un laberinto extraño por extraño, usa esta última técnica para desplazar uno de tus extremos a la esquina libre para completar tu laberinto.

Estoy buscando un algoritmo de generación de laberinto que pueda generar laberintos sin callejones sin salida, pero solo un principio y un final. Me gusta esto:

Imagen de http://www.astrolog.org/labyrnth/maze/unicursl.gif

¿Dónde encuentro o voy a construir un algoritmo de generación de laberinto?

Cuando "camina", mantenga los cambios realizados en cada paso de una pila, para que de esa manera pueda ver x pasos adelante y luego en cada etapa, de modo que no pueda seguir avanzando (caminando hacia una esquina o caminando como una espiral) la pila hasta que tengas una ruta de caminata viable y sigas caminando desde allí hasta que la pila esté vacía (es decir, levantes la pila todo el camino de regreso porque en cada paso anterior no había un vecino viable). Luego aplica las transformaciones a la estructura de datos del laberinto.

En el ejemplo que das, solo hay una ruta real de principio a fin. Si eso es todo lo que quieres, ¡estoy pensando que podrías usar caminatas al azar!

El concepto es simple: dados los límites exteriores del laberinto, un punto de inicio y un punto final, escriba una función para generar caminatas aleatorias desde el punto de inicio que eventualmente terminan en el punto final. Las condiciones serían que nuestro "andador aleatorio" solo puede moverse hacia arriba, hacia abajo, hacia la derecha o hacia la izquierda desde el cuadrado anterior, y no puede entrar dentro de un cuadrado de un cuadrado previamente atravesado (esto crea muros).

Como yo lo veo, hay dos desafíos algorítmicos aquí. El primero es determinar si estamos dentro de un cuadrado de un cuadrado previamente atravesado (colisiones). Tal vez podríamos mantener una lista de los cuadrados atravesados ​​(sus coordenadas) y los límites del laberinto, y para cada nuevo cuadrado evaluar la distancia de cada cuadrado en la lista. Aunque esto no suena muy eficiente.

El otro desafío es llegar al punto final con nuestra caminata aleatoria. Si las colisiones con casillas previamente atravesadas no fueran un problema, con el tiempo llegaríamos a nuestro punto final, pero con ellas tenemos el problema de que podríamos aislarnos del punto final. La forma de evitar esto es verificar y evitar la entrada de bucles. Si evitamos ingresar bucles formados por la ruta atravesada y / o los límites del laberinto, entonces mantenemos una ruta posible al punto final. En cuanto a calcular si estamos en un bucle ... Meh, eso es un poco difícil.

Si ya tiene un algoritmo de resolución de laberintos, puede ejecutarlo siempre que tenga una posible colisión para ver si existe una ruta desde su casilla actual al punto final. Cuando lo ejecutes, haz que piense que todos los cuadrados atravesados ​​previamente son muros, así como sus límites.

Estoy trabajando en esto en este momento ... Comenzando desde un borde, estoy caminando al azar a través de una matriz cuadrada, marcando las celdas con la longitud del camino cuando las paso.

Cuando te quedas atascado (y lo harás), crea una unión en T formando un bucle con la ruta más reciente adyacente a ti (pero mira a continuación). Luego retrocedí a lo largo del camino existente hacia el otro lado del cruce en T y rompí el ciclo allí. Esta cola que cuelga luego forma su nueva "cabeza" de la caminata aleatoria (recuerde recalcular las longitudes de su ruta desde la fuente de ruta), y puede continuar.

Los experimentos muestran que al hacer esto, no (o que aún no ha visto, a continuación) se metió en un ciclo de creación de nuevas colas, siempre y cuando su nueva "cola" quede atrapada, no se vuelva a conformar sin cerebro. un enlace con la celda de la que acaba de deshacerse si es la más reciente; elija la segunda más reciente en ese caso.

El caso de terminación es cuando te "atascas" en un elemento de borde y llenas la matriz (tu longitud de ruta es la misma que el área de la matriz) - ya terminaste. Tu punto de partida te lleva a tu punto final.

Parece que hay dos posibles ineficiencias y posibles contratiempos con esto (estoy jugando con el algoritmo en este momento) - A veces te metes en una esquina y la ÚNICA manera de continuar es volver a formar el lazo con el que está acabas de romper. Luego, la secuencia rastrea a través de todos los bucles que ha realizado anteriormente hasta el punto en que originalmente se quedó atascado. Si eso no puede ir a ningún otro lado (es otra esquina), entonces rebotarás entre los dos. Hay formas de evitarlo, pero significa mantener una especie de lista de celdas en bucle, solo despejándola cuando realmente estableces una nueva ruta.

La otra es que parece más probable dejar un cuadrado impar sin llenar, particularmente cuando su matriz es impar por impar. No he investigado completamente por qué este es el caso, y es cuando ocurre esto que el problema de la esquina previa parece ser particularmente frecuente. El trabajo continúa ...

No he pensado en esto, solo una idea:

  • Concéntrate no en el camino, sino en las paredes
  • Comience con solo el cuadro exterior negro
  • Añada progresivamente bloques de muro en posiciones arbitrarias adyacentes a bloques de muro existentes, manteniendo la condición de que sigue habiendo un camino de principio a fin
  • Cuando ninguna celda de ruta tiene más de dos vecinos de ruta, ya ha terminado

El proceso de selección "arbitrario" para nuevos trozos de muro puede comenzar tratando de "crecer" secciones rectas perpendiculares a la pared exterior, luego, en algún momento, cambie al relleno donde sea posible.

Probablemente necesitaría la habilidad de retroceder si se atasca.

Probablemente no sea demasiado eficiente.

Quisiera comenzar con un cuadrado completamente negro (completo) y tratar de cavar el camino. Durante la excavación puede asegurarse fácilmente de que no haya callejones sin salida, simplemente continúe. Utilice el algoritmo de búsqueda inicial de profundidad y retroceso. Realice una "caminata aleatoria": en cada paso, decida al azar si desea mantener la dirección o cambiarla. Comprueba la condición del callejón sin salida: si te quedas atascado, puedes decir "bueno, he terminado, estoy al final" o, si consideras que el laberinto aún no ha sido lo suficientemente cavado, solo retrocede. Siempre recuerda lo que has hecho antes y prueba al azar alguna otra acción. Probablemente use cierta heurística para preferir ciertas direcciones, como, por ejemplo, mantener siempre un poco de espacio libre antes de esquivar la pared, intente primero caminar alrededor de las paredes, etc. De esta manera podría encontrar la solución deseada que llene toda la casilla mucho más rápidamente.