A maze generation algorithm where I can choose entrance and exit points
What would be a good maze generation algorithm where the developer can choose entrance and exit points arbitrarily (both of them should be located on the edges, of course)? A piece of pseudocode or an implementation in any language would be most helpful.
While not exactly an algorithm, i describe here some steps in creating a maze. Each of these steps will need to be turned into code, but i think they are a good starting point.
step 0: Initially, all the squares in the matrix have all their borders marked as walls.
Later on, some of these walls will be cut, such as to create paths.
In the following image, every wall that will be intersected by a path will be cut;
all the walls that are not cut by any path will be kept.
step 1: We start the following way: create the most simple path between the entry and the exit points; this path will be made of only one horizontal and one vertical line.
Next, because this path is too simple, we try to make it more complicated (more twisted, having more turns); we do this by gradually replacing segments of the existing path, with three sides of a rectangle (which, together with the removed segment, would have represented an entire rectangle); we repeat this step as many times as necessary, only taking care that the path will not intersect itself.
step 2: Now we have a relatively complicated path that connects the entry and exit points in the maze. However, there are still cells in the matrix will walls surrounding them on all 4 sides. I have looked for some examples of mazes, and i have noticed that every cell in the maze is potentially accessible from the entry point, even though it is a dead end. (to put it in another way, all the paths in the maze form a tree).
What we need to do now is to connect all the remaining cells in the maze to the existing path. As a convention, i will call 'main path' the path that we have just created from the entry to the exit points; all the other paths that branch out of it will be named 'secondary paths'. So how do we create secondary paths? By picking one random point in the large areas of the maze that are not traversed by the main path, and another random point on the main path. Than link these points in a similar way that we did with the entry and exit points: link them with the most simple path possible, later make this path more complicated - by replacing a segment with the 3 segments that would make the complement of a rectangle. We won't need to repeat this step many times because the secondary paths don't need to be more complicated than the main path.
step 3: Now we have created several secondary paths , by linking some random points in the maze with the main path. There are still some areas that are inaccessible, but they are small. So for these cells, we can just link them with a straight line to the nearest point in either the main path or a secondary path, and that's it. All the squares in the maze are accessible. All we need to do now is to remove any wall that is intersected by a path, and keep all the other walls.