Mathematical Maze Generation

Question

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.

Answer 1

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.