How to make a Maze Generator

What are we going to make? A maze generator. How? Let's see.

What do we need?

We're going to make the project in C++, using SDL Library for graphics. They have a really nice tutorial on setting up SDL, which is really easy and fast, right here.

Let's code!

First of all, what do we understand by maze? Hmmm... Let's take a look at the dictionary: a confusing network of intercommunicating paths or passages. I don't like how it sounds, let's make it simpler: a collection of rooms that have or have not a connection. So, how are we going to structure this? In a normal way, it can be structured as a graph, but for the simplicity of this problem, we're gonna make it as an NxN grid.

Now comes the fun part, where the thinking is happening... What should contain every cell from the grid? Let's call it a room. What does a normal room? Walls. So, theoretically, our connections between the rooms, are represented by walls. .

Now, how do we connect 2 rooms? By removing the wall between them. And how we can do that? By removing two walls. Now here comes the question "Wait, between two rooms we have two walls". Theoretically no, but in this model, yes, because when you remove the left wall of a room, you have to remove the right wall of the room situated at it's left. Kind of confusing, but this image will most probably make it clearer.

How does the algorithm look like?

The algorithm is based on a backtrack solution (Also, you can find Kruskal and Prim's version on randomizing a maze) and it works like this:

1. Pick one room, make it the starting point and mark it as visited
2. While there are unvisited rooms
   1. If the current cell has any neighbors which have not been visited
      1. Choose one random neighbor that hasn't been visited yet
      2. Push the current room to the stack
      3. Remove the wall between the current room and the next stack (bye bye walls, welcome roads)
      4. Make the current cell the chosen one and mark it as visited
   2. Else If there are no unvisited neighbors and stack is not empty
      1. Pop a cell from the stack
      2. Make it the current cell

It's a very simple algorithm, that can make some very interesting visual effects and be helpful in some situations... And with this, my childhood thinking that mazes from books were manually designed is ruined. You can check it out here and see it in action here.

You can find the original article on MY BLOG.