# RMMZI need a fast Floodfill Algorithm

#### Aerosys

##### Veteran
Hey all,

for my Plugin, I need a Floodfill Algorithm that returns an array of all islands on a generated Map, whereas an island is an array of all its points. Right now I use an iterative stack approach, but it needs several seconds on a large worldmap (e.g. 256x256 tiles). This is the code I'm having right now. To check if a tile is sea or passable, the function f is called, that is not shown here.

Code:
``````getAllIslands(f) {

const w = this.dataMap.width;
const h = this.dataMap.height;
const toReturn = [];
const visited = MK.createMatrix(w, h);

for (let x = 0; x < w; x++) {
for (let y = 0; y < h; y++) {
const points = this.scan(x, y, visited, f);
if (points)
toReturn.push(points);
}
}
}

scan(x, y, visited, f) {

const w         = this.dataMap.width;
const h         = this.dataMap.height;
const stack     = [];
const toReturn  = [];
function ok(x, y) {
return 0 <= x && x < w && 0 <= y && y < h
&& !(visited[x][y])
&& f(x, y);
}
if (ok(x, y))
stack.push({x: x, y: y});
else
visited[x][y] = true;

while (stack.length > 0) {
const pos = stack.pop();
toReturn.push(pos);
visited[pos.x][pos.y] = true;

if (ok(pos.x - 1, pos.y))   stack.push({x: pos.x - 1, y: pos.y });
if (ok(pos.x, pos.y - 1))   stack.push({x: pos.x,     y: pos.y - 1 });
if (ok(pos.x + 1, pos.y))   stack.push({x: pos.x + 1, y: pos.y });
if (ok(pos.x, pos.y + 1))   stack.push({x: pos.x,     y: pos.y + 1 });
}
}``````

#### Another Fen

##### Veteran
A bit rusty when it comes to Javascript, so not sure if I'll be of much help here.

Have you tried measuring how much time your f-function takes to check every tile or tried your algorithm with a simplified f-function?
For scale, at least on my PC your algorithm takes about 30-80ms for a 256x256 map, and while there obviously will be differences the numbers seem a bit off to me:
Code:
``````var width = 256;
var height = 256;

function getAllIslands(f) {

const w = width; //this.dataMap.width;
const h = height; //this.dataMap.height;
const toReturn = [];
//const visited = MK.createMatrix(w, h);
const visited = new Array(width);
for (let x = 0; x < width; x++) {
visited[x] = new Array(height);
}

for (let x = 0; x < w; x++) {
for (let y = 0; y < h; y++) {
const points = scan(x, y, visited, f); //this.scan(x, y, visited, f);
if (points)
toReturn.push(points);
}
}
};

function scan(x, y, visited, f) {

const w         = width; //this.dataMap.width;
const h         = height; //this.dataMap.height;
const stack     = [];
const toReturn  = [];

function ok(x, y) {
return 0 <= x && x < w && 0 <= y && y < h
&& !(visited[x][y])
&& f(x, y);
}
if (ok(x, y))
stack.push({x: x, y: y});
else
visited[x][y] = true;

while (stack.length > 0) {
const pos = stack.pop();
toReturn.push(pos);
visited[pos.x][pos.y] = true;

if (ok(pos.x - 1, pos.y))   stack.push({x: pos.x - 1, y: pos.y });
if (ok(pos.x, pos.y - 1))   stack.push({x: pos.x,     y: pos.y - 1 });
if (ok(pos.x + 1, pos.y))   stack.push({x: pos.x + 1, y: pos.y });
if (ok(pos.x, pos.y + 1))   stack.push({x: pos.x,     y: pos.y + 1 });

}
};

function fMakeSquareIslands(size) {
return function(x, y) {
return x % (size + 1) !== size && y % (size + 1) !== size;
};
};

var start;
var result;

start = performance.now();
result = getAllIslands(fMakeSquareIslands(Infinity));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");

start = performance.now();
result = getAllIslands(fMakeSquareIslands(Infinity));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");

start = performance.now();
result = getAllIslands(fMakeSquareIslands(Infinity));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");

start = performance.now();
result = getAllIslands(fMakeSquareIslands(0));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");

start = performance.now();
result = getAllIslands(fMakeSquareIslands(1));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");

start = performance.now();
result = getAllIslands(fMakeSquareIslands(10));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");

start = performance.now();
result = getAllIslands(fMakeSquareIslands(100));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");

start = performance.now();
result = getAllIslands(fMakeSquareIslands(Infinity));
console.log(performance.now() - start + " milliseconds for " + result.filter(a => a.length > 0).length + " islands.\n\r");``````

Without additional constraints on the generated islands you obviously won't be able to optimize your code past checking every tile at least once.

Small nitpick otherwise: as far as I remember an empty array is not a falsy object, so your
if (points)
statement should always be fulfilled right now.

Someone else might have better insight here though.

Last edited:

#### Aerosys

##### Veteran
Thanks for taking your time to try it out

Okay your measured time sounds good enough, so it's not caused by my algorithm (probably?). This is my f function
Code:
``(x, y) => noiseMap[x][y] >= minValue``
, whereas noiseMap is an Array of Arrays. I want to get all the islands on a generated Map, so you can read the f function as
Code:
``(x, y) => \$gameMap.isPassable(x, y)``

Small nitpick otherwise: as far as I remember an empty array is not a falsy object, so your
if (points)
statement should always be fulfilled right now.
Thanks for the tip!

### Latest Profile Posts

My Game Development Livestream

Of course, so, someone had covid at work today and I was exposed to them, so, I'm stuck at home for...TWO WEEKS!
oh god I'm going to die
Kind of relieved that I had medibang installed when I need to edit Sprite I was about to download gimp but I remember I had medibang installed lol