Mazes

Welcome back! Our first couple posts are helpful for if you are designing a video game, but what if you want an algorithm for something that can be done on paper just for fun? Well you can always do a maze! Mazes are monotonous and time consuming to draw though so you need a better solution. Luckily there are many! There a multiple different algorithms for generating mazes and we are not going over all of them. We are going to go over one called a Recursive backtracker. The basic idea is as follows.

We have a list of unvisited cells. We choose one at random and start there. Next the algorithm loops until there are no more unvisited cells. In each iteration of the loop it checks if the current cell has any unvisited neighbors. If it does it moves to that cell, pushes it to the stack, removes the wall in between and marks it as visited. If the cell has no unvisited neighbors, we pop a cell off the stack and make it the current cell. This may sound confusing but it is actually very straightforward one it is seen in code so let's jump into it.

This is the bulk of the algorithm and where all the hard work is done. We can see in the first two for-loops is where we populate a list with unvisited cells. Then we choose a random cell and make it our start and mark it as visited. Unseen in this snippet is the while loop condition which checks to see if there are still unvisited cells. As usual this can be seen in the Github Repository ( link below ).  This also applies to getting the neighbors. We can see if we have neighbors we get a random one, move there and make it visited and if we don't we pop one of the stack.

So when this is actually run, how does it look!

Look at that maze! Wow that looks complicated. And they are. I spent more time than I care to admit trying to solve that. This algorithm has it's ups and downs. You may notice that there are little or very few long "jagged" corridors. This is due to the nature of the algorithm and there are other maze algorithms, like using a depth-first search algorithm, that will make those long jagged corridors.

I'm happy with how our mazes look though. They are complicated and fun and more common in everyday life than some of topics. As usual, I hope you learned something new.

For the full source code, go here.