算法在 Tile 地图中填充封闭区域 JavaScript

Question

对不起我的英语。

我有一个问题，接下来是什么：

例如，我有一张地图：

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]];

其中包含一系列数字 0 和 1（例如）。我需要填写这张地图上所有封闭的方框，例如使用数字 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]];

考虑到：

如本例只有一个闭合图形，可以有多个闭合图形
不会考虑地图的边
如果有任何用处，数字 1（即实心）将随着时间的推移生成，所以地图会不断变化（就像数组中的笔画）

我找到了一个名为 "Flood Fill" 的方法，但是它取决于起点，在这种情况下它没有起点。这个想法是代码负责找到封闭区域并自动填充它们。

Answer 1

如果您没有起始坐标，识别每个要填充的 0 的一种方法是识别边缘上的每个 0。这些零中的每一个都应该不被填充，并且最终与这些 0 相邻的每个 0 也不应该被填充。因此，如果您将边 0 作为 "starting point" 并遍历它们的所有递归邻居，您将确定每个坐标为 0 但不应填写。

然后，很简单：只需遍历输入，对于每一个 0，检查当前坐标是否在不应填充的那组坐标中。如果该集合中的坐标不是，请替换为 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));

结果：

[
  [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]
]

算法在 Tile 地图中填充封闭区域 JavaScript

Algorithm Fill Closed Area in Tile map JavaScript

javascript

dictionary

autofill

flood-fill