1

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

让执行该算法的函数获取一个 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 次）。

4

1 回答 1

1

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

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

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

在上面的示例中：

  • 当你计算 的面积时(0, 0)，你会将 0 分配给西北角的四个瓦片。您还将面积 4 附加到面积数组中。

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

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

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

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

于 2015-01-14T21:19:21.300 回答