Algorithms for 3D Mazes

Question

Are there algorithms for creating three-dimensional mazes? Essentially the same as the 2D maze, but can the Z axis be traversed? The idea still remains the same as for the beginning from beginning to end. Can backtracking be used?

What algorithm should I use to create a 3D maze?

See here . I mean, you can also go to the cube, and not just sort out his faces.

Answer 1

I made 2d mazes several years ago using the Kruskal algorithm here . There should be no reason for this not to work with the three-dimensional case you described. Basically, you consider a cell as a cube and have a large array that has (for each cell) 6 walls in the directions +/- x, y and z. The algorithm initially starts from all walls everywhere and randomly causes the walls to disappear until each cell in the maze is connected.

Answer 2

I have code for creating a 2D maze, of all things, RPGLE (something that I did as an independent exercise in learning the language). Due to the way I wrote this, the only changes needed for the general algorithm would be to add the size Z as an extra dimension ...

It's all about 20 pages (although this includes input / output), so here is the code. You must translate this into any language you need: I translated it from the BASIC spaghetti code ( goto was used here, yes, but it was a fun exercise).

 //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); 

All this is supported by two two-dimensional arrays (well, the equivalent of RPG): one for walls that occupy a "square", and the other for whether or not this square is visited. A maze is created after visiting each square. Garuanteed is only one way, a worm-queue maze.

To make it three-dimensional, make it use three-dimensional arrays and add the required dimensional index.

Answer 3

I developed an algorithm some time ago for 2D labyrinths on a square grid, there is no reason why this should not work for a 3D labyrinth on a cubic grid either.

---

Start with a three-dimensional grid, originally completely filled with wall cells.

...

Launch the agent at the edge of the grid, the agent moves in a straight line on the cleaning wall X, Y, Z, -X, -Y or -Z as it moves.

Action 'N' has a small chance at every step.

The “M” action occurs when the cell immediately in front of the agent is a wall and the cell in front of it is empty.

'N' - random selection:

• removal of this agent
• 90 degrees left or right
• and creating an agent on the same square, rotated 90 degrees to the left, right, or both (two agents).

'M' - random selection:

4. removal of this agent
5. removing a wall in front of this agent and removing this agent
6. and do nothing while continuing
7. Rotate left or right 90 degrees.
8. and creating an agent on the same square, rotated 90 degrees to the left, right, or both (two agents).

   ---

The labyrinths differ from each other, and their character is very flexible, adjusting the trigger for “M” (for actual compounds) and also changing the chances from 1 to 8. You can delete an action or two or enter your own actions, for example one, to make a small cleaning or bypassing one step.

A trigger for “N” can also be another kind of randomness, for example, the example below can be used to create fairly branched mazes that still have several long straight parts.

 float n = 1; while (random_0_to_1 > 0.15) { n *= 1.2; } return (int)n; 

---

Some minor adjustments will be required from my simple description, for example, a trigger for action “M” will have to check cells adjacent to cells, which it also checks, depending on which connections are desired.

In order for the labyrinth to contain cycles, 5 or 6 are required, and for the labyrinth to contain dead spots, at least one alternative action of "M" on 5 and 6 is required.

Some chances / actions and “M” triggers will tend to make labyrinths that do not work, such as unsolvable or full of empty or wall cells, but many of them will get consistently nice results.