Basic Idea of Using Breadth-first search (BFS) in Flood-Fill Algorithm
Reminder
It's been a while since we published this blog post. Some of the information may be outdated.
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored. (From Wikipedia)
General Goal
In a two-dimensional array, setting up a random starting point value to 1. For each index in the Moore Neighborhood (Light Green) with the value 0, change the value to the center index + 1 (Yellow).
So, a 10*10 two-dimensional array after being filled would output:
10 10 10 10 10 10 10 10 10 10
10 9 9 9 9 9 9 9 9 9
10 9 8 8 8 8 8 8 8 8
10 9 8 7 7 7 7 7 7 7
10 9 8 7 6 6 6 6 6 6
10 9 8 7 6 5 5 5 5 5
10 9 8 7 6 5 4 4 4 4
10 9 8 7 6 5 4 3 3 3
10 9 8 7 6 5 4 3 2 2
10 9 8 7 6 5 4 3 2 1Of course, we need to take care of any impassible position (-1):
10 10 10 10 10 10 10 10 10 -1
10 9 9 -1 9 -1 9 9 9 9
-1 9 8 8 8 8 8 8 8 8
10 9 8 7 7 7 7 7 7 7
10 9 8 7 6 6 6 6 6 6
-1 9 8 7 6 5 5 5 5 5
-1 9 8 -1 6 5 4 4 4 -1
10 9 8 7 -1 5 4 3 3 3
-1 9 8 7 6 5 4 3 2 2
10 9 8 7 6 5 4 3 2 1The impassible position should not be filled or overridden, and it also should not be set as the center of the Moore Neighborhood. (-1+1 is always 0)
Direction
There are multiple approaches to a flood-fill algorithm. I use Breadth First Search, BFS in this case. The fundamental idea of BFS is to insert unchecked nodes to the tail of the queue. A queue is following the First In First Out, FIFO rule.
▲ （The photo above is from: dev.to)
We will not discuss how to achieve a queue. We can add #include <queue> to invoke the queue data structure in C++.
Basic Idea：
- Add starting point (x, y coordinate) to the queue.
While the queue is not empty
- Get the value of the front point (x, y coordinate), and remove it from the queue.
- Set this point (x, y coordinate) as the center index of the Moore Neighborhood.
If it's Moore Neighborhood legal (not out of the boundary, not -1, unfilled before, which means 0)
- Change the value of this point (x, y coordinate) to be the center index + 1.
- Put this point (x, y coordinate) to the queue.
- Back to step 2
▲ Demostration（Around 3-4 minutes long）
C++ Code
#include <queue>
...
...
// check if the coordinate is legal
bool validCoord(int indexX, int indexY, int gridWidth, int gridHeight) {
if (indexX < 0 || indexY < 0) {
return false;
}
if (indexX >= gridWidth || indexY >= gridHeight) {
return false;
}
return true;
}
void bfs(int** grid, int gridWidth, int gridHeight, int cIndexX, int cIndexY) {
grid[cIndexY][cIndexX] = 1;
// Create two new queue to store x and y coordinate
std::queue<int> queueX;
std::queue<int> queueY;
// Store staring point x coordinate to the queueX
queueX.push(cIndexX);
// Store staring point y coordinate to the queueY
queueY.push(cIndexY);
// If both of the queue is NOT empty
// (Of course they should be emptyed simultaneously, or something goes wrong)
while (!queueX.empty() && !queueY.empty()) {
// Get the front value from queueX queue
cIndexX = queueX.front();
// Remove it from queueX queue
queueX.pop();
// Get the front value from queueY queue
cIndexY = queueY.front();
// Remove it from queueY queue
queueY.pop();
// Get the value of the center index
int centerEleValue = grid[cIndexY][cIndexX];
// 8 possibilities in a Moore Neighborhood N,S,W,E,NW,NE,SW,SE
// NW
// Get current Moore Neighborhood index
int nIndexX = cIndexX - 1;
int nIndexY = cIndexY - 1;
// check if the coordinate is not legal, skip it
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
// Check if the index value is 0, or it might be filled before, or it might be an impassible
if (grid[nIndexY][nIndexX] == 0) {
// change the value to be the center index + 1.
grid[nIndexY][nIndexX] = centerEleValue + 1;
// Add current Neighborhood x, y coordinate to their queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// W
nIndexX = cIndexX - 1;
nIndexY = cIndexY;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// SW
nIndexX = cIndexX - 1;
nIndexY = cIndexY + 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// N
nIndexX = cIndexX;
nIndexY = cIndexY - 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// S
nIndexX = cIndexX;
nIndexY = cIndexY + 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// NE
nIndexX = cIndexX + 1;
nIndexY = cIndexY - 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// E
nIndexX = cIndexX + 1;
nIndexY = cIndexY;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// SE
nIndexX = cIndexX + 1;
nIndexY = cIndexY + 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
}
}Obviously, it looks tedious. In fact, we can use two for loops instead
For more details about how to iterate a Moore Neighborhood, please refer this post
#include <queue>
...
...
// check if the coordinate is legal
bool validCoord(int indexX, int indexY, int gridWidth, int gridHeight) {
if (indexX < 0 || indexY < 0) {
return false;
}
if (indexX >= gridWidth || indexY >= gridHeight) {
return false;
}
return true;
}
void bfs(int** grid, int gridWidth, int gridHeight, int cIndexX, int cIndexY) {
grid[cIndexY][cIndexX] = 1;
// Create two new queue to store x and y coordinate
std::queue<int> queueX;
std::queue<int> queueY;
// Store staring point x coordinate to the queueX
queueX.push(cIndexX);
// Store staring point y coordinate to the queueY
queueY.push(cIndexY);
// If both of the queue is NOT empty
// (Of course they should be emptyed simultaneously, or something goes wrong)
while (!queueX.empty() && !queueY.empty()) {
// Get the front value from queueX queue
cIndexX = queueX.front();
// Remove it from queueX queue
queueX.pop();
// Get the front value from queueY queue
cIndexY = queueY.front();
// Remove it from queueY queue
queueY.pop();
// Get the value of the center index
int centerEleValue = grid[cIndexY][cIndexX];
// nIndexY, nIndexY is neighborhood index of cIndexX, cIndexY
// Find right corner of moore neighborhood
int nIndexX = cIndexX - 1;
int nIndexY = cIndexY - 1;
// Use for loop iterate the moore neighborhood
for (int y = nIndexY; y < nIndexY + 3; ++y) {
for (int x = nIndexX; x < nIndexX + 3; ++x) {
// Check if it is the center point
if (y == cIndexY && x == cIndexX) {
continue;
}
// Check if the index is valid
if (validCoord(x, y, gridWidth, gridHeight)) {
// if the grid is unexplored
if (grid[y][x] == 0) {
// set the value +1 to the center element
grid[y][x] = centerEleValue + 1;
// then push into queue
queueX.push(x);
queueY.push(y);
}
}
}
}
}
}
Comments are disabled.