Maze Generation started out as an experiment.
I was fascinated by maze generation algorithms. I used a randomized version of Kruskal’s algorithm.
Create a list of all walls, and create a set for each cell,
each containing just that one cell.
For each wall, in some random order:
If the cells divided by this wall belong to distinct sets:
Remove the current wall.
Join the sets of the formerly divided cells.
I tried to do it in python in the begining, and later in C (for practice). The algorithm scaled really well, and I used it to generate huuge mazes of ~5GB with a single path between points.
The project took about a week to complete. Later on, the algorithm was used to design a real physical maze game in college.
The UI was witten in C using the excellent GTK Libraries, and Clutter for Vector graphics.
A few days later, I explored the Dead end filling algorithm to solve any randomly generated maze.
Now, at this point, I thought it’d be cool if i could turn it into a game :). so…
The human player is blue and a Computer player is red. The aim of the game is to get to the other diagonal end first. I had to adjust the velocity of the computer player so that it’s nearly impossible to beat the machine, unless you time your keystrokes accurately and not make any mistakes.
Here is a youtube video (mute to avoid the horrible background music) of the path the Machine takes to solve. This is not how dead end filling works . The maze is already solved. I’m just animating the solution path.