4
$\begingroup$

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important).

There are many Maze generation algorithms, but they only work on a finite grid.

What if instead you are working on an infinite grid? But you only need to know finite of the grid at a time (the application I have in mind is a character wandering around in a grid). What are some algorithms I could use?

In particular, it would be best if the algorithm wasn't biased by which parts of the maze you choose to evaluate first.

One algorithm I thought of was a modification of randomized Kruskal's algorithm. Basically, to calculate a part of the grid, you add the walls to the list, and then eliminate walls until the part of the grid you want to reveal, along with the parts of the maze already revealed, are all in the same set. This might have bias though depending on which parts you evaluate first.

$\endgroup$
  • $\begingroup$ how do you plan to store an infinite random maze on a computer? you can generate finitely many vertices and when you leave generate more of the maze? these random algorithms have nice properties that you don't have to generate the entire object at once $\endgroup$ – john mangual Jan 19 '18 at 0:36
  • $\begingroup$ @johnmangual yes, you only store finitely much of it at a time $\endgroup$ – PyRulez Jan 19 '18 at 0:49
2
$\begingroup$

If you have to create the maze:

  • Without boundaries
  • Generated uniformly
  • Generated from a seed

It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a really large maze.

Daedalus has lots of features and implements all the algorithms on this page. To generate a really big maze in Daedalus, start the program -> press File -> run script -> Worlds largest maze -> click Ok -> press i.

From Daedalus features: (beware the rabbit hole)

World's Largest Maze: This script has the option to use different algorithms to generate the parts of the Maze being viewed, which are nested cell fractal, binary tree, recursive division, unicursal Labyrinth, classical Labyrinth, and Hilbert curve Labyrinth.

Mazes created here are enormous, and measure at least a billion passages on each side. Visiting one cell per second, it would take over 31 years just to walk from one side of the Maze to the opposite side, and that’s assuming no walls are in your way. Wall following to actually solve the Maze will take on average 31 billion years

Wall following a maze this large on a regular computer, would take over 100 years. Exceeding the lifetime of a person, I would say this is "big enough".

Nested Fractal: This creates a fractal Maze, which is composed of smaller Mazes connected together. Each cell of an outer Maze contains an inner Maze nested inside of it, where this Maze nesting process can be repeated multiple times.

Consider a 10^9 by 10^9 passage Maze, or a 10x10 Maze nested with 9 levels total. If we want at least a 100x100 section around us, we only need to create the 100x100 passage submaze at the lowest level, and the seven 10x10 Mazes it's nested within, to know exactly where the walls lie within a 100x100 section. To ensure the Maze remains consistent and never changes as you move around, have a formula to determine a random number seed for each coordinate at each nesting level.

The nested fractal maze has an obvious texture, where you can see the maze is split up into "blocks"

view of an infinite nested fractal maze

This is the closest i have come to an infinite maze, and it should be possible to extend this by adding randomization to the edges of the lowest level to break the "blocky" texture.

From Daedalus features:

Binary Tree: The algorithm creates Mazes with the special property that each cell has a passage that leads either up or left, but never both or neither. This creates a biased texture, where one can always easily travel diagonally up and to the left without hitting barriers or having to make choices. Moving down and to the right is when the Maze becomes a challenge, so the Maze is hard to solve but easy to solve backwards. The Maze forms a binary tree, with the upper left corner the root, where each node or cell has one or two children, and one unique parent which is the cell above or to the left of it.

view of an infinite binary tree maze

Recursive Division: The algorithm creates a Maze by adding walls, where the area within the Maze is divided by a randomly positioned horizontal or vertical wall with a passage opening within it. Each subarea is then recursively divided with more walls until all areas are filled.

Every time we subdivide, we only have to subdivide the part of the maze we are in.

enter image description here

The images are from World's Largest Maze in Daedalus, (the subjectively best) open-source maze generation program, written in C++, and it even has its own scripting language. If you want a more detailed explanation of the algorithms, you can also check out the source code. The images above are colored based on the distance you have to walk to another cell. Black cells can't be reached without exiting the viewport.

$\endgroup$
0
$\begingroup$

Generating such unbiased maze it's a very hard problem, since long term dependencies in the tree appear from the fact that you have an infinity maze, i.e. There is a chance that the path from 2 neighboring positions goes through several part of the grid away non calculated yet.

Here is one idea that might help. Imagine you have already calculated several quadrants. Since the final (infinite board) will be a tree, from any position you need to be able to reach a border exit. Here a border exit is a wall location that has not wall and is adjacent to a calculated quadrant and a non calculated quadrant.

When you want to calculate some quadrant, take all wall location in some arbitrary order, and make Kruskal, but add a dummy node that represent the outside. Whenever a node is connected to this node, it can goes outside the quadrant. You stop when all nodes are connected to this dummy node. Note that you will not have a tree but a forest.

Make sure you understand the approach described above. Now I will described a solvable issue with this approach.

Here there is just one problem. How can I decide when a wall location shared by two quadrants, if it will contain a wall or not. Why is this a problem? Because you need to be consistent generating both quadrants, while keeping the connected tree property. Let's denote first quadrant as quadrant $ZERO$. For each quadrant take the Manhattan distance from this quadrant to quadrant $ZERO$, if two quads have the same distance they will not be adjacent. Assign to each quadrant the responsibility of generating the border walls to the neighboring quadrants with distance from $ZERO$ greater that itself.

$\endgroup$
0
$\begingroup$

consider the uniform spanning tree. we get an unbiased maze on a grid (or any graph) by performing a "loop-erased random walk".

Prim algorithm or any BFS also returns a spanning tree, I think.

$\endgroup$
  • $\begingroup$ This is no boundary. $\endgroup$ – PyRulez Jan 19 '18 at 0:30
  • $\begingroup$ @pyrulez then don't use a boundary. it still works. boundary is for display $\endgroup$ – john mangual Jan 19 '18 at 9:26
  • $\begingroup$ then when do you "lock in" the path? $\endgroup$ – PyRulez Jan 19 '18 at 18:33
  • $\begingroup$ @PyRulez you raise a good point. the first graphic does have a boundary and the second graph does not. Loop Erased Random Walk "forgets" loops but when it touches the growing path, we now include the entire path. The second graphic may be what you are looking for. $\endgroup$ – john mangual Jan 19 '18 at 21:23
  • $\begingroup$ okay, the second graphic might work. The question is though, what is the probability that it will? How likely is it that the random walk will run into the original graph? $\endgroup$ – PyRulez Jan 20 '18 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.