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

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: