Aerosys

Veteran
Veteran
Joined
Apr 23, 2019
Messages
512
Reaction score
486
First Language
german
Primarily Uses
RMMZ
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);
            }
        }
        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

Veteran
Veteran
Joined
Jan 23, 2013
Messages
604
Reaction score
315
First Language
German
Primarily Uses
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);
        }
    }
    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.
 
Last edited:

Aerosys

Veteran
Veteran
Joined
Apr 23, 2019
Messages
512
Reaction score
486
First Language
german
Primarily Uses
RMMZ
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 Threads

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
AAAAAAAAi.png
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

Forum statistics

Threads
110,368
Messages
1,052,667
Members
143,402
Latest member
IBanana
Top