A few weeks ago, I said I would write about my maze generator. [link] While now I am!

First some maze vocab:
Perfect Maze: A maze where there is exactly one path between any two cells.
Bias Maze: Maze tends to move one direction over another direction.
River: How much the solution path "twists and turns."
Cell: A square with 4 walls.

There is a lot more than that, but for this, you don't need to know much more.

There are many different types of mazes. I am focusing on perfect mazes, as they seem to be the most useful.
I will post three time. This one will be on the algorithms I have done. The next one will be on the algorithms I still have to do, and the final one will be on maze solving.

Recursive Backtracker: This is probably the simplest algorithm. All you do is choose a starting point, and remove a wall from a neighboring cell(this cell must not have any wall removed). If all neighboring cells have walls removed, move back, and choose a new neighbor. The maze is done when you have carved into all cells(/you can't go back any farther). 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.

Prim's Algorithm: Each cell has three states: (1)"In" the cell has had a wall removed (2)"Frontier" no walls removed, but a neighbor has a wall removed (3)"Out" This cell has not been touched yet, and no neighbors are "in". Choose a random cell and make all neighbors "Frontier." Choose any frontier cell and remove a wall from an "in" neighboring cell. Change "Frontier" to "in." Update "Out" neighbors to "Frontier." The maze is done when no "Frontier" are left(thus meaning no "out" cells remain either.) This algorithm results in Mazes with a very low "river" factor, with many short dead ends, and the solution is usually pretty direct as well.

Kruskal's Algorithm: This algorithm is the most complex one. You might get confused...
This relies on the Union-Find algorithm. [link] I had a really cool visual example of this, but it appears it was taken down(this is pretty good though)...

Basically, you create a 3 dimensional array. The outermost is the x-axis. The the next level is the y-axis, and the innermost stores each cell. At random, take a cell and try to remove a wall between is and a random cell. Make sure the cells are not connected. How? Are they in the same innermost array? If not, remove the wall, and combine the two innermost arrays.(This is extremely hard to explain, I read about 15 articles on the union-find algorithm, and still have trouble understanding it). The maze is done when the innermost part of the array is 1 array, thus all the cells are connected.
Because of my limited understanding of union-find, my Kruskal algorithm is slow. I hope to gain a better understanding of it, and improve my code.

This algorithm yields Mazes with a low "river" factor, but not as low as Prim's algorithm.

Aldous-Broder Algorithm: This is a simple algorithm. Choose a starting cell. Choose a random neighbor. If the neighbor has a wall removed, start over using the random neighbor as the starting cell. If the neighbor has all its walls, remove the wall between the two cells. Take the new cell and start over. If all the cells have been used, the maze is done.
This algorithm yields Mazes with a low "river" factor, only slightly higher than Kruskal's algorithm.

Wilson's Algorithm: This is basically Aldous-Broder algorithm, but its improved. Start by choosing a cell. Make it part of the maze(set its value to "in.") Choose another cell. Choose random neighbors, and remove walls until you find a "in" cell. Each time you choose a new cell, set it to "in." Once all cells are used, you are done.

Thats all I have done so far. I still have a about 5 algorithms, and 7 solving algorithms.