The recursive backtracker
The recursive backtracker, as the name suggests, involves recursively calling a function that carves passages between two tiles in the game grid. By choosing random directions to carve this path, the algorithm carves its way through the level as far as possible before resolving its recursions, working back to the start node.
The following is pseudocode for one such algorithm:
Choose random direction and make a connection to the adjacent node if it has not yet been visited. This node becomes the current node (a recursive call).
If all the adjacent cells in each direction have already been visited, go back to the last cell (return from the previous recursive call).
If you're back at the start node, the algorithm is complete.
As we can see, there's really not much to it! The only pitfall is that you need to have the entire maze in memory. For large mazes this method can be inefficient or maybe not possible at all! However, for our implementation, it will work perfectly...
