Recursive Flood Fill Algorithm in GameMaker: Studioapproach

This is not a QR code! It is a ds_grid being flood filled.

This is not a QR code! It is a ds_grid being flood filled.

If you have ever used the paint bucket tool in an image editor, you have been exposed to two-dimensional flood filling - the color replacement of a region, based on the color of an individual point (pixel). The use of flood filling extends beyond making pictures. This algorithm can play an important role in some games. If one were to make a dungeon crawler, some form of flood filling may be used in enemy AI to determine whether the player was in the same room as them. It is notably used in Minesweeper to clear sections of the board.

Flood filling is an inherently straightforward algorithm, meaning the process of getting it working in GameMaker: Studio is quick. While it is not always necessary to visualize flood filling, for the sake of a more effective tutorial I have decided to implement the ability to click on cells in the ds_grid to change their color, as indicated by the .gif. The source is available to download at the end of this post.

The Recursive Algorithm

floodfill(i, j, new_color, prev_color);
1) If the given cell (i, j) exists within the grid, continue. Otherwise, return.
2) If the color of the cell is the same color it started as, the region color, continue. Otherwise, return.
3) Replace the color of the cell with the new color.
4) Repeat with the north, south, east, and west cells.

Initializing

The following code should go in the Create Event of an object. This declares all necessary variables and generates our grid.

arr = ds_grid_create(45, 45); // init 45x45 grid
cell_width = 10; // width of each grid cell
cell_height = 10; // height of each grid cell
xpos = 32; // x-coordinate of the top-left cell in the room
ypos = 32; // y-coordinate of the top-left cell in the room
flood_color = c_lime; // color to flood the grid

// cycle through all the cells in the grid and make them either white or black
for (var i = 0; i < ds_grid_width(arr); i++) {
    for (var j = 0; j < ds_grid_height(arr); j++) {
        ds_grid_set(arr, i, j, choose(c_white, c_black));
    }
}

Drawing

The following code should go in the Draw Event of the same object. This draws the grid and allows us to click on individual cells to flood fill their associated regions.

// cycle through all the cells in the grid
for (var i = 0; i < ds_grid_width(arr); i++) {
    for (var j = 0; j < ds_grid_height(arr); j++) {
        var x1, y1, x2, y2; // temporary variables for top-left and bottom-right coordinates of each cell
        x1 = xpos + (i * cell_width);
        y1 = ypos + (j * cell_height);
        x2 = x1 + cell_width;
        y2 = y1 + cell_height;

        // draw rectangle at the given coordinates based on the color of the cell
        draw_set_color(ds_grid_get(arr, i, j));
        draw_rectangle(x1, y1, x2, y2, false);

        // if mouse button is pressed and the cursor is in the cell
        if (mouse_check_button_pressed(mb_left) && point_in_rectangle(mouse_x, mouse_y, x1, y1, x2, y2)) {
            if (ds_grid_get(arr, i, j) != flood_color) { // ensure the color of the cell is not already the flood color
                floodfill(i, j, flood_color, ds_grid_get(arr, i, j)); // call the algorithm
            }
        }
    }
}

The Flood Fill Script

The following code should go in a script called floodfill. This is the meat of the tutorial, despite its shortness.

///floodfill(i, j, new_color, prev_color);
var i, j, new_color, prev_color;

i = argument0; // cell col
j = argument1; // cell row
new_color = argument2; // new, replacement color the cell should be
prev_color = argument3; // the color of the region to be changed

// if the coordinates are not within the grid and if the color of the cell has changed, return
if (i < 0 || i >= ds_grid_width(arr) || j < 0 || j >= ds_grid_height(arr)) || (ds_grid_get(arr, i, j) != prev_color) {
    return 0;
}

// change the color of the cell to the new color
ds_grid_set(arr, i, j, new_color);

// adjacent cell recursion
floodfill(i - 1, j, new_color, prev_color); // cell to the left
floodfill(i + 1, j, new_color, prev_color); // cell to the right
floodfill(i, j - 1, new_color, prev_color); // cell above
floodfill(i, j + 1, new_color, prev_color); // cell below

Wrapping Up

There are numerous ways to approach the flood fill algorithm, some more efficient than others. You can read about these other solutions here. If you desire to use flood fill on a large grid (n-hundred * n-hundred), I recommend looking into non-recursive solutions, such as stack implementation. I dive into this concept in-depth in my Depth-First Search Maze Generation tutorial.

Even if this recursive approach is best used in small-scale cases, I hope you were able to take something away from this brief exercise. Click here to download the source project. As always, if you have any questions, comments, or critiques feel free to leave them below.

GameMaker-related posts mailing list