Recursive Flood Fill Part II: Making a "Flood It" Game

Make the board the same color by flooding it from the top-left.

Make the board the same color by flooding it from the top-left.

This tutorial expands upon the concepts taught in my previous Recursive Flood Fill Algorithm in GameMaker: Studio post. Today, I will walk you through creating a Flood It game using the recursive flood fill algorithm.

The win condition is to make the entire board the same color by means of changing the color of the top-left cell. The accompanying .gif showcases the completion of the game. To increase replayability, this simple mechanic can be coupled with varying board sizes, additional colors, and a best-score counter.

To keep this lesson digestible, our version of the game will get minimal GUI. Changing the flood color is done by pressing keyboard keys, the number of turns used is printed in the GameMaker: Studio console, and a random board is generated each play. 

Flood It Mechanics

1) If each cell of the board is not the same color, continue. Otherwise, game complete.
2) Press R, Y, G, or B to set the flood color.
3) If the top-left cell's color is not the flood color, continue.
4) Execute the flood fill algorithm from the top-left cell.

Initializing

The following code should go in the Create Event of an object. This declares all necessary variables and generates our grid. When comparing this initialization code to Part I's initialization code, the key differences are: setting a random seed, modifying grid dimensions, and creating a turn counter.

random_set_seed(randomize()); // randomness

arr = ds_grid_create(16, 16); // init 16x16 grid
cell_width = 20; // width of each grid cell
cell_height = 20; // 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

// init the colors used in the game
red = c_red;
yellow = c_yellow;
green = c_lime;
blue = c_blue;

flood_color = red; // color to flood the grid (from top-left cell)

turns = 0; // how many color swaps it takes to flood the grid

// cycle through all the cells in the grid and make them any of the four colors
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(red, yellow, green, blue));
    }
}

Flooding

The following code should go in the Step Event of the same object. This event does not appear in Part I and is used to change the flood color based on keyboard inputs. The floodfill script call has moved to this event from the Draw Event, as it is triggered upon pressing the keys. The turn counter also increases by one each time a different color is selected.

var pressed = false; // no key has been pressed

// determine which key was pressed
switch (keyboard_key) {
    case (ord("R")): // if R, set the flood color to red
        flood_color = red;
        pressed = true; // indicate that a key has been pressed
        break;
    case (ord("Y")): // if Y, set the flood color to yellow
        flood_color = yellow;
        pressed = true;
        break;
    case (ord("G")): // if G, set the flood color to green
        flood_color = green;
        pressed = true;
        break;
    case (ord("B")): // if B, set the flood color to blue
        flood_color = blue;
        pressed = true;
        break;
}

// if a key has been pressed
if (pressed) {
    if (ds_grid_get(arr, 0, 0) != flood_color) { // ensure the color of the top-left cell is not already the flood color
        turns+=1; // increment turn counter
        floodfill(0, 0, flood_color, ds_grid_get(arr, 0, 0)); // call the algorithm, starting in the top-left (0, 0) grid cell
    }
}

Drawing

The following code should go in the Draw Event of the same object. When comparing this drawing code to Part I's drawing code, the key differences are: the addition of a check to determine whether each grid cell is the same color (win condition) and the removal of cell mouse-clicking to call the floodfill script (moved, in part, to the Step Event).

var success = true; // whether the grid is one solid color, default to true*

// 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++) {
        // temp variables for top-left and bottom-right coordinates of each cell
        var x1, y1, x2, y2;
        x1 = xpos + (i * cell_width);
        y1 = ypos + (j * cell_height);
        x2 = x1 + cell_width;
        y2 = y1 + cell_height;

        var col = ds_grid_get(arr, i, j); // get the color of the cell

        // *multiple cell colors in the grid, we cannot win this turn
        if (col != flood_color) {
            success = false;
        }

        // draw rectangle at the given coordinates based on the color of the cell
        draw_set_color(col);
        draw_rectangle(x1, y1, x2, y2, false);
    }
}

// if all grid cells are the same color, print the number of turns and restart the game
if (success) {
    show_debug_message(turns);
    room_restart();
}

The Flood Fill Script

The following code should go in a script called floodfill. This code has gone unmodified since Part I.

///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

If you managed to successfully create the game, congratulations! If something is not working, either go back and ensure you followed all the steps and put the code in the correct events, or download the source project here. If you want an additional challenge, try adding more colors in a larger grid. Further, try your hand at adding clickable buttons that set the flood color rather than pressing keyboard keys. As always, if you have any questions, comments, or critiques feel free to leave them below.

GameMaker-related posts mailing list

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

A Secret Project: Afterbox's Website Launched!

Check out the official Afterbox website at http://afterbox.io

Conceived in February 2016, I have been slowly and secretly working on my most ambitious project to date: Afterbox. Afterbox is a data preservation and inheritance service to house user's meaningful and sensitive information which is too often lost over time and through passing.

While I can't share everything surrounding the application at this time (and boy, is there a lot!), the website launched this past weekend with rich information about the upcoming service. If you like what you see, be sure to follow Afterbox on social media and join the mailing list!

This summer is going to be chock full of exciting developments for Afterbox. Co-founder Noah Chrysler and I are going to be located in the beautiful Menlo Park, California from June to September. If you're located in the area, let me know! I'd love to do some networking.

Check out Afterbox at http://afterbox.io

Using ASCII to Generate Levels in GameMaker: Studio

Using ASCII to Generate a Level in GameMaker: Studio

In a recent blog post, I showcased how levels can be generated in GameMaker: Studio by means of parsing colors from images. In response to the tutorial, reddit user Myles recommended that I tackle level creation through text by associating ASCII characters with objects. Today, I'm going to do just that.

This method of constructing rooms is considerably faster than using images, allowing for sizable floors to oftentimes be generated within a single game step. As Myles pointed out in his comment, ASCII-based spawning holds ground in the game development scene as it's used in the indie sensation, Spelunky, to generate chunks.

On the topic of Spelunky from a level design perspective, I recommend this YouTube video by Mark Brown of Game Maker's Toolkit. It gives an in-depth analysis of how creator Derek Yu managed to use random preset rooms to birth engaging environments. While my walkthrough will not cover how to create a full-fledged Spelunky-esque generator, it's not out of the question for me to make a post about that in the future.

Anyway, let's get started!

The Text Document

First and foremost, a plain-text document should be created. I simply use Windows' default Notepad - though feel free to use whatever you're comfortable with - saving the file with a .txt extension. This file extension will makes things much easier as we won't have to worry about compression and other miscellaneous file type-specifics. With a simple .txt and GM:S, a file can be opened and read line-by-line without hassle. I named this file levels.txt. It's included later in the source, but can be downloaded individually here. This file should go into the resource tree folder Included FilesI'll explain what goes into a text document and how it should be structured, assuming you haven't figured it out already by looking at the image at the beginning of this post.

Plain-text document representing a level.

My game features three objects: a wall (oWall)a player (oPlayer), and a coin (oCoin). Each object is represented by an ASCII character in the text document. The ampersand (@) character represents object oWall, a capitalized P represents object oPlayer, and a capitalized C represents object oCoin. Further, a sole underscore (_) on a line signals the end of a level. This allows for the level width and height not having to fit within predefined dimensions.

You can use any regular characters you desire, so long as they are used consistently both within the text document and GM:S (explained later). Any characters not being utilized by objects nor separators will be ignored by the generator. These ignored characters are used in part to give levels their shape as no objects will spawn in their place. For example, the first level in the document uses periods to carve hallways while the second and third level use spaces.

load_levels();

The first of two scripts the project will contain is called load_levels(). This script should only be called once. It locates the text document containing the level data and organizes it into a two-dimensional array, global.data, storing information level by level, row by row. The the first dimension of the array indicates the particular level. There are three test levels created in the source project, so the index spans from 0 to 2. The second dimension increments for each row the particular level contains. The first test level contains 12 rows, so the index spans from 0 to 11. For clarity, global.data[1, 4] would hold the string data for the fifth row of the second level.

///load_levels();

/*
    This script loads levels - separated by var separator - from a text document.
*/

var separator, fname, f, file, level, row, line; // init vars

separator = "_"; // character(s) on a new line in the text doc that indicate a new level should begin
fname = "levels.txt"; // name of file levels are pulled from (should be .txt)
f = working_directory + "\" + string(fname); // file location

/*
    2d array used to house (string) level data row by row
        First index is the level number
        Second index is the level's row data
*/
global.data[0, 0] = "";

level = 0; // current level
row = 0; // current row of level

if (file_exists(f)) { // check if file exists
    file = file_text_open_read(f); // open file
    while (!file_text_eof(file)) { // repeat until the end of the file is reached
        line = file_text_read_string(file); // read line
        if (line == separator) { // if the line contains the separator, a new level begins
            level++; // increment the level counter
            row = 0; // reset the row counter
        } else { // if there is data on the line
            global.data[level, row] = line; // store line information
            row++; // increment level row counter
        }
        file_text_readln(file); // move to next line
    }
    file_text_close(file); // close file
} else {
    show_error("Cannot locate " + string(fname) + "!", true); // error loading file
}

return 0;

generate_level();

Now that all level data is neatly organized thanks to the previous script, we can begin generating a level. This script, generate_level(), takes one integer argument: the level to load. As aforementioned, there are three levels in the project so a 01, or 2 can be passed in to this script without encountering any problems. To determine how many levels were loaded from the file, function array_height_2d() can be used in conjunction with the global.data array.

Row by row, the generator spawns objects at coordinates in relation to its character position multiplied by the cell_width and cell_height variables respectively. Which object to create an instance of is determined by the switch statement. If you represent walls as anything other than an ampersand, for example, changes must be reflected here in the code. Otherwise, the character will be ignored by the generator. This system is easily modified, allowing for cases to be added or removed at your discretion.

///generate_level(level);

/*
    This script generates a particular level, arg0, from the text doc.
    Script load_levels() must be called first.
*/

var level, cell_width, cell_height, i, j, obj, char; // init vars

level = argument0; // which level, int, to generate

/*
     Horizontal and vertical size of each cell, each char in text doc.
        Objects will spawn in relation to this grid.
*/
cell_width = 64;
cell_height = 64;

for (i = 0; i < array_length_2d(global.data, level); i++) { // cycle through level's rows
    for (j = 0; j < string_length(global.data[level, i]); j++) { // cycle through row's characters
        obj = noone; // object to spawn
        char = string_char_at(global.data[level, i], j + 1); // grab character

        switch (char) { // set object to spawn based on current character
            case ("@"): // @ represents object oWall
                obj = oWall;
                break;
            case ("C"): // C represents object oCoin
                obj = oCoin;
                break;
            case ("P"): // P represents object oPlayer
                obj = oPlayer;
                break;
        }

        if (obj != noone) { // create necessary object if there was a character match
            instance_create(j * cell_width, i * cell_height, obj);
        }
    }
}

return 0;

Wrapping Up

So there you have it: how to generate levels using ASCII characters in GameMaker: Studio. As mentioned in the preface of this tutorial, I would like to expand on concepts taught today to create something along the lines of how Spelunky (or Binding of Isaac, among other games) create their worlds. There are limitations on this implementation of ASCII level generation. Without rewriting how the generator interprets text documents, this system allows for only one object per grid space. Further, the player can easily access the text file to modify existing levels and write levels of their own. Using a checksum (hashing the level's text and comparing it to see if it's been modified) can alleviate this problem. 

You can download the full source, which includes basic object interactivity, here.

As always, if you have any questions, comments, or critiques, feel free to leave them in the comments below.

GameMaker-related posts mailing list