Aerosys

Veteran
Veteran
Joined
Apr 23, 2019
Messages
493
Reaction score
460
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
586
Reaction score
297
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
493
Reaction score
460
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

Do you like to practice level design? I do hahahaha! It's not from a specific game, it's just some tests...Fase 1.png
I really need a better indicator of where you can jump up and down though I feel... otherwise I like how this turned out for the first part of the first dungeon of the game.
@Shaz needs to make a website for his plugins. (it can be done easily for free with google sites.) I can't find a database of them anywhere!
Dion2.jpg

testing #2

Forum statistics

Threads
109,128
Messages
1,042,381
Members
141,629
Latest member
YOURBESTFRIIEND
Top