Maze Algorithm That generates the most difficult mazes?

Question

I was playing around with the recursive backtracking algorithm but it always produces very easy mazes. What algorithm produces the hardest mazes to solve (please include information about braids and biased directions if appropriate)?

Sensorimotor

Define "hardest". – Lorettalorette

Takes the longest time to solve by a human:). – Sensorimotor

Ok, but you'd need to convert that to an objective metric before you have a chance of finding an algorithm for it! – Lorettalorette

This question is both broad and subjective. There are a slew of different types of mazes. The "most difficult" mazes would be those that a human could never solve, unaided, in their lifetime (like hyper-hyper-mazes that exist in the 4th or higher dimension.) astrolog.org/labyrnth/algrithm.htm – Cordon

Answer 1

Quantitatively defining the "difficulty" of a maze isn't easy. So let me be qualitative.

First off, Recursive Backtracker is a "perfect maze" algorithm; it generates mazes with one, and only one, solution. Most work on maze generation has to do with generating perfect mazes, so I will limit my answer to those.

There are many, many variations and off-shoots of maze algorithms. But in effect, there are only 12 basic maze algorithms. I have them listed here in the order that I personally (qualitatively and anecdotally) find to be most-to-least difficult:

1. Kruskal's
2. Prim's
3. Recursive Backtracker
4. Aldous-Broder
5. Growing Tree
6. Hunt-and-Kill
7. Wilson's
8. Eller's
9. Cellular Automaton (Easy)
10. Recursive Division (Very Easy)
11. Sidewinder (Predictable)
12. Binary Tree (Flawed)

There is not a lot of difference in the difficulty of the top four on my list. Sorry about that. Perhaps there is a flaw in your implementation. Most likely, you're just good at doing mazes. Try making them larger.

Backrest

The assumption of perfect mazes being more difficult is wrong. On a dead end you can backtrack, a maze with loops is much harder to solve if there are relatively view solutions since it will not be so obvious you are walking in circles opposed to walking into a dead end. – Murrelet

That's an interesting point. But I have found little information on generating non-perfect mazes, so I amended my answer to show that. – Backrest

Lol, i am actually looking for one. Now i am just remembering when i start to backtrack tiles and cut some walls there later. It somewhat works but it does not feel very clean. – Murrelet

I would LOVE to hear about any success you have. Maybe try to start with Hilbert Curves: people.cs.aau.dk/~normark/prog3-03/html/notes/…, or this person has a slow, but possibly functional approach: michaelchaney.com/2014/03/unicursal-mazes – Backrest

I had the same problem, I was using backtracking and kept ending up with a pretty simple maze to solve and after trying reading all the answers I tried out prims and kruskals and turns out your list is pretty correct and the kruskal implemented maze seemed to be the most challenging or "difficult" The implementations can be found here in case anyone is interested Maze – Alcorn

Aldous-Broder and Wilson's both generate uniform spanning trees, which means that their outputs are effectively identical. – Alveta

@DanielM. That's an interesting point. Perhaps I've never seen an implementation of Wilson's that I thought produced particularly hard/interesting mazes. While they might both be centered around USTs, they are different algorithms and the end results I've seen seem a bit different. But I will play around with them and see if perhaps I was wrong. – Backrest

Answer 2

Whilst not a direct answer, this article on visualizing maze generation algorithms is a must-watch.

Lowery

Sum it up for everyone. If that link dies, so does your answer. – Cordon

Seriously? Sum up a visualization? Would you like a text description of each visualization? – Lowery

The high-resolution rainbow visualizations of maze depth are amazing – Chatham

Answer 3

You can check maze generation algorithms from here :

Maze Classification

Drexler

Answer 4

Depth-first search can produce very complex mazes. Here is an open-source C++ implementation: https://github.com/corporateshark/random-maze-generator

Try setting ImageSize to 4096 and NumCells to 2047. The result will be pretty tough.

Varipapa

Answer 5

flood fill algorithms is what IEEE recommend.

There are many versions of this algorithm. I google an implemantion for the flood fill algorithm.
but I did not find implemantion

Lever