Index: binaries/data/mods/public/maps/random/rmgen/math.js =================================================================== --- binaries/data/mods/public/maps/random/rmgen/math.js +++ binaries/data/mods/public/maps/random/rmgen/math.js @@ -175,3 +175,49 @@ return order; } + +/** + * Flood fill algorithm to verify if all the points are connected against the given list of tileClass + */ +function areConnected(points, tileClasses) +{ + let connectionArray = new Uint8Array(mapSize*mapSize).fill(0); + let initialPos = pickRandom(points); + let tilesToVisit = [new Vector2D(initialPos.x, initialPos.y)]; + let connectionAmount = 0; + while (tilesToVisit.length > 0) { + let position = tilesToVisit.pop(); + let idx = position.x * mapSize + position.y; + if (connectionArray[idx] != 0) { + continue; + } + if (!g_Map.validTilePassable(position)) { + connectionArray[idx] = 1; + continue; + } + let tcValid = true; + for (let tileClass of tileClasses) { + if (tileClass.has(position)) { + connectionArray[idx] = 1; + tcValid = false; + } + } + if (!tcValid) { + continue; + } + connectionArray[idx] = 1; + for (let point of points) { + if (position.x == point.x && position.y == point.y) { + connectionAmount++; + if (connectionAmount == points.length) { + return true; + } + } + } + tilesToVisit.push(new Vector2D(position.x + 1, position.y)); + tilesToVisit.push(new Vector2D(position.x - 1, position.y)); + tilesToVisit.push(new Vector2D(position.x, position.y + 1)); + tilesToVisit.push(new Vector2D(position.x, position.y - 1)); + } + return false; +}