Practical algorithms and code optimization: maze generation

I am currently building a prototype game based upon Maze generation and pathfinding for my 3rd Year project at University.

You can play the prototype at http://mazeapp.heroku.com

I've found Maze generation algorithms to be fascinatingly diverse in their approach to the problem, and the types of mazes they generate.

The problem itself can broadly be classified as a Random Tree Generation and Traversal.

Aside from the typical Kruskals/Primms approach, a selection of the Algorithms that you can use for Generation are:

Recursive Backtracker. This is a nice simple algorithm that generates mazes without many short 'dead end' passages. It appears to be the approach taken by the author. One issue with Recursive Backtracker mazes is that they are slightly easier for Humans to solve from an over the shoulder or first person perspective, as there aren't many dead ends. Furthermore, because the algorithm is recursive rather than iterative, complex (large) mazes tend to cause stack overflow errors.

Growing Tree. My favourite algorithm for maze generation (for academic purposes). It functions in a similar manner to the recursive backtracker algorithm however when it comes to explore a new cell you can choose either to explore the newest cell, or one at random. The more often you choose the newest cell - the more the maze will look like a maze generated by recursive backtracker (because in this case the process is essentially exactly the same). The more often you choose a random cell, the more short dead ends paths you wil have. This balance allows for some dynamic weighting function and some interesting results. Plus it generates mazes that are fun to solve and nice to look at.

Eller's Algorithm. This is an algorithm I discovered by accident in an article written by Jamis Buck (http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller... - incidentally he has a fantastic series on maze generation algorithms with a lot of hypnotic in browser demos... check them out!). It is interesting because it allows you to generate mazes of infinite depth in linear time and low memory. Mazes must have a set width or height but can otherwise continue forever whilst continuing to be technically perfect mazes (single acyclic paths to goal).

----

As a last aside its also worth mentioning that although they're not technically mazes - mazes with loops in are more challenging. Loops can conceptually be added by adding edges at random to your randomly generated tree.

----

From a pathfinding perspective simple A* is indeed guaranteed to give you an optimal solution if one exists - however its not terribly interesting as it requires full world knowledge ahead of time - you can't compete with an A* agent in a Maze haha.

What I have done for the agent implementation in my example (the shadow) is a dynamically weighted variant of A* pathfinding. Essentially you introduce a pessimistic error into your A* heuristic which depends on the value of that heuristic. Analogously - the further you are from an object the world the less accurately you can estimate its distrance from you. From that point I stop and rerun A* each time the agent moves 10 cells from the position where is last ran A*. This gives the agent the appearance of heading in the general direction of the goal whilst still having the ability to take wrong turns etc...

----

That was a great opportunity to geek out :)

love the frenglish in this (and i say that as someone who lives abroad and has a shitty accent, not in mockery).

one thing not mentioned is that if you do a flood fill once the maze is generated, recording distances, you can choose start and end points to be maximally separated (assuming you have no other restrictions on start and end). which tends to help give an "interesting" puzzle.

i wasted a month of my phd generating mazes for the son of a collaborator, in fortran 66, on a microvax. good times :o) the idea was to save the collaborator from having to hand-draw the mazes his son was pestering him for. but the poor child burst into tears when given one of my computer-generated multi-million cell constructions :o(

Making difficult "perfect" mazes is easy. Making fun or organic-seeming mazes is a more interesting problem. I experimented with maze generating algorithms with a view to creating more open mazes — to do this was to have some probability of abandoning a thread before running out of space, also I would measure how isolated each cell was and maximize cell isolation.

Http://loewald.com/maze

One can also use a disjoint-set data structure. Make a list of walls as tuples containing the "room number" (cell index) of both adjacent cells. Add all cells as disjoint sets in a disjoint-set data structure. Shuffle all the doors (tuples) randomly. Then go through the shuffled list and for each door: IF both sides are not part of the same set already: remove the wall. ELSE save the wall, it is part of the final maze.

A very cool algorithm for generating mazes and other spanning trees from the uniform distribution: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.8...

The author says a lot about "topological equivalence" but it's clear that he's playing fast and loose with those terms. So don't read too closely into the math, and just enjoy the rest of the article.

It seems the author is not aware of John Tromp's IOCCC maze program. It uses working storage equivalent to one row of the maze. Very clever.

A* all the things