Understanding the Growing Tree Algorithm
Explore the Growing Tree algorithm and its flexibility in generating various maze textures by changing cell selection methods. Understand how it generalizes Simplified Prim's and Recursive Backtracker algorithms, allowing you to create mazes with different passage styles and dead-end frequencies by adjusting selection criteria.
We'll cover the following...
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:
Choose a cell at random from ...