Flood Fill Objects Inside Walls

How do I flood fill objects within the wall starting from the light bulb objects. At first I tried having the bulb create them all, but could not get it to fill some of the shapes. Then I tried the method of creating one blue object at the light bulb, then each blue object checking around itself, and adding in 4 directions if it didn't find a collision with a wall or its own object type. Studio throws a recursion depth failure error at more than 114 of the blue objects. How am I supposed to do this? I know it won't go on forever. Might have been alright with 500-2000, but 114 is unacceptable for this. I also might want the ability to flood fill on the wall, but not past it if I set a variable to different value in the create event.

Without Flood Fill.jpg Results Wanted With Flood Fill.jpg Previous Method Before Blue Tile Self Checking.jpg Flood Fill Recursion Depth Error.jpg
 
Last edited:
This should work, I've made it in a couple of minutes, so it is not fully optimized. Take it just as a reference.

Code:
 /// Initialize macros
#macro CELL_SIZE 32
#macro EMPTY  0
#macro WALL  1
#macro LIGHT 2

oController =========================================

Code:
/// CREATE EVENT
var width = (room_width div CELL_SIZE);
var height = (room_height div CELL_SIZE);

// Initialize game grid
global.GRID = ds_grid_create(width, height);

// Clear all the grid's cells
ds_grid_clear(global.GRID, EMPTY);

// DRAW EVENT
var grid_w = ds_grid_width(global.GRID);
var grid_h = ds_grid_height(global.GRID);

for (var i= 0; i < grid_w; i++) {
     for (var j = 0; j < grid_h; j++) {
      // Draw a yellow rectangle if the cell is a LIGHT, you can alternatively use a sprite
      // draw_sprite(sLight, 0, i * CELL_SIZE, j * CELL_SIZE);
       if (global.GRID[# i, j] == LIGHT) {
         var col = c_yellow;
          draw_rectangle_colour(i * CELL_SIZE, j * CELL_SIZE, (i * CELL_SIZE) + CELL_SIZE, (j * CELL_SIZE) + CELL_SIZE, col, col, col, col, false);
    }
    }
}
oWall =====================================

Code:
// CREATE EVENT
// Add the wall to the game grid
add_to_grid(WALL);
oLight ===================================

Code:
// CREATE EVENT
// Add the light to the game grid
add_to_grid(LIGHT);
alarm[0] = room_speed * 2;

/// ALARM 0
var xgrid = x div CELL_SIZE;
var ygrid = y div CELL_SIZE;

// Check if adjacent cells are empty
// Left check
fill_cell(xgrid - 1, ygrid, LIGHT, EMPTY);
// Right check
fill_cell(xgrid + 1, ygrid, LIGHT, EMPTY;
// Down Check
fill_cell(xgrid, ygrid - 1, LIGHT, EMPTY);
// Up Check
fill_cell(xgrid, ygrid + 1, LIGHT, EMPTY);
SCRIPTS:
Code:
///add_to_grid

var xgrid = x div CELL_SIZE;
var ygrid = y div CELL_SIZE;

global.GRID[# xgrid, ygrid] = argument0;
Code:
/// fill_cell(xx, yy, new, old);

var xx = argument0;
var yy = argument1;
var new = argument2;
var old = argument3;

// If out of bounds || cell != cell_to_replace, return
if (xx < 0 || xx  >= ds_grid_width(global.GRID) || yy < 0 || yy >= ds_grid_height(global.GRID) || global.GRID[# xx, yy] != old) {
   return 0;
}

// Change the value of the cell
global.GRID[# xx, yy] = new;

// Recursion
fill_cell(xx - 1, yy, new, old);
fill_cell(xx + 1, yy, new, old);
fill_cell(xx, yy - 1, new, old);
fill_cell(xx, yy + 1, new, old);
QUICK OPTIMIZATION:
You can have wall instances just in the room editor.
After their are being created, they store their value in the grid cell and then destroyed.
oController then loops through the grid cells and if one is equal to WALL, draws the sprite accordingly.
This way you have just the oController and oLight in your room.

Code:
/// oWall CREATE EVENT
// Add the wall to the game grid
add_to_grid(WALL);
instance_destroy();
Code:
/// oController DRAW EVENT
for (var i= 0; i < grid_w; i++) {
     for (var j = 0; j < grid_h; j++) {
      // Draw a yellow rectangle if the cell is a LIGHT, you can alternatively use a sprite
      // draw_sprite(sLight, 0, i * CELL_SIZE, j * CELL_SIZE);
       if (global.GRID[# i, j] == LIGHT) {
         var col = c_yellow;
          draw_rectangle_colour(i * CELL_SIZE, j * CELL_SIZE, (i * CELL_SIZE) + CELL_SIZE, (j * CELL_SIZE) + CELL_SIZE, col, col, col, col, false);
    } else if (global.GRID[# i, j] == WALL) {
              draw_sprite(sWall, 0, i * CELL_SIZE, j * CELL_SIZE);
    }
    }
}
Hope that makes sense.
 
Last edited:

NightFrost

Member
One well-established method for flood-fill style seeking, grid shapes included, is the Djikstra's algorithm. Basically a pathfinding algorithm, but it performs in a flood-fill manner so it is able to find all nodes connected to starting node.
 
This should work, I've made it in a couple of minutes, so it is not fully optimized. Take it just as a reference.
This way is definitely more complicated than how I went about it. I have used ds grids once before, but I'm not following some of it. I probably need the blue blocks to be objects added to the room for what I'm doing. I did input the code in their events and objects. These are the script errors.
 

Attachments

Last edited:
Every one of those errors is because you haven't created the scripts that @AlexDerFerri posted under the text SCRIPTS. A floodfill algorithm is not something that is super simple for someone new. The concept itself is simple but because it is a recursive style function, it can take a while to wrap your head around what needs to be done. It is a different type of beast to the simple x = 50 type code that new coders are used to dealing with.
 
Every one of those errors is because you haven't created the scripts that @AlexDerFerri posted under the text SCRIPTS.
Ok I added add_to_grid and fill_cell as scripts. I don't know what the arguments represent and what to put in them. What does argument 0 do/represent in add_to_grid, and what do arguments 0-3 do/represent in fill_cell (especially what old, new)?
 
Ok I added add_to_grid and fill_cell as scripts. I don't know what the arguments represent and what to put in them. What does argument 0 do/represent in add_to_grid, and what do arguments 0-3 do/represent in fill_cell (especially what old, new)?
Everything I have posted in the first comment has been tested and it works great for me. Make sure to add the two scripts (add_to_grid and fill_cell) and to initialize all the macros.
I can't think of a better solution without using a grid/array based system.
If you don't understand how ds_grid works, I recommend you to give a look at it before dealing with something like flood-fill algorithm.
 

NightFrost

Member
Also, here's a flood-fill in Breadth-First search style (not Djikstra, since we're not interested in movement cost) using a while loop technique.
Code:
/// @function scr_breadth_first(startx, starty, grid)
/// @function Does a breadth-first search across a grid and returns an array of coordinates connected to start point.
/// @param startx Starting x-position on the grid.
/// @param starty Starting y-position on the grid.
/// @param grid The ds grid to check. Script assumes clear grid cells are marked with 0 and blocked grid cells with 1.

var Start = [argument[0], argument[1]];
var Grid = argument[2];
var Width = ds_grid_width(Grid);
var Height = ds_grid_height(Grid);
var Frontier = ds_queue_create();
var Visited = ds_grid_create(Width, Height);
ds_queue_enqueue(Frontier, Start);
var Result = 0;
var Counter = 0;

while(!ds_queue_empty(Frontier)){
   var Current = ds_queue_dequeue(Frontier);
   var xx = Current[0];
   var yy = Current[1];
   // Check above.
   if(yy > 0 && Visited[# xx, yy] == 0 && Grid[# xx, yy - 1] == 0){
       var New = [xx, yy - 1];
       ds_queue_enqueue(Frontier, New);
       Visited[# xx, yy - 1] = 1;
       Result[Counter++] = New;
   }
   // Check right.
   if(xx < Width && Visited[# xx + 1, yy] == 0 && Grid[# xx + 1, yy] == 0){
       var New = [xx + 1, yy];
       ds_queue_enqueue(Frontier, New);
       Visited[# xx + 1, yy] = 1;
       Result[Counter++] = New;
   }
   // Check below.
   if(yy < Height && Visited[# xx, yy + 1] == 0 && Grid[# xx, yy + 1] == 0){
       var New = [xx, yy + 1];
       ds_queue_enqueue(Frontier, New);
       Visited[# xx, yy + 1] = 1;
       Result[Counter++] = New;
   }
   // Check left.
   if(xx > 0 && Visited[# xx - 1, yy] == 0 && Grid[# xx - 1, yy] == 0){
       var New = [xx - 1, yy];
       ds_queue_enqueue(Frontier, New);
       Visited[# xx - 1, yy] = 1;
       Result[Counter++] = New;
   }
}
ds_grid_destroy(Visited);
return Result;
This could be optimized in several ways but for clarity I've left it as is. For example, if the search area was always surrounded with walls the out of bounds checks would be unnecessary because the search never will be. The ds grids could also be switched to arrays for speed.
 
Everything I have posted in the first comment has been tested and it works great for me. Make sure to add the two scripts (add_to_grid and fill_cell) and to initialize all the macros.
I can't think of a better solution without using a grid/array based system.
If you don't understand how ds_grid works, I recommend you to give a look at it before dealing with something like flood-fill algorithm.
I know the basics on arrays and ds_grids. I think I've copied down your code correctly in GM Studio, but I'd like to know what I should put in the arguments for the scripts add_to_grid, and fill_cell. What exactly is it setting in the arguments? What values do they take?
 
Last edited:
When you call add_to_grid, you're actually telling which value you want the cell the object is at to be.
I used macros in order not to have magic numbers, so:
EMPTY is 0
WALL is 1
LIGHT is 2

So, if the object calling the script is oWall, you will pass WALL as argument, if it is oLight you will pass LIGHT, and so on...

This is what your game grid will look like after initializing all the cells with the add_to_grid script:

GameGrid.jpg



fill_cell(x grid position of the cell you want the algorithm to start from, y grid position of the cell you want the algorithm to start from, which value you want to fill the grid with (in this case LIGHT), which cell you want to be filled (in this case EMPTY));

To make it simple, after passing the cell position (argument0 and argument1) you want the algorithm to start from, you're telling the script to fill the grid cell with LIGHT (argument2), if the algorithm finds an EMPTY cell (argument3).

Code:
/// ALARM 0 (MAKE SURE THE SET THE ALARM IN THE CREATE EVENT)

// HERE I GET THE oLight X AND Y CELL POSITION IN THE GRID
var xgrid = x div CELL_SIZE;
var ygrid = y div CELL_SIZE;

Example: if the oLight is at position (64, 32), the oLight position in the grid will be grid[# 2, 1], as
64 div 32 = 2;
32 div 32 = 1;


// Now I start the algorithm from the adjacent cells
// Left check
fill_cell(xgrid - 1, ygrid, LIGHT, EMPTY);
// Right check
fill_cell(xgrid + 1, ygrid, LIGHT, EMPTY;
// Down Check
fill_cell(xgrid, ygrid - 1, LIGHT, EMPTY);
// Up Check
fill_cell(xgrid, ygrid + 1, LIGHT, EMPTY);
AlgorithmStartAt.jpg
 
Top