Algorithm Fill Closed Area in Tile map JavaScript

Question

sorry for my english.

I have a problem and what is the next:

Example, i have a map:

var map = 
    [[0,1,1,0,0,0,0,0,0,0],
    [0,1,0,1,0,1,1,0,0,0],
    [0,1,0,0,1,0,0,1,0,0],
    [0,1,0,0,0,0,0,0,1,0],
    [0,0,1,0,0,0,0,1,0,0],
    [0,0,0,1,0,0,0,1,1,0],
    [0,0,1,0,0,0,1,0,0,0],
    [0,1,0,0,0,0,0,1,0,0],
    [1,0,0,1,1,1,0,1,0,0],
    [0,1,1,0,0,1,1,1,0,0]];

Which contains a series of numbers 0 and 1 (For example). I need to fill in all the closed boxes that are on this map, for example using the number 2.

Example:

var map = 
    [[0,1,1,0,0,0,0,0,0,0],
    [0,1,2,1,0,1,1,0,0,0],
    [0,1,2,2,1,2,2,1,0,0],
    [0,1,2,2,2,2,2,2,1,0],
    [0,0,1,2,2,2,2,1,0,0],
    [0,0,0,1,2,2,2,1,1,0],
    [0,0,1,2,2,2,1,0,0,0],
    [0,1,2,2,2,2,2,1,0,0],
    [1,2,2,1,1,1,2,1,0,0],
    [0,1,1,0,0,1,1,1,0,0]];

Taking into consideration that:

1. Just as in this example there is only one closed figure, there can be several closed figures
2. The sides of the map will not be taken into consideration
3. If it is of any use, the numbers 1 (which would be the solid), will be generated as time passes, so the map will be constantly changing (like strokes in an array)

I found a method called "Flood Fill" but however it depends on a starting point, in this case it has no starting point. The idea is that the code is in charge of finding the closed areas and filling them automatically.

Answer 1

If you don't have starting coordinates, one method to identify every 0 to be filled is to identify every 0 on the edges. Each of these zeros should not be filled, and each 0 eventually adjacent to these 0s should also not be filled. So, if you take the edge 0s as the "starting point" and iterate through all of their recursive neighbors, you'll have identified each coordinate which is a 0 but should not be filled in.

Then, it's simple: just iterate over the input, and for every 0, check to see if the current coordinate is in that set of coordinates that shouldn't be filled. If the coordinate is not in that set, replace with a 2.

var map = 
    [[0,1,1,0,0,0,0,0,0,0],
    [0,1,2,1,0,1,1,0,0,0],
    [0,1,2,2,1,2,2,1,0,0],
    [0,1,2,2,2,2,2,2,1,0],
    [0,0,1,2,2,2,2,1,0,0],
    [0,0,0,1,2,2,2,1,1,0],
    [0,0,1,2,2,2,1,0,0,0],
    [0,1,2,2,2,2,2,1,0,0],
    [1,2,2,1,1,1,2,1,0,0],
    [0,1,1,0,0,1,1,1,0,0]];
const height = map.length;
const width = map[0].length;

const edgeZerosCoords = new Set();
map.forEach((arr, row) => {
  arr.forEach((num, col) => {
    if (num === 0 && (row === 0 || col === 0 || row === width - 1 || col === height - 1)) {
      edgeZerosCoords.add(`${row}_${col}`);
    }
  })
});
const doNotFillCoords = new Set();
const visited = new Set();
const checkCoord = (row, col) => {
  // Verify valid coord:
  if (row < 0 || col < 0 || row === width || col === height) return;
  const str = `${row}_${col}`;
  if (doNotFillCoords.has(str) || visited.has(str)) return;
  visited.add(str);
  const num = map[row][col];
  if (num !== 0) return;
  doNotFillCoords.add(str);
  checkCoord(row + 1, col);
  checkCoord(row - 1, col);
  checkCoord(row, col + 1);
  checkCoord(row, col - 1);
};
for (const str of edgeZerosCoords) {
  const [row, col] = str.split('_').map(Number);
  checkCoord(row, col)
}
map.forEach((arr, row) => {
  arr.forEach((num, col) => {
    const str = `${row}_${col}`;
    if (num === 0 && !doNotFillCoords.has(str)) {
      map[row][col] = 2;
    }
  })
});
console.log(JSON.stringify(map));

Result:

[
  [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 2, 1, 0, 1, 1, 0, 0, 0],
  [0, 1, 2, 2, 1, 2, 2, 1, 0, 0],
  [0, 1, 2, 2, 2, 2, 2, 2, 1, 0],
  [0, 0, 1, 2, 2, 2, 2, 1, 0, 0],
  [0, 0, 0, 1, 2, 2, 2, 1, 1, 0],
  [0, 0, 1, 2, 2, 2, 1, 0, 0, 0],
  [0, 1, 2, 2, 2, 2, 2, 1, 0, 0],
  [1, 2, 2, 1, 1, 1, 2, 1, 0, 0],
  [0, 1, 1, 0, 0, 1, 1, 1, 0, 0]
]