Growing Tree Algorithm
One algorithm with a dial, where the way you pick the next room decides what kind of maze you get
Growing Tree Algorithm #
Growing Tree keeps a list of active rooms, the ones that might still have unvisited neighbours. Pick a room from the list. If it has an unvisited neighbour, knock down the wall to it, open that room, and add it to the list. If it doesn’t, remove it, because it’s finished. Repeat until the list is empty.
Everything interesting is in how you pick. Always take the
newest room, and you get the Recursive Backtracker: the list is the
stack, and removing a finished room is the backtrack. Take a random
room, and the maze grows outward in a blob, much like Prim’s. Mix the
two, and you get mazes somewhere in between.
ordered_remove
keeps the list in order, which “newest” depends on. Prim’s could use
unordered_remove because it never cared about
order.
Pseudocode #
active = [a random room]; mark it visited
while active is not empty:
room = pick one from active
if room has an unvisited neighbour:
next = a random unvisited neighbour
knock out the wall between room and next
mark next visited
add next to active
else:
remove room from active
Solution #
This uses the random_dir helper from the Hunt and Kill
article.
Strategy :: enum { NEWEST, RANDOM, MIXED }
pick :: proc(strategy: Strategy, count: int) -> int {
switch strategy {
case .NEWEST:
return count - 1
case .RANDOM:
return rand.int_max(count)
case .MIXED:
// half the time the newest, half the time a random one
if rand.float32() < 0.5 do return count - 1
return rand.int_max(count)
}
return 0
}
growing_tree :: proc(maze: ^[COLS][ROWS]Cell, first: [2]i32, strategy: Strategy) {
active: [dynamic][2]i32
defer delete(active)
maze[first.x][first.y] = .PATH
append(&active, first)
for len(active) > 0 {
i := pick(strategy, len(active))
room := active[i]
dir, ok := random_dir(maze, room, .WALL)
if !ok {
// no unvisited neighbours: this room is finished
ordered_remove(&active, i)
continue
}
wall, next := room + dir, room + 2 * dir
maze[wall.x][wall.y] = .PATH
maze[next.x][next.y] = .PATH
append(&active, next)
}
}
generate :: proc(maze: ^[COLS][ROWS]Cell) {
growing_tree(maze, random_room(), .MIXED) // try .NEWEST and .RANDOM too
}Run it, press space a few times, and you’ll get a new maze each time.
odin run .