3
$\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.

|cite|improve this question
$\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
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.

|cite|improve this answer
$\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.

|cite|improve this answer
$\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.