计算正方形网格中区域面积的算法

Question

我正在开发一款使用 tilemap 的游戏。地图上的方块可以是墙，也可以是空的。我正在尝试开发的算法应该在地图上取一个点，return 从该点可以到达的像元数（等于包含该点的扇区面积）。

让执行算法的函数采用二维数组形式的 x 坐标、y 坐标和地图。

function sectorArea(x_coord,y_coord,map) { ... }

假设地图看起来像这样（其中 1 代表墙）：

map = [0,0,1,0,0,0],
      [0,0,1,0,0,0],
      [1,1,1,0,0,0],
      [0,0,0,0,0,0]

然后sectorArea(0,0,map) == 4和sectorArea(4,0,map) == 15。

我天真的实现是递归的。目标单元格被传递给 go 函数，然后该函数在任何相邻的空单元格上递归 - 最终传播到该扇区中的所有空单元格。它运行太慢并且很快达到调用堆栈限制：

function sectorArea(x_coord,y_coord,map) {
    # First convert the map into an array of objects of the form:
    # { value: 0 or 1,
    #   visited: false }
    objMap = convertMap(map);

    # The recursive function:
    function go(x,y) {
        if ( outOfBounds(x) || outOfBounds(y) || 
             objMap[y][x].value == 1 || objMap[y][x].visited )
            return 0;
        else
            objMap[y][x].visited = true;
            return 1 + go(x+1,y) + go(x-1,y) + go(x,y+1) + go(x,y-1);
    }
    return go(x_coord,y_coord);
}

谁能推荐一个更好的算法？如果非确定性解决方案足够准确，它实际上会很好，因为速度是主要问题（该算法可以在单个滴答期间在不同点上调用 3 或 4 次）。

Answer 1

也许你可以加速算法本身。 Wikipedia 表明扫描线方法是有效的。

关于重复调用：可以缓存结果，这样就不用每次都运行重新计算面积了。

一种方法可能是在您的图块旁边保留一个整数区域地图。这表示几个区域，其中一个特殊值，例如 -1，表示没有区域。（此区域地图还用作您的 visited 属性。）除此之外，保留一个（简短的）区域数组及其面积。

在你上面的例子中：

当你计算(0, 0)的面积时，你会将0分配给西北角的四块地砖。您还将面积 4 附加到面积数组。
当您计算 (0, 1) 的面积时，您会注意到该坐标的区域地图的值为零，而不是 -1。那就是说面积已经算出来了
当你计算(4, 4)的面积时，你在区域地图中找到-1。这意味着该区域尚未计算。这样做，用 1 标记区域并将新区域 15 附加到区域数组。

我不知道看板多久换一次。当您必须重新计算区域时，清空区域地图并清空数组列表。

区域地图只创建一次，不会在每次更新时重新创建。（当 objMap 经常重新创建而不是仅仅被覆盖时，我认为这是您代码中的潜在瓶颈。）

计算正方形网格中区域面积的算法

Algorithm for calculating the area of a region in a grid of squares

algorithm

area

sector