Growing Forest Algorithm

Growing several trees at once and merging them with Kruskal’s sets

Sourcecodeberg.org/yordanos/mazes

Growing Forest Algorithm #

Growing Forest is Growing Tree with several trees growing at once, and Kruskal’s sets to stop them forming loops. Start a few trees in random rooms. Each active room either grows into an uncarved neighbour, which joins its tree, or runs into a carved room. If that room belongs to a different tree, knock the wall down and the two trees become one. If it belongs to the same tree, leave the wall alone. New trees can start at random along the way. When the growing is done, any trees that never met are connected by a final pass of Kruskal’s.

How many trees you start with and how often new ones appear changes the texture of the maze. Think Labyrinth notes that, with the right parameters, Growing Forest can reproduce the Recursive Backtracker, Kruskal’s, Prim’s and Growing Tree.

Growing Forest Algorithm

Pseudocode #

every room is its own set; all rooms uncarved
start N trees: carve a random room, add to active

while active is not empty:
    maybe start a new tree (with some chance)
    room = pick one from active
    if room has no uncarved neighbour:
        remove room from active
        continue
    next = room + 2 * (a random direction in bounds)
    if next is uncarved:
        knock out the wall, carve next, join sets, add next to active
    else if find(room) != find(next):
        knock out the wall, join sets

merge what's left: Kruskal's pass over every wall

Solution #

This uses find and join from Kruskal’s, rooms_beside_wall from Prim’s, and random_dir from Hunt and Kill.

// a random direction whose neighbouring room is in bounds
random_dir_any :: proc(room: [2]i32) -> [2]i32 {
    dirs := [4][2]i32{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    rand.shuffle(dirs[:])

    for d in dirs {
        if is_cell_in_bounds(room + 2 * d) do return d
    }

    return {}
}

growing_forest :: proc(maze: ^[COLS][ROWS]Cell, trees: int, spawn_chance: f32) {
    parents: [COLS][ROWS][2]i32
    walls: [dynamic][2]i32
    defer delete(walls)

    // every room is its own set, and we collect the walls for the final pass
    for x in 1..<i32(COLS - 1) {
        for y in 1..<i32(ROWS - 1) {
            if x & 1 == 1 && y & 1 == 1 {
                parents[x][y] = {x, y}
            } else if (x + y) & 1 == 1 {
                append(&walls, [2]i32{x, y})
            }
        }
    }
    rand.shuffle(walls[:])

    active: [dynamic][2]i32
    defer delete(active)

    // start the first trees
    for _ in 0..<trees {
        room := random_room()
        for maze[room.x][room.y] != .WALL do room = random_room()

        maze[room.x][room.y] = .PATH
        append(&active, room)
    }

    for len(active) > 0 {
        // sometimes start a new tree
        if rand.float32() < spawn_chance {
            room := random_room()

            if maze[room.x][room.y] == .WALL {
                maze[room.x][room.y] = .PATH
                append(&active, room)
            }
        }

        i := rand.int_max(len(active))
        room := active[i]

        // no uncarved neighbour: this room is finished
        if _, ok := random_dir(maze, room, .WALL); !ok {
            unordered_remove(&active, i)
            continue
        }

        dir := random_dir_any(room)
        wall, next := room + dir, room + 2 * dir
        root_room, root_next := find(room, &parents), find(next, &parents)

        if maze[next.x][next.y] == .WALL {
            // grow into a new room
            maze[wall.x][wall.y] = .PATH
            maze[next.x][next.y] = .PATH

            join(root_next, root_room, &parents)
            append(&active, next)
        } else if root_room != root_next {
            // two different trees meet: connect them
            maze[wall.x][wall.y] = .PATH

            join(root_next, root_room, &parents)
        }
    }

    // merge what's left: Kruskal's pass
    for wall in walls {
        a, b := rooms_beside_wall(wall)

        root_a, root_b := find(a, &parents), find(b, &parents)
        if root_a == root_b do continue

        maze[wall.x][wall.y] = .PATH
        join(root_a, root_b, &parents)
    }
}

generate :: proc(maze: ^[COLS][ROWS]Cell) {
    growing_forest(maze, 5, 0.01)
}

Run it, press space a few times, and you’ll get a new maze each time.

odin run .