Estoy buscando un algoritmo de generación de laberinto que pueda generar laberintos sin callejones sin salida, pero solo como un comienzo y un final. De esta manera:Algoritmo para generación de laberinto sin callejones sin salida?
Imagen de http://www.astrolog.org/labyrnth/maze/unicursl.gif
¿Dónde encuentro o ir sobre la construcción de un algoritmo de generación de laberinto?
Parece que usted quiere una curva de llenado de espacio pseudo-aleatorio (por ejemplo, véase Context-based Space Filling Curves -EUROGRAPHICS ’2000 (formato PDF, 1,1 MB ))
miren un Space-filling curve.
Sospecho que podría aplicar algo de azar a la construcción de uno de estos para lograr lo que desea.
Las curvas llenas de espacio son geniales, pero las que están en ese papel tienen extremos sin salida, y no estoy seguro de cómo podrías deshacerte de ellas. –
@j_random_hacker: Creo que la idea es que las "paredes" en una curva llena de espacio son una única línea larga; así que si inviertes los negros y los blancos, entonces deberías tener un laberinto de soluciones sin callejones sin salida. –
@Lie: Buen punto. –
no he pensado en esto, sólo una idea:
El proceso de selección 'arbitrario' para nuevos trozos de pared puede comenzar tratando de 'crecer' secciones rectas perpendiculares a la pared exterior, luego, en algún momento, cambie al relleno siempre que sea posible.
Probablemente necesitaría la capacidad de dar marcha atrás en caso de que se atasque.
Probablemente no sea demasiado eficiente.
Creo que esto podría resultar en callejones sin salida. – phimuemue
@phimuemue: Un callejón sin salida implica que hay bloques que pueden convertirse en una pared sin hacer que la pared no tenga soluciones (es decir, el algoritmo de búsqueda de ruta de principio a fin falló). Siempre que sea posible agregar un bloque de pared sin bloquear la solución, agregue el muro. –
Me gustaría sugerir comenzar con el 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.
En el ejemplo que da, 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 lo veo, aquí hay dos desafíos algorítmicos. 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.
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 para no dar más pasos (en una esquina o en espiral al igual que caminar) haga estallar la pila hasta que tenga una ruta de caminata viable y continúe caminando desde allí hasta que la pila esté vacía (es decir, usted hace estallar la pila porque en cada paso anterior no había un vecino viable). Luego aplica las transformaciones a la estructura de datos del laberinto.
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 a medida que 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 que está junto a ti (pero mira abajo). 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 demuestran que al hacer esto no entra (o no ha visto aún) a un ciclo de creación de nuevas colas, siempre y cuando su nueva "cola" quede atrapada, no solo sin cuidado, vuelva a formar 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.
La caja de terminación es cuando te "atascas" en un elemento de borde, y has llenado la matriz (tu longitud de ruta es la misma que el área de la matriz) - listo. Tu punto de partida te lleva a tu punto final.
Parece que hay dos posibles ineficiencias y posibles inconvenientes 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 ciclo vincula con el que 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 que no puede ir a ningún otro lado (es otra esquina), entonces simplemente saltará 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 propenso a 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 ...
Ahh - He encontrado una manera mucho más fácil de generar un laberinto unicursal. – Nick
Ahh - He encontrado una manera mucho más fácil de generar un laberinto unicursal.
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.
continuación, arbitrariamente unirse a los bucles para formar bucles más grandes - por lo que (por ejemplo) 2 bucles 2x2 convertirse en un único bucle de 4x2. Sigue haciendo esto, asegurándote de no unirte a un bucle.
el tiempo que va a terminar con un solo bucle que utiliza todas las celdas ocupadas por la granja original de bucles. 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 la unión en T en el lado opuesto para volver a formar su pieza única cadena con una nueva ubicación final.
Si usted está trabajando en un laberinto y pico y pico por, utilice esta última técnica de gusano uno de sus extremos a la esquina sin llenar para completar su laberinto.
Creo que he encontrado otro método, sin embargo, aún no lo he probado exhaustivamente.
Ver https://twitter.com/tdhooper/status/340853820584230915/photo/1
De izquierda a derecha:
generar un laberinto no unicursal como se describe aquí https://en.wikipedia.org/wiki/File:Prim_Maze.svg, creo que este es el algoritmo de Prim
sellar la salida
Dibuja un camino que visita cada punto del laberinto (es decir, intenta resolverlo)
Make este camino una pared
Funciona: http://www.stainlessvision.com/lab/maze-generator/unicursal.html código aquí: https: // github.com/tdhooper/random-laberinto-generador –
¿Hay alguna restricción, por ejemplo no hay cuadrados negros de 2x2? –
@Lie Ryan: No. Aunque sería bueno tener tales algoritmos entre las respuestas. – Fejuto
Relacionados: http://stackoverflow.com/questions/2641964/algorithm-to-generate-a-segment-maze – nico