从正方形列表创建矩形列表的算法？

Question

我正在尝试为我的 2D 自上而下游戏实现视线可见性/雾war，并发现 this article 具有简单高效的算法涉及在矩形的边缘发射光线以计算要变亮的三角形列表。

但是，我的游戏使用了图块，因此运行这对于每帧玩家周围的 150x150 (22,500) 个图块来说效率非常低。相反，最好将 tile-map 转换为矩形列表，然后运行针对它的视线算法。例如，如果这是我的瓷砖地图（其中 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，等等

是否有一种算法可以从二维图块矩阵生成矩形列表？

Answer 1

有一种天真的方法，例如，在宽度优先填充过程中从左上角开始，这会给您与您正在寻找的结果相似的结果。

宽度优先算法可能如下所示：

结果：

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用于存储矩形信息
按行和列循环遍历图块
检查 tile 是否等于 1，如果不等于，则处理下一个 tile
检查坐标处的tileCache是否不等于0； if != 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 个矩形

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 && 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 && h++;
  }
  return h;
}

从正方形列表创建矩形列表的算法？

Algorithm for creating a list of rectangles from a list of squares?

javascript

algorithm

matrix

tile

roguelike

更新