Algoritmos para laberintos 3D

Question

¿Existen algoritmos para producir laberintos tridimensionales? Esencialmente lo mismo que un laberinto 2D, pero el eje de profundidad Z se puede atravesar? La idea sigue siendo la misma, para llegar de principio a fin. ¿Se podría seguir rastreando?

¿Qué algoritmo debo usar para generar un laberinto 3D?

Ver here. Quiero decir que también puedes ir al cubo, no solo iterar las caras del mismo.

Answer 1

Hice 2d laberintos hace unos años usando el algoritmo de Kruskal here. No debería haber ninguna razón para que esto no funcione con el caso 3d que describió. Básicamente, considerarías una celda como un cubo y una gran matriz que tiene (para cada celda), 6 paredes en las direcciones +/- x, y, z. El algoritmo inicialmente comienza con todas las paredes en todas partes y al azar hace que las paredes desaparezcan hasta que todas las celdas del laberinto estén conectadas.

Answer 2

Tengo el código para generar un laberinto en 2D, en todo, RPGLE (algo que hice como auto-ejercicio mientras aprendía el idioma). Debido a la forma en que lo escribí, los únicos cambios necesarios para el alogrithm general serían agregar la dimensión Z como una dimensión adicional ...

Todo el asunto tiene 20 páginas (aunque esto incluye entrada/salida) , así que aquí está algún código. Deberías poder traducir esto al lenguaje que necesites: lo traduje del código de espagueti BASIC (goto s se usaron demasiado aquí, sí. Pero fue un ejercicio divertido).

//set out maximum maze size 
maximumMazeSquareCounter = mazeHorizontalSize * mazeVerticalSize + 1; 
// generate a starting horizontal positiongetRandomNumber(seed : randomNumber); 
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1; 
currentVerticalPosition = 1; 
mazeSquareCounter = 1; 
// generate the top row of the maze (with entrance) 
mazeTopRow = generateEntrance(currentHorizontalPosition); 
//write to the printer file 
writeMazeDataLine(mazeTopRow); 
mazeSquareCounter += 1; 
//set the first position in the maze(the entry square 
setPathPoint(currentHorizontalPosition : currentVerticalPosition); 
//do until we've reached every square in the maze 
dou mazeSquareCounter >= maximumMazeSquareCounter; 
//get the next available random direction 
mazeDirection = getNextRandomDirection(getNextAvailableDirection(currentHorizontalPosition : currentVerticalPosition)); 
//select what to do by the returned results 
select; 
//when FALSE is returned - when the maze is trapped 
when mazeDirection = FALSE; 
//if not at the horizontal end of the maze 
if currentHorizontalPosition <> mazeHorizontalSize; 
//add one to the position 
currentHorizontalPosition += 1; 
//else if not at the vertical end of the maze 
elseif currentVerticalPosition <> mazeVerticalSize; 
//reset the horizontal position 
currentHorizontalPosition = 1; 
//increment the vertical position 
currentVerticalPosition += 1; 
//otherwise 
else; 
//reset both positions 
currentHorizontalPosition = 1; 
currentVerticalPosition = 1; 
endif; 
//when 'N' is returned - going up (other directions removed) 
when mazeDirection = GOING_NORTH; 
//set the point above current as visited 
setPathPoint(currentHorizontalPosition : currentVerticalPosition - 1); 
//set the wall point to allow passage 
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_NORTH); 
//change the position variable to reflect change 
currentVerticalPosition -= 1; 
//increment square counter 
mazeSquareCounter += 1; 
endsl; 
enddo; 
//generate a random exit 
// get a random number 
getRandomNumber(seed : randomNumber); 
// set to the horzontal position 
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1; 
//set the vertical position 
currentVerticalPosition = mazeVerticalSize; 
//set wall to allow for exit 
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_SOUTH); 

Todo el asunto está respaldado por dos matrices bidimensionales (así, el juego de rol equivalentes): Uno de los muros que ocupan el 'cuadrado', y el otro para si o no esa plaza ha sido visitado. El laberinto se crea después de que cada cuadrado ha sido visitado. Garuante solo en un camino, laberinto de gusanos.

Para que esto sea tridimensional, hágalo utilizando matrices tridimensionales y agregue el índice de dimensión necesario.

Answer 3

Diseñé un algoritmo hace algún tiempo para laberintos 2D en una cuadrícula, no hay ninguna razón por la que esto tampoco debería funcionar para un laberinto 3D en una cuadrícula cúbica.

---

Comience con una cuadrícula 3D inicialmente completamente poblada con celdas de pared.

...

Start un agente en un borde de la red, el agente se desplaza en una línea recta en la X, Y, Z, -X, -Y o en la pared de compensación dirección -Z mientras viaja .

Acción 'N' tiene una pequeña posibilidad de aparecer en cada paso.

La acción 'M' ocurre cuando la celda directamente en frente del agente está en la pared y la celda que está delante está vacía.

'N' es una elección aleatoria de:

1. eliminación de ese agente
2. girando a la izquierda o derecha 90 grados
3. y la creación de un agente en el mismo cuadrado gira 90 grados a la izquierda, a la derecha o ambos (dos agentes).

'M' es una elección aleatoria de:

4. la eliminación de ese agente
5. la eliminación de la pared frente a ese agente y luego la eliminación de ese agente
6. y sin hacer nada, llevando a cabo
7. girando a la izquierda o 90 grados a la derecha.
8. y crear un agente en el mismo cuadrado girado 90 grados a la izquierda, a la derecha o ambos (dos agentes).

---

los laberintos son distintivos, y su carácter es muy flexible mediante el ajuste del disparador de 'M' (que ver con uniones válidas) y por ajustar también las posibilidades de 1 a 8 que se produzcan. Es posible que desee eliminar una o dos acciones o introducir sus propias acciones, por ejemplo, una para hacer un pequeño claro o dar un paso atrás.

El activador para 'N' también puede ser otro tipo de aleatoriedad, por ejemplo, el siguiente ejemplo se puede utilizar para crear laberintos bastante ramificados que todavía tienen algunas partes rectas largas.

float n = 1; 

while (random_0_to_1 > 0.15) 
{ 
    n *= 1.2; 
} 

return (int)n; 

---

algunos pequeños ajustes serán necesarios a partir de la descripción de mi sencilla, por ejemplo disparador para la acción 'M' tendrá que comprobar las células adyacentes a las células comprueba así, dependiendo de qué tipo de uniones son deseable.

Se necesitan 5 o 6 para que el laberinto contenga ciclos y se requiere al menos una acción alternativa 'M' para 5 y 6 para que el laberinto contenga callejones sin salida.

Algunas opciones de posibilidades/acciones y desencadenantes 'M' tenderán a hacer laberintos que no funcionan, por ejemplo, son irresolubles o están llenos de células vacías o de pared, pero muchos producirán buenos resultados consistentemente.