Categories
personal blog procedural generation series tutorial

Procedural Generation in GMS #5: A Flood of Fills

In this entry, we learn how a little bit of recursion can make some big waves with the flood fill algorithm.


THE ENTIRE SERIES

More to come…


Note: None of the code for any of these proc-gen tutorials is highly optimised. My goal was to get the concepts across as simply as possible, rather than to make them run as fast as possible. Use the following as a springboard for further learning and experimentation, rather than as the best solution possible.

Also, if you are a complete beginner, it’s probably best to start at the first entry and work your way through, as further into the series we get, the more knowledge from previous entries is assumed.

Well, it looks like there was a three way tie with the last vote. Flood fill, A* pathfinding and room perturbation all got the same amount of votes EDIT: Well, they did as I started writing this article, but votes came in during the writing and changed the order a bit…Flood fill still won though =D. However, I think there might be a bit of providence here because I could just teach how to do room perturbation, A* and flood fill on their own over time, but thinking of them as a conjoined set has given me an idea for the next few tutorials. Using A* and room perturbation, we can create a fully connected room based dungeon with corridors. Flood fill is by far the least complicated of the three and it kind of nicely sets up A* so that’s what we’ll start with.

EDIT (31/01/2021): I was asked how I made the gif animation run slowly, rather than instantly filling everything, so I’ve added a section at the end to show that process.


Contents

RECURSIVE RECURSION

FILLING IN THE BLANKS

SLOW MOTION

THE NEXT STEP


RECURSIVE RECURSION

Flood fill introduces a common technique in computer science that we haven’t touched on yet: Recursion.

Recursion is when a process calls itself. The easiest way for me to visualise it in my head is to think of when a streamer points their camera at their screen and you see the infinite series of monitors inside monitors inside monitors. That’s a recursive process. The camera sends a picture of the monitor to the monitor, which then displays itself, and then the camera sees the “extra” monitor, sends that data back into the monitor, creating a third monitor, etc, etc. It happens faster than the blink of an eye, but it’s still a step by step process in reality. The same as any recursive process within a computer.

Of course, infinite recursion will stop your code dead in its tracks, so probably the most important part of recursion is properly setting a “boundary” condition for when the recursive process should stop.

As I’ve said, flood fill is a recursive process (as is A*, so this is good training for when we get into that). First of all we pick a point on our map, then we decide on a “border value” (which is the value that the flood fill should not fill) and then a “change value” (if you think of a paint program, this is equivalent to the colour you want to fill with, it’s the value that the flood filled cells will take on as they get flood filled). That’s all you really need, but I’m also including an option for whether to attempt to fill only along the cardinal directions:

Or whether to attempt to fill the inter-cardinal directions as well:

We run the flood fill algorithm on the first square, and that square decides whether it should be flood filled or not (if you choose a cell with the “border value” to start on, the flood fill will end here immediately and not change anything). If it does get flood filled, it then runs the flood fill algorithm on the squares around it, which in turn run the flood fill algorithm on the squares around them. This is why it’s recursive, because we are running the flood fill algorithm inside of the flood fill algorithm.

I’ve created a version of the algorithm that runs very slowly for display below (even in the gif at the start, I slowed it down, otherwise it would be pretty much instantaneous). The areas that it checks but decides it shouldn’t fill are coloured in red, the rest are flood filled with the grey. You can see that it starts with a single cell, moves on to the immediate cells around it and then checks the cells next to each of the immediate cells and so on. Because it can’t move through walls, it gets “squeezed” through passages.


FILLING IN THE BLANKS

So that’s enough of the theory, I think, let’s get into the code. First we’ll create a new script called flood_fill_func (or whatever you want). Inside that, we’ll create a function:

///@func	FloodFill()
///@param	map				The map we are using (a 2D array)
///@param	x				The starting x position to flood fill from
///@param	y				The starting y position to flood fill from
///@param	border_val		The value we consider a border
///@param	change_val		The value we want to change each flood filled cell to
///@param	cardinal_only	Set to true if we only want to check cardinal directions, set to false if we want to include inter-cardinal directions as well
function FloodFill(map,x,y,border_val,change_val,cardinal_only) {

A quick note: In previous entries, I was writing the ///@func and ///@param comments inside of the function, but I’m pretty sure GMS likes them before the function (though either works alright, I think), so if you’re confused as to why they’re suddenly outside, there’s your explanation.

Given the previous sections explanations, I think we can pretty easily see what is going on. We’re just getting all the arguments we need for the flood fill to function.

Inside the function we start with:

if (x < 0 || y < 0 || x >= array_length(map) || y >= array_length(map[0])) {
	return;
}
if (map[x][y] == border_val || map[x][y] == change_val) {
	return;
}

Here is the very important “boundary” condition check to kill the flood fill we were talking about in the previous section. First we check to see if the cell we are trying to flood fill is inside the bounds of the map. Then we check to see if it’s either a border value or has already been changed into our change value (if we don’t include the change value check, we’ll probably end up with an infinite loop of the flood fill constantly trying to refill areas it’s already filled). If either of these is true, we return out of the function, which, as we will see later, cancels this particular line of recursion.

There will be multiple lines waiting though because the recursion ends up as a stack style data structure. Each new call of FloodFill() gets added to the stack, so returning out of the function at any one point is simply removing that particular “run” of the function from the stack, but if there have been any more FloodFill() calls, then the stack won’t be empty and the computer will simply move on to the next FloodFill() in the stack.

Beginners Note: You might see that I'm first checking if x >= array_length(map) and then I'm checking if y >= array_length(map[0]). What is that map[0] doing there? Why not simply check map again? The reason is because it is a 2D array. We are simply supplying the map and not also the width and height of the map, so we have to manually check the size of both x and y. We can imagine it as though the map array holds all the x columns in the map and then, inside of each x column, there's another "hidden" array holding all the y rows that are in that x column. So the simplest way to check how many y rows there are is to check how large the "hidden" array is in the first x column, which corresponds to map[0]: 

If we pass the “boundary” condition check, we know we are good to fill, so we then assign the current cell the change value:

map[x][y] = change_val;

And finally we get to the recursion:

FloodFill(map,x+1,y,border_val,change_val,cardinal_only);
FloodFill(map,x-1,y,border_val,change_val,cardinal_only);
FloodFill(map,x,y+1,border_val,change_val,cardinal_only);
FloodFill(map,x,y-1,border_val,change_val,cardinal_only);
	
if (!cardinal_only) {
	FloodFill(map,x+1,y-1,border_val,change_val,cardinal_only);
	FloodFill(map,x-1,y-1,border_val,change_val,cardinal_only);
	FloodFill(map,x+1,y+1,border_val,change_val,cardinal_only);
	FloodFill(map,x-1,y+1,border_val,change_val,cardinal_only);
}

We simply input exactly the same arguments that the initial FloodFill() call received, except that we alter the x and y to correspond to the cells we want to check next, north, west, east and south. If we have set cardinal_only to false, that means we also want to check the inter-cardinal directions, so we do that in the if statement.

Beginners Note: You might see the ! in front of cardinal_only. What's that all about? Well, ! is basically saying "not" (it always reminds me of Borat...Nooooot!). It's got to do with whether a value is true or false. We can use ! in two ways. Firstly, we can set a boolean (a true or false statement) to it's opposite counterpart. if my_var is true and we run this line: my_var = !my_var; then my_var will end up being false after that. Conversely, if my_var is false and we run the exact same line, then my_var will end up being true. It simply switches between the two. The second use is checking to see if something is false. Let's have a look at two if statements:

if (my_var) { }

if (!my_var) { }

The first if statement will only run if my_var is equal to true (well, kind of, GMS doesn't have proper booleans, so it does a funny thing where any value greater than or equal to 0.5 is considered true and any value below 0.5 is considered false...Although it does have true or false keywords, which correspond to 1 and 0 internally). The second if statement will only run if my_var is false ("not" my_var). Those previous two statements are exactly equivalent to:

if (my_var == true) { }

if (my_var == false) { }

So we are simply checking to see if cardinal_only is false. It's just a little bit less typing.

That’s it. No really, that’s it. We’ve got flood fill done now. Let’s have a look at it as a whole:

///@func	FloodFill()
///@param	map				The map we are using (a 2D array)
///@param	x				The starting x position to flood fill from
///@param	y				The starting y position to flood fill from
///@param	border_val		The value we consider a border
///@param	change_val		The value we want to change each flood filled cell to
///@param	cardinal_only	Set to true if we only want to check cardinal directions, set to false if we want to include inter-cardinal directions as well
function FloodFill(map,x,y,border_val,change_val,cardinal_only) {
	
	// Check if the current cell is out of bounds
	if (x < 0 || y < 0 || x >= array_length(map) || y >= array_length(map[0])) {
		return;
	}
	// Check if the current cell is either a border value or has already been assigned the change value 
	if (map[x][y] == border_val || map[x][y] == change_val) {
		return;
	}
	
	// If neither of the previous is true, we assign the current cell the change value
	map[x][y] = change_val;
	
	// Now we run FloodFill() from inside of FloodFill() for each of the cardinal directions
	FloodFill(map,x+1,y,border_val,change_val,cardinal_only);
	FloodFill(map,x-1,y,border_val,change_val,cardinal_only);
	FloodFill(map,x,y+1,border_val,change_val,cardinal_only);
	FloodFill(map,x,y-1,border_val,change_val,cardinal_only);
	
	if (!cardinal_only) {
		// And if cardinal_only is not true, we do the same for the inter-cardinal directions
		FloodFill(map,x+1,y-1,border_val,change_val,cardinal_only);
		FloodFill(map,x-1,y-1,border_val,change_val,cardinal_only);
		FloodFill(map,x+1,y+1,border_val,change_val,cardinal_only);
		FloodFill(map,x-1,y+1,border_val,change_val,cardinal_only);
	}
}

It’s a surprisingly simple piece of code, but it really displays the power of recursion. By rerunning this code again and again with slightly altered values, we can intelligently flood fill an entire area, no matter what twists and turns it contains. Pretty neat.


SLOW MOTION

If you implement the above function, flood fill will instantly execute and fill all available tiles in a single step. So how did I make the gif slowly spread out?

I did this by implementing an altered form of recursion in an alarm. First, I’ll show the code and then run through a brief explanation of what is happening.

Firstly, we need to do a little setup in the Create Event of the instance running the flood fill.

fill_queue = ds_queue_create();

border_val = SOLID;
change_val = FILLED;
cardinal = true;
already_checked = array_create(map_width*map_height,false);

Here, we’re creating a queue that we’re going to be storing the cells that need to be filled next in. This is the “recursion” part of this code. It acts the same way as the FloodFill() function, except instead of calling FloodFill() again, we are simply adding the cells to the queue. Then we have our border_val, change_val and cardinal like we have in the FloodFill() function. border_val and change_val should hold the macros we are interested in checking for and filling, here I’m using two macros SOLID and FILLED (with the map already being populated with these macros somehow). Now on to the alarm code.

repeat (ds_queue_size(fill_queue)) {
	if (ds_queue_size(fill_queue) > 0) {
		alarm[5] = 15;
	}
	else {
		show_debug_message("Finished");
		exit;
	}

	pos = ds_queue_dequeue(fill_queue);
	xx = pos[0];
	yy = pos[1];

	var _repeat = true;
	if (xx < 0 || yy < 0 || xx >= array_length(map) || yy >= array_length(map[0])) {
		_repeat = false;
	}
	if (_repeat) {
		map[xx][yy] = change_val;
		var nx = xx+1;
		var ny = yy;
		var key = Pos([nx,ny],map_height);
		if (nx < map_width && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
			already_checked[key] = true;
			ds_queue_enqueue(fill_queue,[nx,ny]);
		}
		nx = xx-1;
		ny = yy;
		key = Pos([nx,ny],map_height);
		if (nx >= 0 && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
			already_checked[key] = true;
			ds_queue_enqueue(fill_queue,[nx,ny]);
		}
		nx = xx;
		ny = yy+1;
		key = Pos([nx,ny],map_height);
		if (ny < map_height && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
			already_checked[key] = true;
			ds_queue_enqueue(fill_queue,[nx,ny]);
		}
		nx = xx;
		ny = yy-1;
		key = Pos([nx,ny],map_height);
		if (ny >= 0 && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
			already_checked[key] = true;
			ds_queue_enqueue(fill_queue,[nx,ny]);
		}
		if (!cardinal) {
			nx = xx+1;
			ny = yy-1;
			key = Pos([nx,ny],map_height);
			if (nx < map_width && ny >= 0 && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
				already_checked[key] = true;
				ds_queue_enqueue(fill_queue,[nx,ny]);
			}
			nx = xx+1;
			ny = yy+1;
			key = Pos([nx,ny],map_height);
			if (nx < map_width && ny < map_height && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
				already_checked[key] = true;
				ds_queue_enqueue(fill_queue,[nx,ny]);
			}
			nx = xx-1;
			ny = yy+1;
			key = Pos([nx,ny],map_height);
			if (nx >= 0 && ny < map_height && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
				already_checked[key] = true;
				ds_queue_enqueue(fill_queue,[nx,ny]);
			}
			nx = xx-1;
			ny = yy-1;
			key = Pos([nx,ny],map_height);
			if (nx >= 0 && ny >= 0 && map[nx][ny] != border_val && map[nx][ny] != change_val && already_checked[key] == false) {
				already_checked[key] = true;
				ds_queue_enqueue(fill_queue,[nx,ny]);
			}
		}
	}
}

What the alarm does is firstly it repeat itself as many times as there are cells in the queue. This is a method of speeding up the flood fill. You could totally remove the repeat (ds_queue_size(fill_queue)) { line (and the corresponding closing curly bracket at the very end) and the flood fill would still happen, it would just be much slower.

Then we check to see if there are any cells in the queue. If there’s not, we know we’ve flooded all available cells and we exit the alarm without setting it again. If, on the other hand, queue still has cells left, we set the alarm again.

Then we grab the next cell out of the queue and grab the coordinate variables out of the cell array. We then check to see if the coordinates are inside the bounds of the map (which is slightly redundant, no cell should be added to the queue if it is out of bounds, but it never hurts to have multiple checks for this sort of thing). We use the _repeat variable here so that if the current cell IS out of bounds, _repeat is false and it won’t try to add any of it’s neighbours to the queue. If the cell is inside the bounds of the map, firstly we set that cell to the fill we want to fill with (change_val) and then we start checking it’s neighbours. There’s a function in there called Pos() which converts the dual coordinates into a single unique integer (read #5: A* Is Born (Pathfinding’s Greatest Hits) for an in-depth explanation of Pos()). Here’s the code for Pos().

///@func                    Pos(cell,map_height);
///@desc                    Returns the position of the cell as a single integer
///@param {array} cell      An array containing the coordinates of the cell we are looking at
///@param {int} _map_height The height of the map (unfortunately we have to pass this in as it is a static variable)
static Pos = function(cell,_map_height) {
	return (cell[X]*_map_height+cell[Y]);
}

We need Pos() because we want to be able to check whether the cell we are thinking of adding to the queue has already been checked. By condensing it’s coordinates to a single unique number, we can use that number as a “key” in an array already_checked (which we setup in the Create Event and to begin with, has every entry set to false) to check to see if we have already added that cell to the queue. If already_checked[key] == false we know we haven’t added that cell to the queue.

So we check to see if the cell we are thinking of adding to the queue is be out of bounds, we check to see if it is the border_val (which we don’t want to fill), we check to see that it hasn’t already been filled to change_val and we check to see if we haven’t already added it to the queue using the already_checked array.

If all of those checks come back false, we know that we want to fill that cell, so we mark it’s position in already_checked array as true and we add it to the queue.

Do that for all the directions we want to check (the cardinal variable tells us if we are filling the inter-cardinal directions or not) and there we go, we have a flood fill algorithm that doesn’t use the recursion we use for the original FloodFill() function, and one that “runs over time” rather than being an instant fill. Whenever we want the flood fill to start, we simply add a set of coordinates to the fill_queue and then start running the alarm. Let’s see how it would work if we want to flood fill from a place we clicked and the flood fill code is in Alarm[0].

if (mouse_check_button_released(mb_left)) {
	var x1 = mouse_x div CELLSIZE;
	var y1 = mouse_y div CELLSIZE;
	ds_queue_enqueue(fill_queue,[x1,y1]);
	alarm[0] = 1;
}

The only thing there I think needs explaining there is the mouse_x div CELLSIZE stuff. CELLSIZE is a macro we’ve already setup which corresponds to how big we want a cell in our grid to be visually. If we want to convert from the pixel space of the room to grid space, we want to div the pixel coordinates by CELLSIZE (div simply divides while ignoring the remainder, so it will always return a whole number, no decimals). If we want to convert from grid space to pixel space, we multiply the grid coordinates by CELLSIZE and we get the pixel space.

Then we just add those coordinates to the fill_queue as an array and the flood fill should start working it’s magic.


THE NEXT STEP

And thus we’ve had our fill of the flood. It neatly leads on to A*, which involves recursion as well (though not quite the same as flood fill, as we will be using a stack or a queue for the recursion, rather than calling a function, or at least, that’s what I’m planning right now). Flood fill can be useful for all sorts of things. You can figure out the entire area of a particular “room”, no matter what shape you’ve set the boundaries to. You can create an island in the middle of a map and flood fill the outside to be ocean. You can use it in maze creation. There’s a lot of applications for such a simple piece of code.

The next entry will either be focused on A* or room perturbation, depending on what mood I’m in. Once we’ve covered those two topics, we will have a final entry in this “mini-series within the series” that ties it all together and uses both A* and room perturbation to create a dungeon with connected corridors between rooms!

Read on with #5: A* Is Born (Pathfinding’s Greatest Hits)

If you’ve got any comments, criticisms or advice don’t hesitate to comment and let me know, I’m always happy to hear feedback from readers. And if you like what I’m doing, consider supporting me through either a donation at the bottom of the page or buying my game Spaceslingers!


Sign up to get notified whenever I upload a blog post, so you don’t miss any of the next installments!


By RefresherTowel

I'm a solo indie game developer, based in Innisfail, Australia.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s