Understanding the Growing Tree Algorithm

The Growing Tree algorithm

Both versions of Prim’s algorithm start at an arbitrary cell, and both grow outward from that cell by selecting neighboring cells. In the case of the simplified version, neighboring cells are selected at random. For the “true” version, cells are selected based on their cost.

But those are hardly the only two ways to select cells from that list. What if we always tried to select the cell nearest to the starting point? Or the cell that was most recently added to the list? Or what if we were to combine multiple conditions somehow, picking at random half the time and picking based on weight the other half of the time?

What we have here is the basis of the Growing Tree algorithm. It works like this:

1. Choose a cell at random from the grid. Add it to the active list.

2. Choose a cell from the active list.

3. Choose a random, unvisited neighbor of that cell, link the two together, and add the neighbor to the active list.

4. Repeat steps 2 and 3 until every cell has been linked.

The magic happens in step 2, where a cell is selected. By plugging in different cell selection criteria, vastly different mazes can be constructed. In fact, the implementations of both the simplified and the true Prim’s algorithms are really just special cases of this Growing Tree algorithm!

Let’s implement this. We’ll use Ruby’s blocks (anonymous functions) to define how cells are selected. We'll create a new class called GrowingTree.

The GrowingTree class