RMMZ I need a fast Floodfill Algorithm

[Aerosys]

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.

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);
            }
        }
        return toReturn;
    }
    
    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 });
        }
        return toReturn;
    }

 

[Another Fen]

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:

Spoiler: Testcode

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);
        }
    }
    return toReturn;
};
  
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 });
      
    }
    return toReturn;
};


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.

 

[Aerosys]

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

(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

(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!