Aerosys

Veteran
Veteran
Joined
Apr 23, 2019
Messages
488
Reaction score
459
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
583
Reaction score
287
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
488
Reaction score
459
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 Posts

Latest Profile Posts

Today we be doing an unscheduled stream! Lets get some work done on the titlescreen for Lightestone! <3
www.twitch.tv/riazey
I can't believe it... my mom is going to sign me up for the Planet Fitness down the street! I need to lower my cholesterol according to my doctor, and I'll need to lose some weight to fit into Helen Henny's skirt (I ordered a skirt for my mascot outfit and realized it was a bit too small). My doctor says I need to lose weight anyway.
I blame my lilest bro for the duck suit. Sketched it and realized it had to be added to a mock fashion magazine cover. The titles are actually inside jokes about the place this NPC is from.
EvKECQJVEAw3Qux
Kes
After a few hectic months, my hiatus is over, and I'm now back. Good to see so many familiar names posting. And a forum update while I was away.
V1.3 of Demo, a new concept artist on the team, character voices are coming into light more... I'm happy to say that the fangame is making good progress.

Forum statistics

Threads
108,855
Messages
1,040,094
Members
141,300
Latest member
Torcham
Top