Procedural Maze Generator

Part of a Generated Maze

In my last blog entry I talked about my map generator. Shortly after making that generator I created a second one for generating mazes.

Mazes are a very fundamental part of video games. Most maps that the player actually plays through, be it a building, forest or cave, is really just a maze in disguise.

Part of a Maze with Multiple Solutions

The maze generation algorithm I choose is called the recursive subdivision algorithm. There are several different algorithms to choose from but this one seem the best for my needs since it could create a maze with hallways and rooms of varying sizes.

The algorithm is simple: Start with a rectangle, divide the rectangle in half with a wall and leave a gap or doorway somewhere along that wall. Then take each of the half rectangles created by this division and recursively divide them. Continue until the rectangle is the desired size.

A Maze with Wider Doors and Walls

This algorithm has many ways that it can be controlled to create different types of mazes. One way is to control the number of doors in each wall. If every wall has one door then the maze will have only one correct solution. If the walls can have more than one door the maze will have multiple solutions.

The most important part for me was the ability to control the size of the hallways and rooms. To create rectangular rooms I set it so that it would stop dividing rooms when they were between a certain size. To create long hallways, I set the width of the walls to be greater than one.

This algorithm is just a proof of concept for the moment, but I hope one day to use it along with my map generator to generate levels for a game.