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

Question

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

让执行算法的函数采用 x 坐标、y 坐标和 2D 数组形式的映射。

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

也许你可以加快算法本身的速度。维基百科建议扫描线方法是有效的。

至于重复调用：您可以缓存结果，这样您就不必每次都再次运行面积计算。

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

在上面的示例中：

• 当您计算 (0, 0) 的面积时，您将为西北角的四个切片分配 0。您还将区域 4 附加到区域数组。

• 当您计算 (0, 1) 的面积时，您会注意到该坐标的区域地图的值为零，而不是 -1。这意味着面积已经计算好了。

• 当你计算(4, 4)的面积时，你会发现 -1 在区域图中。这意味着该区域尚未计算。这样做，用 1 标记区域并将新区域 15 附加到区域数组中。

我不知道董事会多久更换一次。当必须重新计算区域时，请清空区域映射并清空数组列表。

区域地图仅创建一次，不会为每个刻度重新创建。（我可以将此视为代码中的潜在瓶颈，当objMap经常被重新创建而不仅仅是被覆盖时。