Maze Generation Algorithms

Mazes are cool and I'm pretty sure everyone likes them, I know I love them -- I do a lot of programming on a platform called Roblox, which if their numbers in terms of growth show anything you've probably heard of.

If you know nothing about programming, then that's fine, because frankly I don't really know much about it either and I'm pretty sure I've been faking my way through it this whole time. But either way, mazes are super rad and I set out on an adventure a week ago to make a random maze generator, but on Roblox. Here's what I learned and a bit about Mazes if you like them.

Let's start out by talking about just how you generate a maze. Especially a random one, because that's pretty weird. As you can see on Wikipedia there's actually an entire article just on algorithms for Maze generation.

The way you generate a Maze is sort of varied, I personally used a depth-first search with recursive backtracking. Let's describe that a bit more in-depth: Imagine a 10x10 grid, where each square is a cell. Each cell has a given column and row. Row 1, Column 1 would be the bottom left, while Row 10 and Column 10 would be the top right of the Maze. Depth-first search utilizes this by starting on a random cell of the maze, then selecting a random neighboring cell and removing the walls between those two cells. This continues until every cell has been visited, once that's finished then you have your maze! Woohoo!

God I love mazes.

Here's a 30 second video of my Maze Generator going through so you can get a better understanding of how this works

There's a few things we didn't bring up in that quick explanation though: In Depth-first search, you have to make sure that the neighbors you're visiting haven't already been visited. Imagine if you start on Row 5 Column 5, and visit Row 5 Column 6, then move in a square back to Row 5 Column 5. You've essentially just made an open space of nothing-ness. That's not a labyrinth, nor a Maze! So instead, you cannot visit already visited neighbors.

But then what happens if you walk into a square that is between 3 visited neighbors through the 4th, boxing you in? That's where recursive backtracking comes in. If that's the case, we'll go to the previous cell until we find one with more unvisited neighbors, until we've gotten all the way back to the start. Once we have, we know a maze has been created that isn't only solveable, but also random.

In short, I love Mazes and they're really cool, and making a random Maze generator was a challenge that I really enjoyed even if at times I wanted to pull my hair out.