Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's a good algorithm to generate a maze? [closed]

Tags:

algorithm

maze

Say you want a simple maze on an N by M grid, with one path through, and a good number of dead ends, but that looks "right" (i.e. like someone made it by hand without too many little tiny dead ends and all that). Is there a known way to do this?

like image 764
Greg Avatar asked Sep 01 '08 21:09

Greg


People also ask

What is the best maze algorithm?

Trémaux's algorithm, invented by Charles Pierre Trémaux, is an efficient method to find the way out of a maze that requires drawing lines on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages, but it is not guaranteed to find the shortest route.

How do you make a maze algorithm?

Another way of generating a maze is by applying a randomized Depth First Search (DFS) to the grid. The algorithm starts at a given cell and marks it as visited. It selects a random neighboring cell that hasn't been visited yet and makes that one the current cell, marks it as visited, and so on.

What is the fastest way to solve a maze?

There is a simple method for finding your way out of a maze or labyrinth: Touch the wall or hedge with the hand nearest to it, left or right. Keep that same hand touching the wall and keep walking. This may take you on a horribly long route, but it will eventually get you out.


2 Answers

It turns out there are 11 classic algorithms to generate "perfect" mazes. A maze is perfect if it has one, and only one, solution. Here are some links to each algorithm, in rough order of my preference.

  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. Recursive Division (Predictable)
  10. Sidewinder (Predictable)
  11. Binary Tree (Flawed)

For more info, check out mazelib on GitHub, a Python library implementing all the standard maze generating/solving algorithms.

like image 61
john_science Avatar answered Sep 18 '22 23:09

john_science


From http://www.astrolog.org/labyrnth/algrithm.htm

Recursive backtracker: This is somewhat related to the recursive backtracker solving method described below, and requires stack up to the size of the Maze. When carving, be as greedy as possible, and always carve into an unmade section if one is next to the current cell. Each time you move to a new cell, push the former cell on the stack. If there are no unmade cells next to the current position, pop the stack to the previous position. The Maze is done when you pop everything off the stack. This algorithm results in Mazes with about as high a "river" factor as possible, with fewer but longer dead ends, and usually a very long and twisty solution. It runs quite fast, although Prim's algorithm is a bit faster. Recursive backtracking doesn't work as a wall adder, because doing so tends to result in a solution path that follows the outside edge, where the entire interior of the Maze is attached to the boundary by a single stem.

They produce only 10% dead ends

is an example of a maze generated by that method.

like image 30
rmmh Avatar answered Sep 22 '22 23:09

rmmh