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