Quarkstrudel im Kopf

July 17, 2014 / Martin

Maze Builder

I was curious how to generate mazes after I have read some articles about them. Actually it is fairly easy to build easy nice looking ones similar to the one below. I followed the Wikipedia article about maze generation.

A generated maze

A generated maze

The algorithm starts a the upper left corner and keeps similar to Prim’s algorithm a list of walls that could be torn down next. Different to the original algorithm its randomized cousin randomly selects one of those walls and extends the labyrinth in that direction if some conditions are met. For example, the algorithm does not generate any loops in the maze and therefore checks if the selected wall candidate has already some open paths on the other side.

My version of the algorithm actually has two little modifications in it. It always extends two fields of the maze at once to generate this chess board like pattern. Also, the algorithm does not build mazes that have junctions with more than three paths leading to them. So the full labyrinth could be described by a binary tree.

You can get the code at github.