Procedurally Generated Mazes

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.

My helpful screenshot

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.

My helpful screenshot

Now, at this point, I thought it’d be cool if i could turn it into a game :). so…

My helpful screenshot

The human player is blue and a Computer player is red. The aim of the game is to get to the ohter diagonal end first. I had to adjust the velocity of the computer palyer 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.



¬ Written by Atul Vinayak on 11 April 2013