CODEWITHSUNDEEP
algorithmmaze
John
John

Reputation: 335

Maze Algorithm That generates the most difficult mazes?

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)?

Upvotes: 8

Views: 8144

Answers (5)

Ian Mercer
Ian Mercer

Reputation: 39277

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

Upvotes: 5

Sergey K.
Sergey K.

Reputation: 25386

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.

Upvotes: 1

john_science
john_science

Reputation: 6541

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.

Upvotes: 7

user1061392
user1061392

Reputation: 324

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

Upvotes: -2

Ahmed Emad
Ahmed Emad

Reputation: 560

You can check maze generation algorithms from here :

Maze Classification

Upvotes: 1

Related Questions