# Mathematical Maze Generation

I have performed some research into maze generation through Java code and learned about different "perfect" maze generation algorithms here.

I found good Java-based maze generation code here.

I have also seen the output of the mazes and learned that the output most closely matching what I want is the recursive backtracking algorithm.

However, I have been searching for one that has long straight paths, with only occasional turns, no "cul-de-sacs" (or very few) and also defined as a "perfect" maze.

I can't help but feel that there is a mathematical way to either perform most of the logic for me, or simplify it.

So I am reaching out to the community to ask if anyone knows:

1. Of a purely mathematical maze generation algorithm that I could use.

Or Failing that ...

2. Mathematical formula(s) that could help me simplify the process of performing some of the tasks necessary for maze generation. (Orphaned areas, Loops, Dead Ends, etc.)

I'll need to control the output in some way.

This is not a project for work or school. It's just a personal project, so there is no rush. I'd like to do this in the way that produces the best results, not necessarily the fastest way.

• As somewhat of a side-note, this website has some visualization algorithms (including maze generation) that might be useful to others. Commented Jul 24, 2014 at 16:46

I also like best the look of the recursive backtracker (RB) mazes. I recently made a maze generator using C#, so it's fresh on my mind. RB starts with a full grid and recursively removes walls until a "perfect" maze is created. Each cell in the maze is an object that contains a list of possible moves, among other things.

For the normal RB algorithm, you use "foreach" to loop through the list of possible moves for the recursion. However, in order to achieve the result that you want, you need to instead use "for" to loop, so that you can totally control which wall you choose to remove. You need a custom method that checks which wall(s) (if any) has already been removed, and then 80%-90% of the time choose the next wall to remove based on that, and the remaining 10%-20% of the time, choose a random wall. When using "for", remember to remove the wall from the list.

For example, if your maze path starts at A1 and is now at C3, like this:

then your custom method would check which walls around C3 have already been removed, and then usually select the opposite wall. In this case, the method would return C3-D3 80%-90% of the time, and the other 10%-20% of the time, it would just randomly select a wall to remove.

Play around with the actual % to alter the result. Sorry if you were looking for some elegant mathematical algorithm. If you do find one, please share it!

*************************** END ***************************

That is the end of my answer, but continue reading if you want to see the result of me trying to achieve your desired result just by altering the way I shuffle the list of moves for each cell.

These mazes all start at cell A1 (top left) and the creator can choose the Finish point in most cases.

If I don't shuffle the list of moves for any cell, I get

since, when creating the list for each cell, I always add up and down before I add left and right.

If I shuffle the list of moves for every cell, I get the regular RB result:

If I shuffle the list of moves for a random 20% of cells, I get noticeably more ups and downs (or less lefts and rights):

If I shuffle the list of moves for a random 10% of cells, I get even more ups and downs

If I shuffle the list of moves for a random 5% of cells, I get

If I shuffle the list of moves for a random 4% of cells, I get

If I shuffle the list of moves for a random 2% of cells, I get

If I shuffle the list of moves for a random 1% of cells, I get

So, I doubt that these mazes are what you are looking for, but the answer above will get you what you want.

• First off, thank you for your answer it was a lot more informative than I was expecting. It doesn't get me there in Java, but it gets me most of the way there. I was trying to create the maze in a silly way. I would define a start and end point, then try to find my way from one point to another, then fill in the things in between. Very bad way to do it. I definitely want to try the way you are suggesting, but I also want to keep the question open for other possible answers. By the way, I think you might be interested in this: (bost.ocks.org/mike/algorithms) Commented Sep 24, 2014 at 1:28
• Yes, I saw that website earlier today from the comment in your original question. Very cool, especially the animation of a spanning tree to a maze! Also, if you think my C# code might help you, I'd be glad to send it your way.
– JLee
Commented Sep 24, 2014 at 2:27
• The original goal included me programming the actual implementation for self-improvement in coding practices, conventions, cleanness of code, etc. So I would politely decline the offer for the code. It would defeat part of the purpose for doing this. Thank you, though. Commented Sep 24, 2014 at 18:06