When I was young, I had a DOS program that would generate random mazes for you to solve. I was was fascinated by the concept, and later on went to make my own maze generator.
Both algorithms I implemented were "diggers", in that they started with the space as a solid block and would dig out the maze. I could have also started with an empty space and built walls around, but digging sounded like the better idea to me.
I looked up a couple algorithms for generating the maze, and I implemented the growtree algorithm first. What this does is pick a random point along the maze and digs a hole in a random direction.
This method, however, resulted in lots of branches that were all very short, and it was very easy to see dead ends, resulting in mazes that weren't very challenging.
I implemented a second algorithm called a backtracer. It would begin digging randomly, and then when it encountered a dead end, it would follow back along the path it followed until it could resume digging, and continued randomly again until another dead end. This resulted in many long dead-end branches, making the mazes somewhat more difficult.
Download: mazegen.tar.gz (Source only, should compile under any *NIX and possibly other systems)
To compile: make
Go back to the main page.
Site created by Rob Bloom.