Every now and then I like to deep-dive into an algorithm I’ll probably never use in my working life. This time, the culprit is the flood fill algorithm. I recently answered a StackOverflow post which sparked my interest. In this blog, I’ll review various algorithm implementations and uncover their strengths and weaknesses with examples. So if that sounds like something you’d enjoy, make yourself a cuppa sit back and fill your boots.
If you’ve used paint, then you’ve probably used a bucket tool. And if you haven’t used paint at all, then that’s a more interesting story. Below is a quick demo of me using a flood fill algorithm in Microsoft paint:
So the flood fill algorithm is just filling the pixels within a shape a certain colour. There are a few different algorithms to choose from.
All of the code I’ve written for this blog can be found here.
Stack-based recursive flood fill
From the Wikipedia page the first algorithm you’ll see is the Stack-based recursive implementation. Let’s start with that:
Flood-fill (node):
1. If node is not Inside return.
2. Set the node
3. Perform Flood-fill one step to the south of node.
4. Perform Flood-fill one step to the north of node
5. Perform Flood-fill one step to the west of node
6. Perform Flood-fill one step to the east of node
7. Return.I’ll use a grid to make it easier to visualise the algorithms. Usually, you’d be changing pixels rather than cells of a grid, but the same premise applies:
const GRID_SIZE = 50;
function setGrid() {
for (let i = 0; i < GRID_SIZE; i++) {
grid[i] = [];
for (let j = 0; j < GRID_SIZE; j++) {
grid[i][j] = '#FFFFFF';
}
}
drawShape();
}
...
function drawShape() {
let gap = 5;
for (let i = gap; i < GRID_SIZE - gap; i++) {
grid[i][gap] = '#000000';
grid[gap][i] = '#000000';
grid[GRID_SIZE - (gap + 1)][i] = '#000000';
grid[i][GRID_SIZE - (gap + 1)] = '#000000';
}
}The code above creates a 50×50 grid with a simple square in the middle:
Starting off with this let’s implement the algorithm:
class RecursiveFill {
fill(x, y, colour) {
if (isValidSquare(x, y, colour)) {
grid[x][y] = '#367588'
this.fill(x + 1, y, colour);
this.fill(x - 1, y, colour);
this.fill(x, y + 1, colour);
this.fill(x, y - 1, colour);
}
}
}The recursive fill algorithm is really simple, the function takes 3 arguments, the x, y and the colour of the first clicked cell. If the cell is valid, then we set the colour and then call the function again with 4 directions, right, left, up and down.
If you’re interested in the isValidSquare function — which all of the following algorithms will use:
function isValidSquare(x, y, colour) {
return x > 0 && x < width && y > 0 && y < height && grid[x][y] === colour;
}It’s simply ensuring the x and y are within the canvas and that the cell is the correct colour.
Executing this looks like:
That’s pretty cool. Let’s make the grid a little more interesting:
We’ll use this grid for the rest of the algorithms.
Iterative stack flood fill
The next step — when you start getting a tonne of stack overflows — is to convert your recursive algorithm into an iterative one.
So rather than calling the function again with the different directions we just add the object to a stack which will be evaluated later:
class StackFill {
fill(x, y, colour) {
let stack = [{ x, y, colour }];
while (stack.length > 0) {
let current = stack.pop();
for (let i = 0; i < directions.length; i++) {
let child = {
x: current.x + directions[i][0],
y: current.y + directions[i][1],
colour
}
if (isValidSquare(child.x, child.y, child.colour)) {
grid[child.x][child.y] = '#367588'
stack.push(child);
}
}
}
}
}Once again the algorithm takes the x, y and colour of the clicked cell. We’re then creating a new object with those values and adding it to a stack. Then we’re looping the stack whilst it still has items in it. The line let current = stack.pop() takes an element from the top of the stack and then we’re looping through the directions — the 4 directions have been put into an array to prevent writing the same code 4 times — creating a new object for each of the directions and then checking to see if that object is valid, changing the colour then adding it to the stack.
Here’s how the iterative stack flood fill looks:
Iterative queue flood fill
Iterative queue flood fill is much the same as the iterative stack flood fill apart from the data structure; rather than adding to a stack, we’re adding to a queue.
class QueueFill {
fill(x, y, colour) {
let queue = [{ x, y, colour }];
while (queue.length > 0) {
let current = queue.shift(0);
for (let i = 0; i < directions.length; i++) {
let child = {
x: current.x + directions[i][0],
y: current.y + directions[i][1],
colour
}
if (isValidSquare(child.x, child.y, child.colour)) {
grid[child.x][child.y] = '#367588'
queue.push(child);
}
}
}
}
}
Span fill
Span fill is a really cool algorithm, given a point it finds the edges filling from the left side to the right then you it scans above and below the given line looking for new seed points.
class SpanFill {
fill(x, y, colour) {
let stack = [{ x, y, colour }];
while (stack.length > 0) {
let {x, y, colour} = stack.pop();
let lx = x;
while (isValidSquare(lx, y, colour)) {
grid[lx][y] = '#367588'
lx = lx -1;
}
let rx = x + 1;
while (isValidSquare(rx, y, colour)) {
grid[rx][y] = '#367588'
rx = rx + 1;
}
this.scan(lx, rx - 1, y + 1, stack, colour);
this.scan(lx, rx - 1, y - 1, stack, colour)
}
return;
}
scan(lx, rx, y, stack, colour) {
for (let i = lx; i < rx; i++) {
if (isValidSquare(i, y, colour)) {
stack.push({x: i, y: y, colour: colour});
}
}
}
}So similar to the previous two algorithms we’re adding an object to a data structure, in this example, we’re using a stack. When we’re in the loop we take one off the stack and then set a new variable lx which represents the left x. With the left x it then loops through decrementing 1 from the lx to find the edge. We then repeat this process with the right x, trying to find the last unfilled x on the right. When we’ve got both of these values and we’ve filled the gap between them, we then start looking at the lines above and below.
Here’s how the span algorithm looks:
Comparing the algorithms
50×50 grid:
| Algorithm | Nodes expanded | Elapsed Time (ms) |
| Recursive | 5777 | 1 |
| Stack | 5780 | 2 |
| Queue | 5780 | 2 |
| Span | 7072 | 1 |
100×100 grid:
| Algorithm | Nodes expanded | Elapsed Time (ms) |
| Recursive | 30977 | 5 |
| Stack | 30980 | 5 |
| Queue | 30980 | 5 |
| Span | 38472 | 4 |
200×200 grid:
| Algorithm | Nodes expanded | Elapsed Time (ms) |
| Recursive | N/A (max call stack) | N/A (max call stack) |
| Stack | 141380 | 9 |
| Queue | 141380 | 12 |
| Span | 175972 | 12 |
400×400 grid:
| Algorithm | Nodes expanded | Elapsed Time (ms) |
| Recursive | N/A (max call stack) | N/A (max call stack) |
| Stack | 602180 | 23 |
| Queue | 602180 | 30 |
| Span | 741172 | 16 |
800×800 grid:
| Algorithm | Nodes expanded | Elapsed Time (ms) |
| Recursive | N/A (max call stack) | N/A (max call stack) |
| Stack | 1926548 | 74 |
| Queue | 1926548 | 79 |
| Span | 2405408 | 71 |
As expected the Span algorithm — despite having to expand the most nodes — seemed to perform the best. Stack and queue weren’t too far behind though. However, there are many optimisations that can be made to the Span algorithm which are glaringly obvious from the results.
There are other algorithms that perform flood fill that I’ve not covered in this blog, an honourable mention would be the Walk-based filling (Fixed-memory method).
And that’s pretty much all there is to it, if you liked this blog then please sign up for my newsletter and join an awesome community!
[…] plug, but relevant: I’ve created a blog comparing the different flood fill algorithms using […]