Procedural Generation Using Flood Fill (Tutorial Part 1)

Introduction:

The cave generation algorithm presented in this blog post is a procedural generation technique that creates dynamic and interconnected cave systems. It follows a series of steps to generate a cave map, which can be used as a basis for creating levels or environments in games, particularly in genres like roguelikes or dungeon crawlers.

The algorithm begins by initializing a 2D grid, which represents the cave map. It then randomly fills the grid with solid and empty cells based on a specified fill percentage. This initial random fill creates a noisy and chaotic structure.

To create more coherent and structured caves, the algorithm applies a smoothing process. The smoothing step looks at each cell's neighborhood and determines whether it should be solid or empty based on the count of neighboring solid cells. This process is repeated for a specified number of iterations, gradually refining the cave structure.

After smoothing, the algorithm identifies connected regions of empty cells, which form the rooms of the cave. It uses a flood fill approach to identify and label each room. Rooms below a certain size threshold are filled in, while larger rooms are kept.

Once the rooms are identified, the algorithm proceeds to connect them to create a coherent cave system. It starts with the largest room and iteratively connects the closest unconnected room to the main cave system. The connections are made by building bridges between the edges of the rooms, ensuring that all rooms are reachable.

The cave generation algorithm provides flexibility through various parameters, such as the cell size, fill percentage, and smoothing iterations. These parameters allow for customization and fine-tuning of the generated caves.

Throughout the blog post, we will dive into the implementation details of each step, explaining the relevant functions and providing code snippets. By the end, you will have a comprehensive understanding of how to generate procedural caves using this algorithm in GameMaker Studio.

(download cave_generator.yymps to follow along)

Step 1: Setting Up the Cave Constructor

function Cave(_cell_size=16, _fill = 0.5, _smooth=4) constructor{
    
    /// local variables
    width = room_width div _cell_size 
        + (room_width % _cell_size ? 1 : 0);
    height = room_height div _cell_size 
        + (room_height % _cell_size ? 1 : 0);
    cell_size = _cell_size;
    room_id = 0;
    map = [];
    fill = _fill;
    smooth = _smooth;
    regions = [];
    rooms = [];
    timer = current_time;
} 

The cave generation algorithm is encapsulated within a constructor function named `Cave`. The constructor takes optional parameters for cell size, fill percentage, and smoothing iterations. It initializes various properties such as the cave dimensions, map array, regions, rooms, and timer.

Step 2: Implementing Utility Functions

The `Cave` constructor includes several utility functions to facilitate the generation process:

- `map_safe`: Clamps the given coordinates within the valid range of the map array.

static map_safe = function(_i, _j){
    var xto = clamp(_i, 0, self.width-1);
    var yto = clamp(_j, 0, self.height-1);
    return [xto, yto];
};

- `grid_val`: Retrieves the value from a grid at the specified coordinates.

static grid_val = function(_grid, _point){
    return _grid[_point[1]][_point[0]];    
}

- `random_fill`: Fills the map array with random values based on the fill percentage.

static random_fill = function(){
    for(var _j = 0; _j < self.height; _j++){
        for(var _i = 0; _i < self.width; _i++){
            if(_j == 0 || _i == 0 || _j == self.height-1 || _i == self.width-1){
                self.map[_j][_i] = 1;
            } else {
                self.map[_j][_i] = random(1) <= self.fill;
            }
        }
    }
};

- `smooth_index`: Smooths the value at a specific index based on its neighbors.

static smooth_index = function(_x, _y) {
    var _neighbors = 0;
    var _list = [
        [_y-1, _x-1], [_y+1, _x-1], [_y, _x-1],
            [_y-1, _x],   [_y+1, _x],
            [_y-1, _x+1], [_y+1, _x+1], [_y, _x+1]
    ];
    var _listLength = array_length(_list);
    var _mapValue = self.map[_y][_x];
    for (var _f = 0; _f < _listLength; _f++) {
        var _pval = _list[_f];
            var _pos = self.map_safe(_pval[1], _pval[0]);
            _neighbors += self.map[_pos[1]][_pos[0]];
            if (_neighbors > 4) {
                break;
            }
    }
    if (_neighbors < 4) {
            return 0;
    } else if (_neighbors > 4) {
            return 1;
    } else {
            return _mapValue;
    }
};

- `smooth_all`: Applies the smoothing process to the entire map.

static smooth_all = function(){
    var _sep = 3;
    var _len = self.smooth * _sep;
    // ignore edges
    var _start = 1;
    var _stopj = self.height-1;
    var _stopi = self.width-1;
    for(var _j = _start; _j < _stopj; _j++){
        for(var _i = _start; _i < _stopi; _i++){
            
            /// run multiple smoothing passes so we don't have to
            /// reduce overhead
            for(var _n = 0; _n <  _len; _n += _sep){
                var _sj = (_j + _n);
                if(_sj >= _stopj){
                    // wrap on y axis
                    _sj = _sj - _stopj + _start;
                    _i += 1;
                    // wrap on x axis
                    if(_i >= _stopi){
                        _i = _i - _stopi + _start;
                    }
                }
                self.map[_sj][_i] = self.smooth_index(_i, _sj);
            }
        }
    }
};

Step 3: Finding Rooms

The `find_room` function is responsible for identifying connected regions of empty cells within the map. It uses a flood fill algorithm to traverse the map and mark connected cells as a single room. The function returns an array of tiles representing the room.

static find_room = function(_checkGrid, _value, _pos) {
        var _saved = [];
        var _check = [];
        // Find first cell to flood fill
        if (self.map[_pos[1]][_pos[0]] == _value && _checkGrid[_pos[1]][_pos[0]] == 0) {
            // Mark cell
            _checkGrid[_pos[1]][_pos[0]] = 1;
            array_push(_check, _pos);
        } else {
            return [];
        }
        // Quick fill
        while (array_length(_check) > 0) {
            var _new_pos = array_pop(_check);
            var _edgeMask = 0;
            var _i = _new_pos[0];
            var _j = _new_pos[1];
            array_push(_saved, [_i, _j, 0]);
            var _directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
            var _edgeMasks = [1, 2, 4, 8];
            for (var _d = 0; _d < 4; _d++) {
                var _pNext = self.map_safe(_i + _directions[_d][0], _j + _directions[_d][1]);
                if (self.grid_val(self.map, _pNext) == _value) {
                    if (self.grid_val(_checkGrid, _pNext) == 0) {
                        _checkGrid[_pNext[1], _pNext[0]] = 1;
                        array_push(_check, _pNext);
                    }
                } else {
                    _edgeMask |= _edgeMasks[_d];
                }
            }
            // Update the edge mask of the current position
            _saved[array_length(_saved) - 1][2] = _edgeMask > 0;
        }
        return _saved;
}

Step 4: Setting Up Rooms

static setup_rooms = function() {
        // Clear out regions
        // We will fill it with batches of interconnected tiles
        self.regions = [];
        self.rooms = [];
        var _checkGrid = array_create(self.height, 0);
        for (var _j = 0; _j < self.height; _j++) {
            _checkGrid[_j] = array_create(self.width, 0);
        }
        var _positions = [];
        // Fill positions array
        for (var _j = 0; _j < self.height; _j++) {
            for (var _i = 0; _i < self.width; _i++) {
                if (self.map[_j][_i] == 0) {
                    array_push(_positions, [_i, _j]);
                }
            }
        }
        // Check whole grid for regions
        while (array_length(_positions) > 0) {
            var _pos = array_pop(_positions);
            var _temp = self.find_room(_checkGrid, 0, _pos, _positions);
            var _size = array_length(_temp);
            if (_size > 0) {
                if (_size > 20) {
                    // Add to region
                    array_push(self.regions, _temp);
                    // Add to regions and room
                    var _len = array_length(self.rooms);
                    // Grab all that are marked as edges
                    var _edges = [];
                    for (var _i = 0; _i < _size; _i++) {
                        if (_temp[_i][2] > 0) {
                            array_push(_edges, _temp[_i]);
                        }
                    }
                    // Make new room object
                    var _room = new Room(_temp, _edges);
                    // Add to rooms array
                    array_push(self.rooms, _room);
                } else {
                    // Fill in rooms less than 20 tiles
                    for (var _i = 0; _i < _size; _i++) {
                        var _pos = _temp[_i];
                        self.map[_pos[1]][_pos[0]] = 1;
                    }
                }
            }
        }
        if (array_length(self.rooms) <= 0) {
            show_debug_message("out of rooms");
            return 0;
        }
        // Sort rooms by size -- descending order (biggest room is first)
        array_sort(self.rooms, function(elm1, elm2) {
            return array_length(elm2.tiles) - array_length(elm1.tiles);
    });
};

The `setup_rooms` function is the main entry point for room generation. It clears the existing regions and rooms, and then iterates through the map to find potential rooms using the `find_room` function. Rooms with a size greater than 20 tiles are added to the `regions` and `rooms` arrays, while smaller rooms are filled in.

Step 5: Filling Circular Regions The fill_array 

This function is a utility function that fills a circular region in the map array with a specified value. It takes the center coordinates (xcell, ycell), the radius of the circle, and the value to fill.

static fill_array = function(xcell, ycell, radius, value) {
        var _radius_squared = radius * radius;
        var _min_x = max(0, xcell - radius);
        var _max_x = min(self.width - 1, xcell + radius);
        var _min_y = max(0, ycell - radius);
        var _max_y = min(self.height - 1, ycell + radius);
        for (var _y = _min_y; _y <= _max_y; _y++) {
            for (var _x = _min_x; _x <= _max_x; _x++) {
                var _dx = _x - xcell;
                var _dy = _y - ycell;
                var _distance_squared = _dx * _dx + _dy * _dy;
                if (_distance_squared <= _radius_squared) {
                    self.map[_y][_x] = value;
                }
        }
    }
};

Here's how the fill_array function works:

1. It calculates the squared radius (_radius_squared) to avoid using the square root function for distance calculations.
2. It determines the minimum and maximum x and y coordinates (_min_x, _max_x, _min_y, _max_y) of the region to fill based on the center coordinates and the radius. These values are clamped within the valid range of the map array.
3. It iterates over each cell within the calculated range using nested loops.
4. For each cell, it calculates the squared distance (_distance_squared) from the center coordinates using the formula: _distance_squared = (_x - xcell)^2 + (_y - ycell)^2.
5. If the squared distance is less than or equal to the squared radius, it means the cell falls within the circular region. In this case, the corresponding cell in the map array is set to the specified value.

By using the fill_array function, you can easily fill circular regions in the map array with a desired value. This function is particularly useful for creating circular rooms or applying circular patterns during the cave generation process.

Step 6: Connecting Rooms

The `Room` class constructor is used to keep track of room tiles and edges.

static Room = function(_tiles, _edges) constructor {
    tiles = _tiles;
    size = array_length(_tiles);
    edges = _edges;
};

The `connect_rooms` function is responsible for connecting the generated rooms to create a coherent cave system. It starts with the largest room and iteratively connects the closest unconnected room to the main cave system. The connection is made by building bridges between the edges of the rooms using the `make_bridge` function.

static connect_rooms = function(){
    /// add all rooms to the main room, but just the edges
    var _roomsLeft = json_parse(json_stringify(self.rooms));
    /// remove first set of edges
    array_delete(_roomsLeft, 0, 1);
    var _blob = json_parse(json_stringify(self.rooms[0].edges));
    var _count = array_length(_roomsLeft);
        
        
    /// loop through all edges and connect to a room
    while(_count > 0){
        var _data = {rm: -1, p1: -1, p2: -1, distance: 10000};
        for(var _e = 0; _e < array_length(_blob); _e+=2){
            var _edgeA = _blob[_e];
            for(var _rm = 0; _rm < array_length(_roomsLeft); _rm++){
                var _roomB = _roomsLeft[_rm];
                for(var _b = 0; _b < array_length(_roomB.edges); _b+=2){
                    /// get distance
                    var _edgeB = _roomB.edges[_b];
                    var _dist = point_distance(_edgeA[0], _edgeA[1], _edgeB[0], _edgeB[1]);
                    /// save shortest
                    if(_data.distance >= _dist){
                        _data.distance = _dist;
                        _data.rm = _rm;
                        _data.p1 = _edgeA;
                        _data.p2 = _edgeB;
                    }
                }
            }
                
        }
        /// add edges to blob, pop room out of rooms list, update count
        if(array_length(_roomsLeft) > 0){
            /// build bridge
            self.make_bridge(_data.p1, _data.p2);
                    
            _blob = array_concat(_blob, _roomsLeft[_data.rm].edges);
            array_delete(_roomsLeft, _data.rm, 1);
            _count = array_length(_roomsLeft);
        }
    }
};

The `make_bridge` function is used to create a connection between two points in the cave system. It calculates the distance between the two points and iterates over each step along the line connecting them. At each step, it fills a circular region using the `fill_array` function to create a corridor connecting the two points.

static make_bridge = function(_pntA, _pntB){
    var _len = point_distance(_pntA[0], _pntA[1], _pntB[0], _pntB[1]);
    for (var _i=0; _i<=_len; _i+=1){
        var _ratio = _i/_len;
    var _x1 = lerp(_pntA[0],_pntB[0],_ratio);
    var _y1 = lerp(_pntA[1],_pntB[1],_ratio);
    var _r1 = abs(lengthdir_x(2, _ratio*180)) + 1;
            
    /// clamp to keep in room bounds
    _x1 = floor(clamp(_x1, _r1+1, self.width-2-_r1));
    _y1 = floor(clamp(_y1, _r1+1, self.height-2-_r1));
            
        /// large corridor
        self.fill_array(_x1, _y1, _r1, 0);
    };
};

Step 7: Generating the Cave

The `generate` function serves as the main entry point for the cave generation process. It calls the necessary functions in the appropriate order to generate the cave:

static generate = function(){
    /// generate map
    self.random_fill();
    /// smoothing
    self.smooth_all();
    /// find rooms
    self.setup_rooms();
    /// connect all rooms
    self.connect_rooms();
};

1. `random_fill`: Fills the map with random values.

2. `smooth_all`: Applies smoothing to the map.

3. `setup_rooms`: Identifies and sets up the rooms.

4. `connect_rooms`: Connects the rooms to form the cave system.

Step 8: Debugging and Visualization

The `draw` function is provided for debugging purposes and visualizes the generated cave system. It renders the map cells as black and white rectangles based on their values. Additionally, it highlights the edges of each room with different colors for visual distinction.

static draw = function(){
    var _size = self.cell_size;
    for(var _i = 0; _i < self.width; _i++){
        for(var _j = 0; _j < self.height; _j++){
            var _val = self.map[_j][_i];
            var _col = _val ? c_black : c_white;
            draw_set_color(_col);
            draw_rectangle(_i*_size,_j*_size,_i*_size+_size,_j*_size+_size,false);
        }
    }
        
    var colors = [c_red, c_green, c_blue, c_orange, c_teal, c_yellow];
    for(var _s = 0; _s < array_length(self.rooms); _s++){
        for(var _f = 0; _f < array_length(self.rooms[_s].edges); _f++){
            var _pos = self.rooms[_s].edges[_f];
            draw_set_color(colors[_s%array_length(colors)]);
            draw_rectangle(_pos[0]*_size,_pos[1]*_size,_pos[0]*_size+_size,_pos[1]*_size+_size,false);
        }
    }
};

Conclusion:

Implementing procedural cave generation in GameMaker Studio involves several steps, including setting up the cave constructor, implementing utility functions, finding rooms, setting up rooms, connecting rooms, and generating the cave. By following this algorithm, you can create dynamic and interconnected cave systems in your games. Feel free to experiment with the parameters and customize the algorithm to suit your specific requirements.

I hope this step-by-step breakdown helps you understand the cave generation algorithm and its implementation in GameMaker Studio. Let me know if you have any further questions!

In the next tutorial I will show you how to use this in GameMaker to build a stunning world!

cave_generator.yymps -- contains all of the code to generate a cave

cave_generator_advanced.yymps -- contains additional functions for bitmasking and includes a copy of Sprite_Layer_Manager which allows you to create animated sprites or tiles anywhere in the room and at any depth -- dynamically, a demo of the generator with the advanced features enabled, and more!