How to generate a maze with more than one successful path?

Question

Which algorithm can be used to generate a maze with more than one successful path and if algorithm is modified version of some well known algorithm then explain or add a link .

I am using 2D array A to store configuration of maze .

Assume if the size of maze is n * n then more than one path should be there from A[0][0] to A[n-1][n-1] .

Softpedal

When you have your maze with just one successful path generated (I assume you have done that), then just remove any one wall segment, et voila, two successful paths (possibly with loops). – Thurifer

After removing of one cell from maze , i have to verify that it leads to two path or more , how to verify it ? – Softpedal

Another Idea: Do BFS from the start and the goal, until you have your maze separated into cells closer to the start and cells closer to the goal. (For each cell record the number of steps from both and categorize it accordingly.) Now look for a wall where the cell at one side is closer to the start, and the other side closer to the goal, and remove that wall. – Thurifer

Well you can easily check how many valid paths you have. Then you could just generate your map with one path and remove random wall blocks while you still have your nAvalilablePaths < 2. – Sulphurate

@tobias and webuster Can you elaborate more ? – Softpedal

Answer 1

This algorithms should be able to generate mazes with distinct loop-free paths from start to goal:

Starting with an empty maze (or a solid block of rock), with just the start and the goal...

1. Subdivide the maze into three sets: Start (intially holding just the start cell), goal (initially holding just the goal cell), and undiscovered (all the rest).
2. Randomly remove walls between cells in the start or the goal set and cells in the undiscovered set, and move the newly discovered cell to the respective set.
3. Repeat until each cell is either in the start or the goal set.
4. Remove as many walls between the two regions as you want paths from the start to the goal.

Alternatively, if you already have a maze with a single path form start to goal, use this variant:

1. Do a Breadth First Search from both the start and the goal, and for each cell in the maze record the number of steps that cell is away from both the start and the goal.
2. Subdivide the maze by putting all cells that are closer to the start into the start set and all cells that are closer to the goal into the goal set.
3. Remove a wall between the two regions to add an additional path from start to goal.

The generated paths might have (maybe even substantial) parts in common, but they should be unique loop-free paths from start to goal. Here's an illustration of the first case:

Thurifer

For the alternative solution, when you say "Do a Breadth First Search from both the start and the goal, and for each cell in the maze record the number of steps that cell is away from both the start and the goal.", the algorihtm needs to record the number of steps starting from any cell? – Aeronautics

@Aeronautics No, not the number of steps starting from any cell, just from the start and the goal cell. In the example, the cell to the north of the S would get 1, the cells adjacent to that (except S itself) would get 2, and so on. – Thurifer

Ok. that first solution that you gave, is it a variant of kruskal's algorithm or some other algorithm? I'm trying to understand the first algorithm. Is there some form of pseucode i can follow from your first solution? – Aeronautics

@Aeronautics I don't think this has anything to do with Kruskal's; I just came up with that myself. The only pseudocode I have are the four bullet points in the description. Which part of the algorithm is not clear? – Thurifer

Just the first and second bullet points of your first solution. I've created a maze using recursive backtracking with one solution path from start to finish. I'm trying to create a maze with multiple paths all from start to finish. I was wondering how i could alter my recursive backtracking to create a maze with multiple paths with what you've proposed or i should implement Prim's algorithm to create an imperfect maze? – Aeronautics

Answer 2

Let's say you are solving your maze with a BFS:

Q.push(initial_position)
visited[initial_position] = true
while !Q.empty
    cur = Q.top
    for n in cur.neighbors
        if (visited[n])
            continue;
        Q.push(n)
        from[n] = cur
        visited[n] = true

With visited, you make sure you don't visit a node twice. With from, you remember how you get to that node.

So let's change visited to contain more information:

Q.push(initial_position)
visited[initial_position] = 1
while !Q.empty
    cur = Q.top
    for n in cur.neighbors
        ++visited[n]
        if (visited[n] > 1)
            continue;
        Q.push(n)
        from[n] = cur

Now visited doesn't just say if the node is visited, but it says how many times it has been visited. Note that it still doesn't say how many paths there are to it, but simply whether that are more than one paths to it.

However, it is still hard to detect multiple solutions by looking at the goal. Think about the following maze:

   #######
-->       -->
   # ### #
   # ### #
   #     #
   #######

This is how visited would look like:

   #######
-->1111111-->
   #1###1#
   #1###1#
   #11112#
   #######

So what we can do is to do another BFS, but this time from the n where visited[n] > 1 and update visited:

Q.push(initial_position)
visited[initial_position] = 1
while !Q.empty
    cur = Q.top
    for n in cur.neighbors
        ++visited[n]
        if (visited[n] > 1)
            if (!visited2[n])
                Q2.push(n)
                visited2[n] = true
            continue;
        Q.push(n)
        from[n] = cur

while !Q2.empty
    cur = Q2.top
    for n in cur.neighbors
        visited[n] = max(visited[n], visited[cur])
        if (visited2[n])
            continue;
        Q.push(n)
        visited2[n] = true

Now visited for the above maze becomes:

   #######
-->2222222-->
   #2###2#
   #2###2#
   #22222#
   #######

So at this point, by looking at the goal you can tell if there has been multiple paths to it or not.

Baptist

Shouldn't there be a node with visited = 3 after the second BFS? Also, this does only detect whether there are multiple paths, but it does not create them, right? – Thurifer

@tobias_k, no, your start position is where there was a 2, which doesn't get updated. Also, the updated visited is a maximum of its parents, so 3 can never happen in this example! And yes, it doesn't generate all the paths. The OP seems to be interested only in verifying that more than one path exists. – Baptist