How to generate a maze with more than one successf

问题:

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] .

回答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:

回答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.