Part 1: Algorithms

The basic algorithm is really quite simple. Start with a grid of the desired size. Create a maze on the left half of the grid. Remove the dead ends. Mirror the left half onto the right half. Connect the two halves together.

The grid size I used in MineBlast is 10x15 cells. The algorithm I used to create the maze is a mixture of Growing Tree and Recursive Backtracking. The Growing Tree algorithm creates many straight paths with many dead ends. The Recursive Backtracking algorithm creates long, winding paths with fewer dead ends.

By combining the two algorithms randomly, I can create some very interesting mazes.

Implementation of the two are quite similar. You start with a list. There you place one randomly chosen cell. That cell is now considered as "visited". Then you enter a While loop. If there are no cells left in the list, then you exit the loop and the maze is complete, otherwise you choose a cell from the list. After choosing the cell, you check for neighboring cells that remain unvisited. Pick one of the unvisited cells at random, link it to the current cell, i.e. break down the wall that separates the two cells, then add the new cell to the list. If the current cell has no unvisited neighbors, then you remove the cell from the list without connecting it to another cell. Either way, you continue back to the top of the loop for the next cell.

The difference between Growing Tree and Recursive Backtracking algorithms is in how you choose the next cell from the list. In Growing Tree, the next cell is chosen randomly from the list. In Recursive Backtracking, the last cell added is chosen (effectively making the list into a stack).


Created with Tutorial Markup (c)2018 James Chamblin