I would like to implement the generation of a three-dimensional maze, something like this

picture

Nothing good was found on this topic. Does anyone have any ideas on this topic?

  • As there is no desire to go to unknown links. Describe what this labyrinth is and what developments you already have. Based on this, it will be possible to help you. In addition, links from the outside often "die" - the question will be just rubbish and no one will benefit from it. - V.March
  • it's just a picture. Well, look, there are 2 dimensional labyrinths and the algorithms for their generation are complete: en.wikipedia.org/wiki/Maze_generation_algorithm Look in the Google 3d maze puzzle, there are pictures of puzzles with such mazes. - JacksonFaller
  • Well, aren't the algorithms the same? - vp_arth

2 answers 2

To begin with, let's decide what the maze is, i.e. We give the first definition of a labyrinth, which we subsequently modify slightly. I will consider the two-dimensional case. Three-dimensional in all its variations is constructed exactly the same.

Definition A maze on a plane will be called a connected undirected graph without loops, each vertex of which has no more than 4 edges.

It is quite easy to draw an analogy of the nxm grid-labyrinth and the labyrinth. How to do it? It is enough to look at the cell and notice that each cell has 4 neighbors (we don’t take boundary cases):

An example of a grid and cell neighbors

Now you can remove, for example, one neighbor. The usual situation in the maze:

An example of a grid and cell neighbors

Each cell can be associated with a vertex. The presence of a neighbor - to connect with the edge. In such a case, it is rather obvious that the definition is more or less correct. At first glance, it is not clear: for each labyrinth, it is possible to choose a labyrinth grid, exactly like vice versa. Here we need a rigorous proof, which does not make much sense.

Generally speaking, to generate the labyrinth itself, it is not necessary to build the graph explicitly. I just focused on this in order to give free rein to your imagination. Building a graph can be useful for more detailed study of the issue. It may be important to you that the maze has any properties. Maybe you want to introduce some kind of "density" or branching of the maze. In this case, graphs can come to the rescue.

Definition The boundary of the lattice or simply the border is the vertex whose coordinate on the lattice is: (x, m), or (n, x), or (1, x), or (n, x), where x is any number from the intervals [1, n] or [1, m].

Now let's move on to the labyrinth generation. Make it so. Define the matrix nxm . Choose one point on one of the borders. After this, we run from this point a detour into the depth within the lattice.

For each maze point we will take turns choosing each of the 4 directions and randomly, with probability p , decide whether there is a passage in this direction or not. We will carry it out until the total number of points on the border is at most k . As soon as this happens, we stop our actions.

By doing actions in this way, one can get a very uneven maze. Therefore, it is possible to slightly change the stop criterion. We will carry out the process until the total number of points on the border is no more than k and on each of the borders (of the whole border, of course, 4) there will be at least k_i points.

Now we need to choose to choose the beginning and the end. You can, of course, take any 2 points on the border, but in this case, it may happen that the path from the beginning to the end will be trivial (that is, too simple and short). In order to avoid this, you should choose the start and end points at a distance from each other not less than d .

Thus, we have built a maze generation algorithm with parameters: k , k_i (4 pieces), p , d .

I advise you to pay attention to such a thing as the theory of percolation . This theory implements the process I described above.

I have three implementations of the percolation process on python, hardware and pluses. You can look at them here: 1 , 2 , 3

  • it is not clear where the "without loops" condition. Not all 2D algorithms are transferred to 3D. - jfs
  • @jfs this algorithm is easily transferred. What neponyatki migrate in 3D? Without loops due to the fact that when the graph is displayed on the grid, the question arises, what to go loop? - hedgehogues
  • “Three-dimensional in all its variations is constructed exactly the same way” it can be perceived that any 2D algorithm in 3D is easily transferred (which is not so). Under "without loops" I [incorrectly] perceived "without cycles" (translated as cycle, and it was necessary as a loop). The cycle of length one (loop, self-loop) is really meaningless for simple labyrinths and they are not usually mentioned. - jfs
  • @jfs, those modifications of the construction of labyrinths that I described, are easy to construct for dimension n. In addition, the author wants to build not a 3-dimensional labyrinth, but 6 two-dimensional ones that connect along the boundaries with each other. It is also easy to do. I meant exactly this, having written the phrase "Three-dimensional in all its variations is built exactly the same way" - hedgehogues
  • Yes, I actually figured it out, just did not have an answer to close the question. I am not strong in mathematics, especially in graph theory, so I was not sure that from 2D to 3D it would be possible to transfer. Made the implementation on c # and draw in a unit, used the recursive backtracker method, if anyone is interested, I can throw it on git. - JacksonFaller

The simplest thing that can come to mind is to generate a 3-dimensional array through Random (), if you write in Java.

int n = 10; int[][][] arr = new int[n][n][n]; for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ for (int k=0; k<n; k++){ Random random = new Random(); Integer r = random.nextInt(2); if (r != 0) { arr[i][j][k] = 1; }else{ arr[i][j][k] = 0; } } } }

If one, then there is a passage, otherwise there is no passage. At the expense of drawing it in 3d model depends on what you write, you can use jPCT in Java.

  • 3
    This is not a labyrinth, but simply a cube with impassable cells. The path in the maze must be connected and, most likely, with a single entrance and a single exit. - Qwertiy ♦
  • one
    I agree, then at the beginning you can generate a randomized path, for example, from cell [0] [0] [0] to cell [n-1] [n-1] [n-1]. Randomly select one path from 6 right, left, forward, back), naturally taking into account the array boundaries and go until we are in the last cell, this will ensure that there is an exit in the maze, and then we confuse it through the same random pattern as in the algorithm above while not blocking the cells of the correct path. - Kotysh