I am sure there are many other ways to create
mazes. This is just the method I used to create my maze generator. The solution
has a maze with many paths, but there will be only one possible solution.
Step 1. Start with a maze with all the walls closed. I will use a basic 10x10
maze for this example. Then select a random point in the grid to start with (A).
Step 2. Select a random side around point A. Check if that point in the grid
has been visited. If it has not, break the wall between them. Continue doing
this until you get to a point where all the walls around the current grid point
has been visited.
Step 3. Once you get to a point where you can't select another unvisited grid
point at the current cursor position, select a random point on the path that you
have taken. In this case (B). Now select a random point at point B that has not
yet been visited and continue in that direction.
Step 4. When all of the grid points have been visited you break down 2 walls
anywhere on the sides of your maze and they become the start and end points and
your maze is complete.
Tip : There were two main obstacles that I had. One was that it was slow
checking to see if all grid points had been visited and the other was how to
select a point on the path that I had visited. I came up with one very clever
solution (I think) that solved both those problems. When you get to the stage
where you have to select a random point on the path already taken, push it onto
a stack (add it to a dynamic array). So when you have to select a random point
on the path, you simple select a random coordinate from the array and then take
that point out of the array. When that array is empty, you have gone through all
the points in the grid. This means that you don't have to scan through every
point in the grid at every step to see if there are unvisited points.
Solving the maze
There are many ways to solve the maze and the best place to find out about
the many solutions would be to visit http://www.astrolog.org/labyrnth/algrithm.htm.
There they have various maze generating and solving algorithms.
To solve a maze you can use the very basic method of always keeping left
until you reach a dead end and then backtracking, or you can add a bit of intelligence
to the algorithm. What I did was to calculate X and Y the distance from the
current position to final position and then select the shortest route. This
means that you tend to go in the right direction. So instead of turning left at
the last square in the above maze you will turn to the right and complete the
maze.
Some of the other faster solving techniques like bellman flooding is done by
assigning a weighting to the different cells and then using that to select your
path.
