How to create a Maze Generator in C?

[kknehra]

Hey guys, I was wondering how best to go about creating a simple Maze Generator in C. I have read around the area and found that implementing the Depth First Search (DFS) algorithm is a good strategy.

My question is, how would one initially go about doing this? I am new to C and I am finding it difficult to start from scratch, however I am confident that, once pointed in the right direction, I can progress.

Any help would be greatly appreciated.

Cheers.

[Salem]

Perhaps start with a web search for "maze generator algorithm"
Maze generation algorithm - Wikipedia, the free encyclopedia

[Nominal Animal]

Hey guys, I was wondering how best to go about creating a simple Maze Generator in C. I have read around the area and found that implementing the Depth First Search (DFS) algorithm is a good strategy.

Yes, it is a good strategy. It is basically a "mole" that digs passages through the given volume, until there are no more possibilities to dig. Every point in such a maze is reachable from any other point within the maze.

First, however, you need to decide whether you want thin or thick walls:

╶─┬───┬───┐     ▒▒▒▒▒▒▒▒▒▒▒
╷ │ ╷ ╵ ╷ │       ▒ ▒   ▒ ▒
│ │ └───┴─┤     ▒   ▒ ▒▒▒ ▒
│ │ ╶─┐ ╷ │     ▒ ▒   ▒   ▒
│ └─┐ └─┴─┤     ▒ ▒ ▒ ▒ ▒▒▒
├─╴ ├─╴ ╶─┤     ▒ ▒▒▒ ▒   ▒
│ ╶─┘ ┌─╴ ╵     ▒   ▒   ▒   
└─────┴───╴     ▒▒▒▒▒▒▒▒▒▒▒

It seems like an unimportant detail, but the implementation details between the two do differ, and you'll just save yourself a lot of grief if you decide it first.

Thick walls are easier to implement.

You'll need a data structure that can describe each cell or tile in your maze. For thick walls, you only need one bit per cell. For thin walls, you need two bits per cell, one bit for horizontal walls and one bit for vertical walls. Usually it is easier to use a char per cell.

Note: If you use thin walls, I recommend you keep the "up" and "left" walls in the cell. Then, the "right" wall is the "left" wall in the cell one step to right, and the "down" wall is the "up" wall on the cell one step down. If you store all four walls for each cell, your walls are effectively doubled; it's not any easier that way. Also note you'll need an extra cell down and right when using thin walls, for the rightmost and bottommost walls.

When you start creating a maze, you fill it up with walls. Then, you place your "mole" at the starting position, and let it chew away.

For each "mole" step, you check the four directions, to see if the mole can chew through walls that way. You only look at unchewed walls: you can progress that direction only if the cell there is unvisited.

For thick walls, you only look at the six cells towards the target cell. For example, to check if the "mole" M can go right:

. . . . .
. . 1 2 .
. M X 3 .
. . 5 4 . 
. . . . .

If all the six cells (1, 2, 3, 4, 5, X) have walls in them, then you can chew from M into X. The same logic applies to the three other directions, just rotate the image.

For thin walls, the cell is unvisited if the four walls surrounding it are all still intact.

If you have only one possible direction, you go that way. If you have two or more -- in a planar maze, four is only possible at the very first step -- you save that position in a stack, and pick one direction at random.

When your "mole" gets stuck, with no possibilities to chew into, you pop off the last position stored in the stack (basically teleporting the mole back to the previous location it could make a choice), and re-check that. Note that you do need to check the maze, you cannot just remember the choices you then had available, because the maze has changed after that. It is not even guaranteed you can progress from that point at all.

When you have no more possible directions, and the stack is empty, you're done.

As an incentive, here's a 40-column, 25-row maze I created using the above logic:

▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒      ▒▒  ▒▒                      ▒▒▒▒  ▒▒      ▒▒▒▒  ▒▒                    ▒▒
▒▒▒▒▒▒      ▒▒  ▒▒▒▒  ▒▒▒▒▒▒▒▒▒▒▒▒    ▒▒      ▒▒        ▒▒▒▒▒▒  ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒    ▒▒    ▒▒  ▒▒▒▒  ▒▒▒▒▒▒  ▒▒▒▒▒▒▒▒    ▒▒    ▒▒            ▒▒
▒▒      ▒▒  ▒▒▒▒▒▒  ▒▒▒▒▒▒        ▒▒    ▒▒▒▒      ▒▒▒▒▒▒  ▒▒▒▒      ▒▒  ▒▒▒▒  ▒▒
▒▒  ▒▒  ▒▒  ▒▒▒▒    ▒▒      ▒▒▒▒  ▒▒▒▒    ▒▒▒▒▒▒  ▒▒  ▒▒    ▒▒▒▒▒▒▒▒▒▒  ▒▒    ▒▒
▒▒  ▒▒  ▒▒  ▒▒    ▒▒▒▒▒▒  ▒▒▒▒    ▒▒▒▒▒▒  ▒▒▒▒    ▒▒  ▒▒▒▒          ▒▒▒▒▒▒  ▒▒▒▒
▒▒  ▒▒  ▒▒  ▒▒  ▒▒▒▒  ▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒  ▒▒    ▒▒▒▒    ▒▒▒▒▒▒▒▒▒▒    ▒▒▒▒    ▒▒
▒▒  ▒▒      ▒▒  ▒▒          ▒▒▒▒      ▒▒      ▒▒▒▒▒▒▒▒          ▒▒▒▒        ▒▒▒▒
▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒  ▒▒▒▒▒▒▒▒▒▒    ▒▒▒▒▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒▒▒  ▒▒▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒
▒▒  ▒▒▒▒        ▒▒      ▒▒▒▒    ▒▒▒▒▒▒      ▒▒▒▒          ▒▒▒▒  ▒▒  ▒▒        ▒▒
▒▒    ▒▒▒▒▒▒▒▒  ▒▒  ▒▒▒▒▒▒    ▒▒▒▒      ▒▒        ▒▒▒▒▒▒  ▒▒    ▒▒  ▒▒  ▒▒▒▒▒▒▒▒
▒▒▒▒  ▒▒        ▒▒▒▒▒▒      ▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒  ▒▒▒▒  ▒▒  ▒▒    ▒▒
▒▒▒▒  ▒▒▒▒  ▒▒▒▒▒▒▒▒    ▒▒      ▒▒▒▒      ▒▒▒▒▒▒▒▒    ▒▒  ▒▒  ▒▒    ▒▒      ▒▒▒▒
▒▒    ▒▒▒▒  ▒▒    ▒▒  ▒▒▒▒  ▒▒    ▒▒▒▒▒▒    ▒▒▒▒    ▒▒▒▒  ▒▒      ▒▒▒▒▒▒▒▒  ▒▒▒▒
▒▒  ▒▒▒▒    ▒▒▒▒        ▒▒  ▒▒▒▒    ▒▒▒▒▒▒        ▒▒▒▒    ▒▒▒▒▒▒  ▒▒    ▒▒    ▒▒
▒▒        ▒▒▒▒▒▒▒▒▒▒▒▒  ▒▒    ▒▒▒▒▒▒▒▒      ▒▒  ▒▒▒▒    ▒▒▒▒      ▒▒▒▒  ▒▒▒▒  ▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒      ▒▒  ▒▒▒▒        ▒▒▒▒▒▒▒▒▒▒    ▒▒▒▒    ▒▒          ▒▒  ▒▒
▒▒      ▒▒  ▒▒▒▒    ▒▒▒▒▒▒  ▒▒    ▒▒▒▒▒▒▒▒▒▒        ▒▒▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒▒▒  ▒▒  ▒▒
▒▒  ▒▒            ▒▒▒▒      ▒▒  ▒▒▒▒▒▒  ▒▒    ▒▒▒▒  ▒▒      ▒▒      ▒▒▒▒▒▒▒▒  ▒▒
▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒▒▒    ▒▒  ▒▒  ▒▒▒▒    ▒▒  ▒▒▒▒▒▒▒▒▒▒  ▒▒  ▒▒▒▒▒▒▒▒▒▒        ▒▒
▒▒  ▒▒      ▒▒    ▒▒▒▒▒▒▒▒▒▒▒▒        ▒▒▒▒  ▒▒▒▒  ▒▒    ▒▒        ▒▒▒▒  ▒▒▒▒▒▒▒▒
▒▒  ▒▒  ▒▒  ▒▒  ▒▒▒▒▒▒      ▒▒▒▒  ▒▒    ▒▒    ▒▒      ▒▒▒▒▒▒▒▒▒▒  ▒▒          ▒▒
▒▒      ▒▒  ▒▒          ▒▒        ▒▒▒▒  ▒▒▒▒      ▒▒          ▒▒      ▒▒  ▒▒  ▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒