Алгоритм заполнения замкнутой области на карте тайлов JavaScript - PullRequest
Новая
       27

Алгоритм заполнения замкнутой области на карте тайлов JavaScript

0 голосов
/ 21 марта 2020

извините за мой английский sh.

У меня проблема и что дальше:

Например, у меня есть карта: 

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. Так же, как в этом примере есть только одна закрытая фигура, может быть несколько закрытых фигур
  2. Стороны карты не будут учитываться
  3. Если это будет полезно, числа 1 (которые будут solid) будут генерироваться с течением времени, поэтому карта будет постоянно меняться (как штрихи в массиве)

Я нашел метод под названием «Flood Fill», но, тем не менее, он зависит от начальной точки, в этом случае он не имеет начальной точки. Идея состоит в том, что код отвечает за поиск закрытых областей и их автоматическое заполнение.

1 Ответ

0 голосов
/ 21 марта 2020

Если у вас нет начальных координат, один из способов определения каждого 0, который будет заполнен, - это определение каждого 0 на краях. Каждый из этих нулей должен быть заполнен , а не , и каждый 0, в конечном счете смежный с этими 0, также не должен быть заполнен. Итак, если вы возьмете ребра 0 в качестве «начальной точки» и выполните итерацию по всем их рекурсивным соседям, вы определите каждую координату, которая равна 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]
]
...