- 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.
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;
}