Блог

Я пытаюсь реализовать видимость прямой видимости / туман войны для моей 2D-игры сверху вниз и нашел эту статью, в которой есть простой и эффективный алгоритм, который включает в себя съемку лучей по краям прямоугольников для вычисления списка треугольников, которые нужно осветлить.

Однако в моей игре используются плитки, поэтому было бы очень неэффективно запускать это против плиток 150×150 (22 500), окружающих игроков в каждом кадре. Скорее, было бы лучше вместо этого преобразовать карту плиток в список прямоугольников, а затем запустить алгоритм прямой видимости против этого. Например, если бы это была моя карта-плитка (где 1-сплошная плитка, а 0 — свободная плитка):

 1 1 1 1 1 1 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
0 0 1 1 0 0 1  
0 0 1 1 1 0 1 
1 0 0 0 0 0 1 
1 1 1 1 1 1 1 
 

Затем вы можете преобразовать это в список прямоугольников, например:

 1 1 1 1 1 1 1 
5 0 0 0 0 0 2 
5 0 0 0 0 0 2 
0 0 6 6 0 0 2  
0 0 6 6 7 0 2 
4 0 0 0 0 0 2 
3 3 3 3 3 3 3
 

В этом результате каждый 1 ссылается на первый прямоугольник, каждый 2 ссылается на второй прямоугольник и т. Д. Это не единственный возможный результат, но один из многих возможных. В принципе, вместо того 7 x 7 = 49 , чтобы проверять плитки, алгоритм должен проверять только 7 прямоугольники, что значительно ускоряет вычисления поля зрения.

Прямоугольники будут иметь такие свойства, как x, y, width, height . В этом случае первый прямоугольник будет выглядеть примерно так x: 0, y: 0, w: 7, h: 1 . Вторым прямоугольником будет x: 6, y: 1, w: 1, h: 5 и т. Д.

Существует ли алгоритм для создания списка прямоугольников из матрицы 2D-плиток?

Существует наивный способ, например, запустить слева вверху процесс заполнения по ширине, который даст вам результаты, аналогичные тем, которые вы ищете.

Вот как может выглядеть первый по ширине алгоритм:

Результаты в:

 1 1 1 1 1 1 1
2 0 0 0 0 0 3
2 0 0 0 0 0 3
0 0 4 4 0 0 3
0 0 4 4 5 0 3
6 0 0 0 0 0 3
6 7 7 7 7 7 7
 

• создайте пустой массив tileCache для хранения обработанных плиток, предварительно заполнив его 0
• создайте массив tileRects для хранения информации о прямоугольнике
• перебирайте плитки по строкам и столбцам
• проверьте, равна ли плитка 1, если нет, перейдите к следующей плитке
• проверьте, не равен ли тайник в координатах 0; если != 0, обработайте следующую плитку
• если это новая плитка, найдите плитки справа, которые находятся 1 , и получите width прямоугольник
• используйте ширину прямоугольника (и x,y), чтобы узнать, какой высоты мы можем сделать прямоугольник, чтобы получить height
• затем используйте x,y,ширину и высоту для создания объекта прямоугольника
• заполните кэш данными

Обратите внимание, что в этом алгоритме есть одна особенность, которая не должна быть проблемой и может быть исправлена, если это проблема. Это позволит перекрывать прямоугольники.

т.е.

 let tiles = [
  [1, 1, 1, 1],
  [0, 1, 1, 0],
  [1, 1, 1, 1],
  [0, 1, 1, 0],
];
 

сгенерирует 3 прямоугольника

 1 1 1 1
0 2 2 0
3 3 3 3
0 2 2 0
 

 let tiles = [
  [1, 1, 1, 1, 1, 1, 1],
  [1, 0, 0, 0, 0, 0, 1],
  [1, 0, 0, 0, 0, 0, 1],
  [0, 0, 1, 1, 0, 0, 1],
  [0, 0, 1, 1, 1, 0, 1],
  [1, 0, 0, 0, 0, 0, 1],
  [1, 1, 1, 1, 1, 1, 1],
];

const tileCache = tiles.map(() => Array(tiles[0].length).fill(0));

const tileRects = [];

function exploreRight(y, x) {
  let w = 1;
  while (tiles[y][x   w] === 1) {
    w  ;
  }
  return w;
}

function exploreDown(y, x, w) {
  let pass = true;
  let h = 1;
  while (pass) {
    for (let $x = x; $x < x   w; $x  ) {
      if (!tiles[y   h] || tiles[y   h][$x] !== 1) {
        pass = false;
        continue;
      }
    }
    pass amp;amp; h  ;
  }
  return h;
}

function fillCache(y, x, h, w, n) {
  for (let $y = y; $y < y   h; $y  ) {
    for (let $x = x; $x < x   w; $x  ) {
      tileCache[$y][$x] = n;
    }
  }
}

let n = 1;
for (let y = 0; y < tiles.length; y  ) {
  for (let x = 0; x < tiles[y].length; x  ) {
    const tile = tiles[y][x];
    const cache = tileCache[y][x];
    if (tile === 0) {
      continue;
    }

    if (cache > 0) {
      continue;
    }

    const w = exploreRight(y, x);
    const h = exploreDown(y, x, w);
    tileRects.push({ y, x, w, h });
    fillCache(y, x, h, w, n);

    if (w > 1) {
      x  = w - 1;
    }
    n  ;
  }
}

console.log(tileCache.map((r) => r.join(" ")).join("n"));

console.log(tileRects); 

Обновить

Если проблема заключается в перекрывающихся квадратах, единственное необходимое изменение заключается в том, что exploreDown метод также должен проверять кэш, а не только плитки. Предполагается, что меньшее количество прямоугольников означает меньшее количество вычислений, но в некоторых случаях перекрытие может быть проблемой.

 function exploreDown(y, x, w) {
  let pass = true;
  let h = 1;
  while (pass) {
    for (let $x = x; $x < x   w; $x  ) {
      if (!tiles[y   h] || tiles[y   h][$x] !== 1) {
        pass = false;
        continue;
      }
      /// change 👇
      if (!tileCache[y   h] || tileCache[y   h][$x] !== 1) {
        pass = false;
        continue;
      }
      // change 👆
    }
    pass amp;amp; h  ;
  }
  return h;
}