Algorithm for maze generation with no dead ends?

Question

I'm looking for a maze generation algorithm that can generate mazes with no dead ends but only a start and end. Like this:

_{Image from http://www.astrolog.org/labyrnth/maze/unicursl.gif}

Where do I find or go about constructing such a maze generation algorithm?

Answer 1

It sounds like you want a pseudo-random space filling curve (for example, see Context-based Space Filling Curves -EUROGRAPHICS ’2000 (PDF format, 1.1 MB))

Take a look a Space-filling curve.

I suspect you could apply some randomness to the construction of one of these to achieve what you want.

Answer 2

I would sugest to start with completely black (full) square and try to dig the path. During the digging you easily ensure there are no dead-ends, simply keep going. Use backtracking, depth first search algorithm. Do a "random walk" - in each step, randomly decide whether to keep direction or change it. Check for the dead end condition - if you get stuck, you can either say "well, I'm done, I'm in the finish", or, if you consider the maze not yet digged enough, just backtrack. Always remember what you've done before and try randomly some other action. Probably use some heuristic to prefer certain directions, like, say, always keeping some free space before dodging the wall, try first to walk around walls etc. - this way you could find the desired solution which fills all the square much more quickly.

Answer 3

I think I've found another method, however I've not yet tested it extensively.

See https://twitter.com/tdhooper/status/340853820584230915/photo/1

From left to right:

• Generate a non-unicursal maze as described here https://en.wikipedia.org/wiki/File:Prim_Maze.svg, I think this is Prim's algorithm

• Seal up the exit

• Draw a path that visits every point in the maze (ie. try to solve it)

• Make this path a wall

Answer 4

In the example you give there is only one actual path from start to end. If that is all that you want, I'm thinking you could use random walks!

The concept is simple: given the outer boundaries of the maze, a start point, and an end point, write a function to generate random walks from the start point that eventually end at the end point. The conditions would be that our "random walker" can only move up, down, right, or left from the previous square, and cannot come within one square of a previously traversed square (this creates walls).

As I see it, there are two algorithmic challenges here. The first is ascertaining whether we are within one square of a previously traversed square (collisions). Perhaps we could maintain a list of traversed squares (their coordinates) and maze boundaries, and for each new square evaluate distance from every square in the list. This doesn't sound very efficient though.

The other challenge is actually reaching the end point with our random walk. If collisions with previously traversed squares were not an issue, we would be bound to reach our end point eventually, but with them we have the problem that we could wall ourselves off from the end point. The way to avoid this is to check for and avoid the entering of loops. If we avoid entering loops formed by the traversed path and/or the maze boundaries, then we maintain a possible path to the end point. As far as actually figuring if we are in a loop... Meh that's kind of hard.

If you already have a maze-solving algorithm, you could run it whenever you have a possible collision to see if a path exists from your current square to the endpoint. When you run it, have it think that all previously traversed squares are walls, as well as their boundaries.

Answer 5

I have not thought this through, just an idea:

• Concentrate not on the path, but on the walls
• Start with just the black outer square
• Progressively add blocks of wall in arbitrary positions adjacent to existing blocks of wall, maintaining the condition that there remains a path from start to end
• When no path cell has more than two path neighbours, you're done

The 'arbitrary' selection process for new bits of wall can start off trying to 'grow' straight sections perpendicular to the outer wall, then at some stage switch to filling in wherever possible.

It would probably need the ability to backtrack should it get stuck.

Probably it is not too efficient.

Answer 6

Ahh - I've found a much easier way of generating a unicursal maze.

Start with a blank grid, and fill it with small 2x2 loops. If the grid is odd-by-even, you'll need to mix in some 2x3 loops, and if it's odd-by-odd, you'll have to leave a single square free - I normally leave a corner unfilled.

Next, arbitrarily join the loops together to form larger loops - so (for example) 2 2x2 loops become a single 4x2 loop. Keep doing this, making sure you don't join a loop back to itself.

Eventually you'll end up with a single loop that uses up all the cells occupied by the original farm of loops. Break this loop at any position, and you've got a unicursal maze, where the start and end locations are next to each other.

You can now move the end points around the grid by forming and breaking small loops - hook the end into another point in the maze, and then break the T-junction on the opposite side to re-form your single piece of string with a new end location.

If you're working on an odd-by-odd maze, use this last technique to worm one of your ends over to the unfilled corner to complete your maze.

Answer 7

When 'walking' keep the changes made on each step in a stack, so in that way you can look x steps ahead and then at each stage such that you can take no further steps ( walked into a corner or a spiral like walk ) pop the stack until you have a a viable walking path and continue walking from there until the stack is empty ( i.e you pop the stack all the way back because at each previous step there was no viable neighbour ). Then apply the transformations to the maze data structure.

Answer 8

I'm working on this at the moment... Starting from an edge, I'm random walking across a square array, marking cells with path length as I pass through them.

When you get stuck (and you will), create a T-junction forming a loop with the most recent path that's adjacent to you (but see below). I then back track along the existing path to the other side of the T-junction and break the loop there. This dangling tail then forms your new 'head' of the random walk (remember to recalculate your path lengths from the path source), and you can carry on.

Experiments show that by doing this it doesn't (or hasn't yet - see below) got into a loop of creating new tails, so long as if your new 'tail' is trapped, you don't just brainlessly re-form a link with the cell you've just broken away from if it's the most recent - choose the second most recent in that case.

The terminating case is when you get 'stuck' on an edge element, and you've filled the array (your path length is the same as the area of the array) - you're done. Your start point leads to your end point.

There seem to be two possible inefficiencies and potential hiccups with this (I'm playing with the algorithm at the moment) - Sometimes you'll walk into a corner and the ONLY way to continue is to re-form the loop link with the one you've just broken. Then the sequence back-tracks through all the loops you've previously made to the point at which you originally got stuck. If that can't go anywhere else (it's another corner) then you'll just bounce between the two. There's ways around that, but it means keeping some sort of a list of looped cells, only clearing it when you actually lay down some new path.

The other is that it seems prone to leaving an odd square unfilled, particularly when your array is odd-by-odd. I've not fully investigated why this is the case, and it's when this occurs that the previous corner problem seems particularly prevalent. Work continues...