Esta publicación clásica detalla las formas más populares de crear y recorrer laberintos. El artículo se divide en cuatro partes: clasificación, algoritmos de generación, algoritmos para resolver laberintos y otras operaciones con laberintos.Clasificación del laberinto
Los laberintos en su conjunto (y, por lo tanto, los algoritmos para crearlos) se pueden dividir en siete clasificaciones diferentes: dimensión, hiperdimensión, topología, teselación, enrutamiento, textura y prioridad. El laberinto puede usar un elemento de cada clase en cualquier combinación.
Dimensión: la clase de dimensión determina esencialmente cuántas dimensiones en el espacio ocupa el laberinto. Los siguientes tipos están disponibles:
Bidimensional : la mayoría de los laberintos, tanto de papel como reales, tienen esta dimensión, es decir, siempre podemos mostrar el plano del laberinto en una hoja de papel y movernos a lo largo de él sin cruzar ningún otro corredor del laberinto.- Tridimensional : el laberinto tridimensional tiene varios niveles; en él (al menos en la versión ortogonal), los pasajes pueden, además de las cuatro direcciones cardinales, bajar y subir. Un laberinto 3D a menudo se visualiza como una matriz de niveles 2D con escaleras arriba y abajo.
Dimensiones superiores : puede crear laberintos de cuatro dimensiones e incluso más multidimensionales. A veces se visualizan como laberintos 3D con "portales" que conducen a través de la cuarta dimensión, por ejemplo, portales hacia el "pasado" y el "futuro".
Entrelazado : laberintos con entrelazado: estos son esencialmente laberintos bidimensionales (o más bien 2.5 dimensionales), en los que, sin embargo, los pasajes pueden superponerse entre sí. Cuando se muestra, generalmente es bastante obvio dónde están los callejones sin salida y cómo un pasaje está por encima del otro. Los laberintos del mundo real, en los que hay puentes que conectan una parte del laberinto con otra, se entrelazan parcialmente.
Hiperdimensión: la clasificación según la hiperdimensión corresponde a la dimensión de un objeto que se mueve a través de un laberinto, y no al laberinto en sí. Los siguientes tipos están disponibles:
No hiperlabirintios : casi todos los laberintos, incluso aquellos creados en alta dimensionalidad o con reglas especiales, generalmente no son hiperlabirintios. En ellos trabajamos con un punto o un objeto pequeño, por ejemplo, una pelota o el jugador mismo, que se mueve de un punto a otro, y la ruta pavimentada forma una línea. En cada punto, hay un número de opciones fácilmente contables.- Hiperlabirinto: los hiperlabirinto son laberintos en los que el objeto que se resuelve no es solo un punto. Un hiperlabirinto estándar (o hiperlabirinto de primer orden) consiste en una línea que forma una superficie cuando se mueve a lo largo de un camino. El hiperlabirinto solo puede existir en 3D o en un medio con una dimensión más grande, y la entrada al hiperlabirinto a menudo no es un punto, sino una línea. Hyperlabyrinth es fundamentalmente diferente, porque es necesario tener en cuenta y trabajar simultáneamente con varias partes a lo largo de la línea, y en un momento dado hay un número casi infinito de estados y opciones para lo que se puede hacer con la línea. La línea de solución es infinita, o sus puntos finales están fuera del hiperlabirinto para evitar que la línea se comprima a un punto, porque en este caso puede considerarse un no hiperlabirinto.
- Hyper-hyperlabyrinth: hyperlabyrinths puede ser arbitrariamente alta dimensión. Hyper-hyperlabyrinth (o hyperlabyrinth de segundo orden) nuevamente aumenta la dimensión del objeto que se está resolviendo. Aquí, el objeto a resolver es un plano que, al moverse a lo largo del camino, forma una figura tridimensional. Hyper-hyperlabyrinth solo puede existir en un entorno dimensional 4D o superior.
Topología: la clase de topología describe la geometría del espacio laberíntico en el que existe en su conjunto. Los siguientes tipos están disponibles:
Normal : este es el laberinto estándar en el espacio euclidiano.
Planair : El término "planair" describe cualquier laberinto con una topología inusual. Por lo general, esto significa que los bordes del laberinto están conectados de una manera interesante. Ejemplos: laberintos en la superficie de un cubo, laberintos en la superficie de una tira de Mobius y laberintos equivalentes a aquellos en un toro donde los lados izquierdo y derecho, superior e inferior están conectados en pares.
Teselación: una clasificación de la geometría de las celdas individuales que componen el laberinto. Tipos existentes:
Ortogonal : esta es una cuadrícula rectangular estándar en la que las celdas tienen pasajes que se cruzan en ángulo recto. En el contexto de la teselación, también se les puede llamar laberintos gamma.
Delta : los laberintos Delta consisten en triángulos conectados, y cada celda puede tener hasta tres pasajes conectados.
Sigma : los laberintos Sigma están formados por hexágonos conectados; cada celda puede tener hasta seis pases.
Theta : los laberintos de Theta consisten en círculos concéntricos de pasajes en los que el principio o el final están en el centro y el otro en el borde exterior. Las celdas generalmente tienen cuatro rutas de conexión posibles, pero puede haber más debido a la mayor cantidad de celdas en los anillos exteriores de los pasillos.
Epsilon : los laberintos de Epsilon consisten en octágonos o cuadrados conectados, cada celda en ellos puede tener hasta ocho o cuatro pases.
Zeta : el laberinto zeta se encuentra en una cuadrícula rectangular, solo que además de los pasajes horizontales y verticales, se permiten pasajes diagonales en un ángulo de 45 grados.
Omega : el término omega se refiere a casi cualquier laberinto con teselación no ortogonal constante. Los laberintos delta, sigma, theta e ipsilon son de este tipo, como muchos otros esquemas en los que se puede pensar, por ejemplo, un laberinto que consiste en pares de triángulos en ángulo recto.
Grieta : un laberinto de grietas es un laberinto amorfo sin teselación constante, en el que las paredes y las pasarelas se ubican en ángulos aleatorios.
Fractal : un laberinto fractal es un laberinto formado por laberintos más pequeños. Un laberinto fractal de células anidadas es un laberinto en cada celda en el que se colocan otros laberintos, y este proceso puede repetirse varias veces. Un laberinto fractal infinitamente recursivo es un verdadero fractal en el que el contenido del laberinto se replica a sí mismo, creando un laberinto esencialmente infinitamente grande.
Enrutamiento: la clasificación por enrutamiento es probablemente el aspecto más interesante en la generación de laberintos. Desde está asociado con los tipos de pasadas dentro de la geometría definida en las categorías descritas anteriormente.
Ideal : "ideal" es un laberinto sin bucles o circuitos cerrados y sin áreas inalcanzables. También se llama un laberinto simplemente conectado. Desde cada punto hay exactamente un camino hacia cualquier otro punto. Labyrinth tiene solo una solución. Desde el punto de vista de la programación, dicho laberinto puede describirse como un árbol, un conjunto de celdas o vértices de conexión.
Trenzado : Trenzado significa que no hay callejones sin salida en el laberinto. También se llama el laberinto del laberinto puramente conectado. En tal laberinto, se usan pasajes que están cerrados y regresan entre sí (de ahí el nombre de "mimbre"), les hacen pasar más tiempo caminando en círculos en lugar de meterse en callejones sin salida. Un laberinto tejido de calidad puede ser mucho más complicado que un laberinto ideal del mismo tamaño.
Ruta única (Unicursal) : ruta única significa un laberinto sin tenedores. El laberinto unidireccional contiene un largo y sinuoso pasaje que cambia de dirección en todo el laberinto. No es muy complicado, solo si no retrocede accidentalmente hasta la mitad y no regresa al principio.
Escaso: un laberinto escaso no hace pases a través de cada celda, es decir, algunos de ellos no se crean. Esto implica la presencia de áreas inalcanzables, es decir, en cierto sentido, es lo opuesto al laberinto de mimbre. Se puede aplicar un concepto similar al agregar paredes, por lo que puede obtener un laberinto desigual con pasillos y habitaciones anchas.- Parcialmente mimbre: Parcialmente mimbre laberinto es un laberinto mixto que tiene bucles y callejones sin salida. La palabra "mimbre" se puede usar para la evaluación cuantitativa, es decir, un "laberinto con tejido fuerte" es un laberinto con muchos lazos o paredes removidos, y solo hay unos pocos en el "laberinto con tejido débil".
Textura: la clasificación de
textura describe el estilo de pases con diferentes enrutamiento y geometría. La textura no son solo parámetros que se pueden activar o desactivar. Aquí hay algunos ejemplos de variables:
Sesgo : en un laberinto con pasajes desplazados, los pasajes rectos tienden a ir más en una dirección que en otras. Por ejemplo, en un laberinto con un alto desplazamiento horizontal, tendremos pasajes largos de izquierda a derecha, y solo pasajes cortos de arriba a abajo que los conectan. Tal laberinto suele ser más difícil de pasar "a través de las fibras".
Sobrevuelo : la métrica Sobrevuelo determina cuánto tiempo tardarán los pasillos antes de que aparezcan los turnos forzados. En un laberinto con un tramo bajo, no habrá pasajes rectos de más de tres o cuatro celdas, y se verá muy al azar. En un laberinto con un tramo alto, el laberinto tendrá un gran porcentaje de pases largos, lo que lo hará parecer un microchip.
Elitismo: El indicador de " elitismo " del laberinto determina la longitud de la solución en relación con el tamaño del laberinto. Los laberintos de élite generalmente tienen una solución corta y directa, mientras que en los laberintos que no son de élite, la solución pasa sobre una gran parte del área del laberinto. Un laberinto de élite de alta calidad puede ser mucho más complicado que un laberinto que no sea de élite.
Simetría : un laberinto simétrico tiene pasos simétricos, por ejemplo, en la simetría de rotación relativa al centro, o reflejada a lo largo de los ejes horizontal o vertical. El laberinto puede ser parcial o completamente simétrico, y puede repetir el patrón varias veces.
Homogeneidad: un algoritmo homogéneo genera todos los laberintos posibles con la misma probabilidad. Se puede llamar a un laberinto que tiene una textura homogénea si se parece a un laberinto típico generado por un algoritmo homogéneo. En teoría, un algoritmo heterogéneo también puede generar todos los laberintos posibles en cualquier espacio, pero no con la misma probabilidad. La heterogeneidad puede ir aún más lejos: puede haber laberintos que el algoritmo nunca generará.- Flujo del río: la característica de "flujo" significa que al crear un laberinto, el algoritmo buscará y limpiará las celdas (o paredes) vecinas a la actual, es decir, fluirá (de ahí el término "fluidez") a las partes aún no creadas del laberinto, como el agua. En un laberinto ideal con una velocidad de flujo más baja, generalmente habrá muchos callejones sin salida cortos, y en un laberinto más "fluido" habrá menos callejones sin salida, pero serán más largos.
Prioridad: esta clasificación muestra que los procesos de creación de laberintos se pueden dividir en dos tipos principales: agregar paredes y tallar pasajes. Por lo general, al generar esto, se reduce solo a la diferencia en los algoritmos, y no a diferencias notables en los laberintos, pero aún es útil tener esto en cuenta. El mismo laberinto a menudo se genera de ambas maneras:
- Agregar muros: los algoritmos para los que los muros son una prioridad comienzan con un área vacía (o borde externo), agregando muros en el proceso. En el mundo real, los laberintos reales que consisten en setos, techos o paredes de madera definitivamente están agregando paredes.
- Corte de pasillos: los algoritmos cuya prioridad son los pasillos comienzan con un bloque sólido y cortan pasajes en el proceso. En el mundo real, tales laberintos son túneles de minas o laberintos dentro de tuberías.
Plantilla: por supuesto, los laberintos pueden cortar simultáneamente pasajes y agregar paredes; Algunos algoritmos informáticos hacen eso. Una plantilla de laberinto es una imagen gráfica que no es un laberinto, que en el menor número de pasos se convierte en un laberinto real, pero aún conserva la textura de la plantilla gráfica original. Los estilos complejos de laberinto, como las espirales de intersección, son más fáciles de implementar como patrones en una computadora, en lugar de tratar de crear el laberinto correcto mientras se conserva su estilo.
Otro: lo anterior no es una lista exhaustiva de todas las clases o elementos posibles dentro de cada clase. Estos son solo esos tipos de laberintos que yo mismo creé. Tenga en cuenta que casi todos los tipos de laberintos, incluidos los laberintos con reglas especiales, se pueden expresar como un gráfico dirigido en el que habrá un número finito de estados y un número finito de opciones en cada estado, y esto se llama
equivalencia de los laberintos . Aquí hay algunas otras clasificaciones y tipos de laberintos:
Orientación : en ciertos pasajes solo puedes moverte en una dirección. Desde el punto de vista de la programación, dicho laberinto se describirá mediante un gráfico dirigido, en contraste con un gráfico no dirigido que describe todos los demás tipos.
Segmentación : el laberinto puede tener diferentes partes correspondientes a diferentes clases.
Laberintos de longitud infinita: podemos crear un laberinto infinitamente largo (un número finito de columnas y cualquier número de filas), pero al mismo tiempo almacenamos solo una parte del laberinto en la memoria, "desplazándonos" de un extremo al otro y destruyendo las líneas anteriores al crear el siguiente. Un ejemplo es una versión modificada del algoritmo Hunt and Kill. Uno puede imaginar un laberinto potencialmente interminable en forma de una película larga compuesta de cuadros individuales. Solo dos cuadros consecutivos se almacenan en la memoria a la vez. Ejecutemos el algoritmo Hunt and Kill, aunque crea un sesgo que es propenso al marco superior, por lo que termina primero. Una vez completado, el marco ya no es necesario, puede imprimirlo o hacer algo más con él. Sea como fuere, deséchelo, convierta el cuadro inferior parcialmente creado en un nuevo cuadro superior y borre el nuevo cuadro inferior. Repita el proceso hasta que decidamos detener, y luego espere hasta que Hunt And Kill complete ambos fotogramas. La única limitación es que el laberinto nunca tendrá un camino que se bifurque hacia la entrada por una longitud de más de dos cuadros. La forma más fácil de crear un laberinto sin fin es el algoritmo Eller o el algoritmo Sidewinder, porque ya crean laberintos una línea a la vez, por lo que puede dejar que agreguen líneas sin fin al laberinto.
Laberintos fractales virtuales : virtual es un laberinto en el que todo el laberinto no se almacena en la memoria al mismo tiempo. Por ejemplo, solo puede almacenar parte de los pasillos de 100x100 cerca de su ubicación en una simulación en la que camina por un laberinto grande. La extensión de laberintos fractales anidados se puede utilizar para crear enormes laberintos virtuales, por ejemplo, mil millones por mil millones de pases. Si construimos una copia real del laberinto de mil millones por mil millones de pases (con una distancia de seis pies entre los pasajes), ¡entonces llenaría la superficie de la Tierra más de 6,000 veces! Considere un laberinto de 10 9 a 10 9 pases, o un laberinto cerrado con solo 9 niveles. Si queremos tener al menos una parte de 100x100 a nuestro alrededor, es suficiente para nosotros crear en el nivel más bajo un sub laberinto de 100x100 pases y siete laberintos de 10x10 en los que está incrustado para saber exactamente dónde están las paredes dentro de la parte de 100x100. (En realidad, es mejor tener cuatro partes adyacentes de tamaño 100x100, formando un cuadrado en caso de que esté cerca del borde o la esquina de la parte, pero el mismo concepto se aplica aquí.) Para garantizar que el laberinto sea constante y sin cambios cuando se mueva alrededor de él, tenemos una fórmula, definiendo un número de semilla aleatorio para cada coordenada en cada nivel de anidación. Los laberintos fractales virtuales son similares al fractal de Mandelbrot, en cuyas imágenes existe virtualmente, y necesitamos visitar cierta coordenada con un aumento bastante alto. para que aparezca.
Algoritmos de laberinto
Aquí hay una lista de algoritmos generalizados para crear las diversas clases de laberintos descritos anteriormente:
Ideal : para crear un laberinto ideal estándar, generalmente es necesario "cultivarlo", asegurando la ausencia de bucles y áreas aisladas. Comenzamos desde el muro exterior y agregamos aleatoriamente un fragmento del muro que lo toca. Continuamos agregando aleatoriamente segmentos de muro al laberinto, pero nos aseguramos de que cada nuevo segmento toque un extremo del muro existente, y su otro extremo esté en la parte aún no creada del laberinto. Si agrega un segmento de pared, cuyos extremos están separados del resto del laberinto, esto creará una pared no conectada con un bucle alrededor, y si agrega un segmento, cuyos extremos tocan el laberinto, creará un área inalcanzable. Este es un método para agregar muros; es casi análogo a cortar pasajes, en los cuales partes de los pasajes se cortan de modo que solo un extremo toque el pase existente.
: , , . : (1) , (2) , , -«», (3) , , , (4) , , (3) , , .
: — , , , , . U- , , , , . . , : , , , . , . , .
: , . , , . - , , , , .- 3D : , , , . - .
: , , . ( ): , , , . , . , ; , . , , .
Crack : Crack- , , . , , , «» . , , . , - . , , ; . , .
: «» , , . , - : (1) , . (2) , , , , , (.. ). (3) , , . , .
: — 3D-, -, , . 3D- , , . , , . , . , ( ), , , .
Planair : Planair- , . — . , .
: , , , -, , , , . , . , , , , , .
Hay muchas formas de crear laberintos perfectos, y cada uno de ellos tiene sus propias características. A continuación se muestra una lista de algoritmos específicos. Todos ellos describen la creación de un laberinto cortando pasajes, sin embargo, a menos que se indique lo contrario, cada uno también puede implementarse agregando paredes:
Rastreador recursivo : - recursive backtracker, , . , , . , , . , . , . , , , . , . Recursive backtracking , , , .
: , . , «» , , . , , ( ). , . , , . , - , , . , , . , . , - (union-find algorithm): , . . , - .
Algoritmo de Prim (verdadero) : este algoritmo crea un árbol de expansión mínimo al procesar pesos de borde únicos al azar. La cantidad de memoria requerida es proporcional al tamaño del laberinto. Comenzamos desde cualquier vértice (el laberinto terminado será el mismo, no importa desde la parte superior que comencemos). Seleccionamos el borde del pasaje con el menor peso conectando el laberinto a un punto que aún no está en él, y luego lo conectamos al laberinto. El laberinto se completa cuando los bordes en cuestión ya no quedan. Para seleccionar eficientemente el siguiente borde, necesita una cola prioritaria (generalmente implementada usando un montón) que almacena todos los bordes del borde. Sin embargo, este algoritmo es bastante lento porque lleva tiempo de registro (n) seleccionar elementos del montón. Por lo tanto, es mejor preferir el algoritmo de Kraskal, que también crea un árbol de expansión mínimo, porque es más rápido y crea laberintos con una estructura idéntica. De hecho, con la misma semilla aleatoria, los algoritmos Prima y Kraskal pueden crear los mismos laberintos.
Algoritmo de Prim (simplificado) : este algoritmo de Prim crea un árbol de expansión mínimo. Se simplifica de tal manera que todos los pesos de los bordes son iguales. Requiere una capacidad de memoria proporcional al tamaño del laberinto. Partimos de un pico aleatorio. Seleccionamos al azar el borde del pasaje que conecta el laberinto con un punto que aún no está en él, y luego lo conectamos al laberinto. El laberinto se completa cuando los bordes en cuestión ya no quedan. Como los bordes no tienen peso y no están ordenados, se pueden almacenar como una lista simple, es decir, la selección de elementos de la lista será muy rápida y tomará un tiempo constante. Por lo tanto, es mucho más rápido que el verdadero algoritmo Prim con pesos de arista aleatorios. La textura del laberinto creado tendrá una velocidad de flujo más baja y una solución más simple que el verdadero método Prim, ya que se extiende desde el punto de partida de manera uniforme, como el jarabe derramado, y no evita los fragmentos de costillas con un peso mayor, que se tienen en cuenta más adelante.
Algoritmo de Prim (modificado) : este algoritmo de Prim crea un árbol de expansión mínimo, modificado para que todos los pesos de los bordes sean iguales. Sin embargo, se implementa de tal manera que en lugar de bordes mira las celdas. La cantidad de memoria es proporcional al tamaño del laberinto. En el proceso de creación, cada celda puede tener uno de tres tipos: (1) "interna": la celda es parte del laberinto y ya está cortada en ella, (2) "límite": la celda no es parte del laberinto y aún no ha sido cortada, pero está ubicada junto a una celda que ya es "interna", y (3) "externa": la celda aún no es parte del laberinto, y ninguno de sus vecinos es también una celda "interna". Comenzamos eligiendo una celda, la hacemos "interna" y para todos sus vecinos establecemos el tipo en "límite". Seleccionamos al azar la celda "límite" y cortamos un pasaje de una de las celdas "internas" vecinas. Cambiamos el estado de esta celda "límite" a "interno" y cambiamos el tipo de todos sus vecinos de "externo" a "borde". El laberinto se completa cuando no quedan más celdas "límite" (es decir, no quedan celdas "externas", lo que significa que todos se han vuelto "internos"). Este algoritmo crea laberintos con un índice de rendimiento muy bajo, tiene muchos puntos muertos cortos y una solución bastante sencilla. El laberinto resultante es muy similar al resultado del algoritmo Prima simplificado, con una ligera diferencia: los vacíos en el árbol de expansión se llenan solo si se selecciona aleatoriamente una celda límite, en contraste con la triple probabilidad de llenar esta celda a través de una de las celdas límite que la conducen. Además, el algoritmo es muy rápido, más rápido que el algoritmo Prim simplificado, ya que no necesita compilar y procesar la lista de bordes.
Algoritmo de Aldous-Broder : lo interesante de este algoritmo es que es homogéneo, es decir, crea con la misma probabilidad todos los laberintos posibles de un tamaño determinado. Además, no requiere memoria adicional o una pila. Seleccionamos un punto y nos movemos aleatoriamente a una celda vecina. Si nos metimos en una celda sin cortar, corta el pasaje de la celda anterior. Continuamos moviéndonos a las celdas vecinas hasta que cortamos los pasajes a todas las celdas. Este algoritmo crea laberintos con un caudal bajo, solo un poco más alto que el algoritmo de Kraskal. (Esto significa que para un intercambio dado, hay más laberintos con un índice de rendimiento bajo que con uno alto, porque el laberinto con una probabilidad promedio es igualmente bajo). Lo malo de este algoritmo es que es muy lento porque no realiza una búsqueda intelectual de este último. es decir, las células, de hecho, no tienen garantías de finalización. Sin embargo, debido a su simplicidad, puede pasar rápidamente por muchas celdas, por lo que se completa más rápido de lo que parece. En promedio, tarda siete veces más en completarse que los algoritmos estándar, aunque en casos malos puede ser mucho más largo si el generador de números aleatorios evita constantemente las últimas celdas. Se puede implementar como la adición de muros, si el muro del borde se considera un solo vértice, es decir, si el movimiento nos mueve al muro del borde, nos teletransportamos a un punto aleatorio a lo largo del borde, y solo entonces continuamos moviéndonos. En el caso de agregar paredes, funciona casi el doble de rápido, porque la teletransportación a lo largo del muro fronterizo permite un acceso más rápido a las partes más alejadas del laberinto.
Algoritmo de Wilson : esta es una versión mejorada del algoritmo Aldous-Broder, crea laberintos con exactamente la misma textura (los algoritmos son homogéneos, es decir, todos los laberintos posibles se generan con la misma probabilidad), pero el algoritmo Wilson es mucho más rápido. Lleva memoria hasta el tamaño del laberinto. Comenzamos con una celda de laberinto inicial seleccionada al azar. Seleccionamos una celda aleatoria que aún no es parte del laberinto y realizamos una caminata aleatoria hasta que encontremos una celda que ya pertenece al laberinto. Tan pronto como nos topamos con la parte ya creada del laberinto, volvemos a la celda aleatoria seleccionada y cortamos todo el camino realizado agregando estas celdas al laberinto. Más específicamente, cuando regresamos a lo largo del camino, cortamos cada celda en la dirección en la que se realizó la caminata aleatoria la última vez que salimos de la celda. Esto evita la aparición de bucles a lo largo del camino de retorno, de modo que un largo pasaje se une al laberinto. El laberinto se completa cuando todas las células están unidas a él. El algoritmo tiene los mismos problemas de velocidad que Aldous-Broder, porque puede llevar mucho tiempo encontrar la primera ruta aleatoria a la celda inicial, pero después de colocar varias rutas, el resto del laberinto se corta con bastante rapidez. En promedio, funciona cinco veces más rápido que Aldous-Broder, y menos de dos veces más lento que los mejores algoritmos. Vale la pena considerar que, en el caso de agregar paredes, funciona el doble de rápido, ya que toda la pared del borde es inicialmente parte del laberinto, por lo que las primeras paredes se unen mucho más rápido.
Algoritmo Hunt and kill : este algoritmo es conveniente porque no requiere memoria adicional o una pila, y por lo tanto es adecuado para crear laberintos o laberintos enormes en computadoras débiles debido a la imposibilidad de quedarse sin memoria. Como no tiene reglas que deban seguirse constantemente, también es más fácil modificar y crear laberintos con diferentes texturas. Es casi similar a un rastreador recursivo, solo que no hay una celda no creada cerca de la posición actual. Entramos en el modo de "búsqueda" y escaneamos sistemáticamente el laberinto hasta encontrar una celda no creada al lado de la celda ya cortada. En esta etapa, nuevamente comenzamos a cortar en esta nueva ubicación. El laberinto se completa cuando en el modo "caza" se escanean todas las celdas. Este algoritmo tiende a crear laberintos con una velocidad de flujo alta, pero no tan alta como el rastreador recursivo. Puede forzarlo a generar laberintos con una velocidad de flujo más baja, entrando con mayor frecuencia en el modo "caza". Funciona más lento debido al tiempo dedicado a buscar las últimas celdas, pero no mucho más lento que el algoritmo de Kraskal. Se puede implementar de acuerdo con el principio de agregar muros, si ocasionalmente se teletransporta al azar para evitar los problemas inherentes a un rastreador recursivo.
Algoritmo de crecimiento
árbol (algoritmo de árbol en crecimiento) : este es un algoritmo generalizado que puede crear laberintos con diferentes texturas. La memoria requerida puede alcanzar el tamaño del laberinto. Cada vez que se corta una celda, la agregamos a la lista. Seleccione una celda de la lista y recorte el pasaje a la celda no creada al lado. Si no hay celdas sin crear cerca de la actual, elimine la celda actual de la lista. El laberinto se completa cuando no hay nada más en la lista. Lo interesante del algoritmo es que, dependiendo de cómo seleccione una celda de la lista, puede crear muchas texturas diferentes. Por ejemplo, si siempre selecciona la última celda agregada, este algoritmo se convierte en un rastreador recursivo. Si siempre selecciona celdas al azar, entonces se comporta de manera similar, pero no de manera idéntica al algoritmo Prim. Si siempre selecciona las celdas más antiguas agregadas a la lista, crearemos un laberinto con el índice de rendimiento más bajo posible, incluso más bajo que el del algoritmo Prim. Si generalmente elige la última celda, pero ocasionalmente elige una celda aleatoria, entonces el laberinto tendrá una velocidad de flujo alta, pero una solución corta y directa. Si se selecciona al azar una de las celdas más recientes, el laberinto tendrá un caudal bajo, pero una solución larga y sinuosa.
Algoritmo de bosque en crecimiento : este es un algoritmo más generalizado que combina tipos basados en árboles y conjuntos. Es una extensión del algoritmo de crecimiento de árboles, que esencialmente incluye varias instancias que se expanden simultáneamente. Comenzamos con todas las celdas ordenadas aleatoriamente en una lista de "nuevo"; Además, cada celda tiene su propio conjunto, como al comienzo del algoritmo de Kruskal. Primero, seleccione una o más celdas moviéndolas de la lista de "nuevo" a la lista de "activo". Seleccione una celda de la lista "activa" y recorte el pasaje a la siguiente celda no creada de la lista "nueva", agregue una nueva celda a la lista de "activos" y combine los conjuntos de dos celdas. Si se intenta cortar la parte existente del laberinto, habilítelo si las celdas están en conjuntos diferentes y combine las celdas, como se hace en el algoritmo de Kraskal. Si no hay celdas "nuevas" cerca de la celda actual, mueva la celda actual a la lista de las "terminadas". El laberinto se completa cuando la lista de "activos" se vacía. Al final, combinamos todos los conjuntos restantes, como en el algoritmo de Kruskal. Periódicamente, puede crear nuevos árboles moviendo una o más celdas de la lista de "nuevos" a la lista de "activos", como se hizo al principio. Al controlar el número de árboles originales y las partes compartidas de los árboles recién creados, puede generar muchas texturas únicas que se combinan con los parámetros ya flexibles del algoritmo de crecimiento de árboles.
Algoritmo de Eller : este es un algoritmo especial, porque no solo es más rápido que todos los demás, sino que tampoco tiene sesgos o defectos obvios; Además, cuando se crea, la memoria se utiliza de manera más eficiente. Ni siquiera requiere que todo el laberinto esté en la memoria, usa un volumen proporcional al tamaño de la línea. Crea un laberinto línea por línea, después de que se completa la generación de la cadena, el algoritmo ya no lo tiene en cuenta. Cada celda en una fila está contenida en un conjunto; dos celdas pertenecen al mismo conjunto si hay una ruta entre ellas a lo largo del laberinto ya creado. Esta información le permite cortar pasajes en la línea actual sin crear bucles o áreas aisladas. De hecho, es bastante similar al algoritmo de Kraskal, solo que aquí se forma una línea a la vez, mientras que Kraskal mira a través de todo el laberinto. La creación de una fila consta de dos partes: conectar aleatoriamente celdas adyacentes dentro de la fila, es decir cortamos pasajes horizontales, luego conectamos aleatoriamente las celdas entre la fila actual y la siguiente, es decir cortar pasajes verticales. Al cortar pasajes horizontales, no conectamos celdas que ya están en el mismo conjunto (porque de lo contrario se creará un bucle), y al cortar pasajes verticales debemos conectar una celda si tiene un tamaño de unidad (porque si la deja, creará un área aislada). Al cortar pasajes horizontales, conectamos celdas si están en el mismo conjunto (porque ahora hay un camino entre ellas), y al cortar pasajes verticales cuando no nos conectamos con la celda, lo colocamos en un conjunto separado (porque ahora está separado del resto del laberinto ) La creación comienza con el hecho de que antes de conectar las celdas en la primera fila, cada celda tiene su propio conjunto. La creación se completa después de que las celdas se conectan en la última fila. Hay una regla especial de finalización: en el momento de la finalización, cada celda debe estar en el mismo conjunto para evitar áreas aisladas. (La última línea se crea combinando cada uno de los pares de celdas vecinas que aún no están en el mismo conjunto). Es mejor implementar el conjunto utilizando una lista cíclica de celdas doblemente enlazadas (que puede ser solo una matriz que une celdas a pares de celdas en ambos lados del mismo conjunto), permitiendo Realizar la inserción, eliminación y verificación de la presencia de células vecinas en un conjunto durante un tiempo constante. El problema con este algoritmo es el desequilibrio en el procesamiento de los diferentes bordes del laberinto; Para evitar manchas en las texturas, debe conectar y omitir las celdas de conexión en las proporciones correctas.
División recursiva: este algoritmo es algo similar al retroceso recursivo, porque ambos usan pilas, solo que no funciona con pasillos, sino con paredes. Comenzamos creando una pared horizontal o vertical aleatoria que intersecta un área accesible en una fila o columna aleatoria, y coloca aleatoriamente espacios vacíos a lo largo de ella. Luego repetimos recursivamente el proceso para las dos subregiones generadas por la pared divisoria. Para obtener los mejores resultados, debe agregar una desviación en la elección de horizontal o vertical en función de las proporciones del área, por ejemplo, un área cuyo ancho es el doble de la altura debería dividirse más a menudo por paredes verticales. Este es el algoritmo más rápido sin desviaciones en las direcciones, y a menudo incluso puede competir con laberintos basados en árboles binarios, porque crea varias celdas al mismo tiempo, aunque tiene un inconveniente obvio en forma de paredes largas que se cruzan en el interior del laberinto. Este algoritmo es un tipo de laberintos fractales incrustados, pero en lugar de crear constantemente laberintos de celdas de un tamaño fijo con laberintos del mismo tamaño dentro de cada celda, divide aleatoriamente un área dada en un laberinto de tamaño aleatorio: 1x2 o 2x1. La división recursiva no se puede utilizar para cortar pasajes, ya que esto lleva a la creación de una solución obvia que sigue a lo largo del borde exterior o que, de lo contrario, se cruza directamente con el interior.
Laberintos basados en árboles binarios : de hecho, estos son los algoritmos más simples y rápidos posibles, sin embargo, los laberintos creados tienen una textura con un sesgo muy alto. Para cada celda, cortamos un pasaje hacia arriba o hacia la izquierda, pero nunca en ambas direcciones. En la versión con la adición de paredes, se agrega un segmento de pared para cada vértice que conduce hacia abajo o hacia la derecha, pero no en ambas direcciones. Cada celda es independiente de todas las demás celdas, porque no necesitamos verificar el estado de algunas otras celdas al crearla. Por lo tanto, este es un algoritmo real para generar laberintos sin memoria, no limitado por el tamaño de los laberintos creados. De hecho, este es un árbol binario, si consideramos la esquina superior izquierda como una raíz, y cada nodo o celda tiene un nodo primario único, que es una celda en la parte superior o izquierda. Los laberintos basados en árboles binarios son diferentes de los laberintos ideales estándar, porque más de la mitad de los tipos de células no pueden existir en ellos. Por ejemplo, nunca habrá intersecciones en ellos, y todos los callejones sin salida tienen pasajes que conducen hacia arriba o hacia la izquierda, y nunca hacia abajo o hacia la derecha. Los laberintos tienden a tener pasajes que conducen diagonalmente desde la esquina superior izquierda a la esquina inferior derecha, y es mucho más fácil moverse de la parte inferior derecha a la esquina superior izquierda. Siempre puede moverse hacia arriba o hacia la izquierda, pero nunca simultáneamente en ambas direcciones, por lo que siempre puede moverse de manera determinista diagonalmente hacia arriba y hacia la izquierda, sin encontrar barreras. Tendrá la oportunidad de elegir y caer en callejones sin salida moviéndose hacia abajo y hacia la derecha. , , , .
Sidewinder: , . : , , . , , , , , . , ( , ). , sidewinder . , sidewinder . , sidewinder , , . sidewinder , « ». , sidewinder — , , , , . sidewinder , , , .
| % | | | ? | ? | | | % |
| 0 0 | | | | | N^2 | 379 | 100.0 |
| Recursive Backtracker | 10 | | | | | N^2 | 27 | 19.0 |
| Hunt and Kill | 11 (21) | | | | | 0 0 | 100 (143) | 9.5 (3.9) |
| 23 | | | | | N* | 10 | 7.2 |
| 25 | | | | | 0* | 10 | 2.0 |
| Sidewinder | 27 | | | | | 0* | 12 | 2.6 |
| 28 | | | | | N* | 20 | 4.2 (3.2) |
| 29 | | | | | N^2 | 48 (25) | 4.5 4.5 |
| - | 29 | | | | | 0 0 | 279 (208) | 4.5 4.5 |
| 30 | | | | | N^2 | 33 | 4.1 |
| () | 30 | | | | | N^2 | 160 | 4.1 |
| () | 32 | | | | | N^2 | 59 | 2.3 |
| () | 36 (31) | | | | | N^2 | 30 | 2.3 |
| 49 (39) | | | | | N^2 | 48 | 11.0 |
| 49 (39) | | | | | N^2 | 76 | 11.0 |
Esta tabla resume las características de los algoritmos para crear laberintos ideales descritos anteriormente. A modo de comparación, se ha agregado un algoritmo de laberinto de ruta única (teóricamente, los laberintos de ruta única son ideales). Explicación de columna:- : , , , 2D-. . , , , . 10% ( ) 49% ( ). Recursive Backtracker 1%. 66%: .
- : : , , . , , , , . , , .
- : , . . , , . Recursive Backtracker , , , . , , . , Hunt and Kill , , .
- : , . , . Sidewinder , . , . Hunt and Kill , , , .
- : . «» , . «» , , . «» , , . , .
- : , . , , (N), (N^2). , ( ). , , . Sidewinder , . , .
- : , , , . , ( 10), . 100x100 Daedalus. , , , .
- : , , . , 100x100 . . «» . , . , . , , , .
Hay muchas formas de resolver laberintos, y cada uno de ellos tiene sus propias características. Aquí hay una lista de algoritmos específicos:
Siguiendo a lo largo de las paredes (seguidor de la pared) : . («»), . ( ). , ( ) . , . , , . , , , . 3D- , 3D- 2D-, .. , -, -, .
: , «» , . 2D- , , .. . , , . . , , . , , . , , . , , — -1, — 1. , , .. 360 , «». , «», , , , , . , , . , — , .
: (Chain algorithm) , ( ) . , , . , . , , . , . ( ) , . . , , . «» , . , , , . , . , .
Recursive backtracker: , . , . : ( ), «», , , «», , . , , «»; «» . (backtracking) , , . , . , , .
(Trémaux's algorithm): . recursive backtracker : , . , . , , . , , , . ( , .) , (.. ), , , , (.. , ). , , , , , . , . , , .
(Dead end filler) : . , . , , . , . , , . , , .
Cul-de-sac filler : , , . dead end filler, , . ( — , , ) , . dead end filler. , , , , . , , , dead end filler.
Blind alley filler : , , . , . — , , . , , cul-de-sac filler, . . , , , , . , , , ( ). , , . , cul-de-sac filler - , collision solver , - .
Blind alley sealer : blind alley filler , , . . . , , blind alley filler, . . , , , , . , , . , . , , . , , .
(Shortest path finder): , , . , , . collision solver, , , «» , ( ), «» , , . «», , . , - , . , , , A* , .
(Shortest paths finder) : , . , , , , , , , - , . , , , «» , , , . , , , , . , .- Collision solver: "amoeba" solver. . , . «» , ( ). « » ( ), , . «», , , , . ( , «», . , , , .) , shortest paths finder, ( ) ( ).
- Random mouse: , , .. , . 180 , . , , . , , .
| | ? | | ? | ? | ? | ? |
| Random Mouse | 1 | | | / | | | |
| Wall Follower | 1 | | | / | | | |
| 1 | | | / | | | |
| 1 | | + | | | | |
| Rastreador recursivo | 1 | Si | Usted es | No | Si | No | Si |
| Algoritmo de Tremo | 1 | Si | Usted es | Dentro / sobre | No | No | Si |
| Relleno de callejón sin salida | Todos + | No | Laberinto | Sobre | No | Si | Si |
| Relleno de callejón sin salida | Todos + | No | Laberinto | Sobre | No | Si | Si |
| Sellador de callejones sin salida | Todos + | Si | Laberinto | No | No | No | Si |
| Relleno de callejón sin salida | Todos | Si | Laberinto | Sobre | No | Si | No |
| Solucionador de colisiones | Todo más corto | Si | Usted + | No | No | No | Si |
| Busca los caminos más cortos | Todo más corto | Si | Usted + | No | Si | No | Si |
| Busca el camino más corto | 1 más corto | Si | Usted + | No | Si | No | Si |
Esta tabla enumera brevemente las características de los algoritmos de resolución de laberintos descritos anteriormente. De acuerdo con estos criterios, es posible clasificar y evaluar algoritmos para resolver laberintos. Explicaciones de columna:- : , . . , () . Dead end filler cul-de-sac filler ( blind alley sealer ) , , , «+».
- : . Random mouse «», , wall follower «», , . dead end filler cul-de-sac filler «», .
- : : «» ( ) . , ( «») («+») . , .
- : , , . , «», , ( ), , , , . .
- : . , , , , . Wall follower, . Recursive backtracker shortest path(s) finder .
- : . .
- Rápido: el proceso de decisión se considera rápido. Los algoritmos más eficientes son suficientes para mirar cada celda del laberinto solo una vez, o pueden omitir completamente partes de él. El tiempo de ejecución debe ser proporcional al tamaño del laberinto, u O (n ^ 2), donde n es el número de celdas a lo largo de un lado. El mouse aleatorio es lento porque su finalización no está garantizada, y el relleno de callejón sin salida resuelve potencialmente el laberinto de cada bifurcación.
Otras operaciones con laberintos.
Además de crear y resolver laberintos, puede realizar otras operaciones con ellos:
: « », , Fill FloodFill. FloodFill , , . , , FloodFill , . , , FloodFill , , . «» .
(Isolation remover): , , . , . , . ( , ) , . , , . .
: , , . , , . , . ( , ) . , , , . , .
: , . , , , , . , , . , . , blind alley sealer ( , ). , , .
- Daedalus : Daedalus, Windows. Daedalus .