0

我正在开发一款游戏，我有必要检查给定数字高度图中的闭合路径：服务器和客户端使用此高度图来设置正确的坐标以移动等......现在，当用户继续前进时一个“特殊”的瓷砖，它会亮起......我的问题是：当用户在这些瓷砖上行走时会创建一条包含空瓷砖的封闭路径，服务器应该自动填充这条路径中的瓷砖......

它应该这样做： http ://www.youtube.com/watch?v= kAVUNE2NTUQ - 1:32

我确定我必须在这里或那里使用一些数学，但我不知道如何......我可以做一个“for”循环，但它会太长，问题是服务器需要做这个循环每次用户走路时...提前感谢您的回答，希望有人可以帮助我。

PS：我正在使用 C#

编辑：当用户在瓷砖上行走时，服务器会自动将 heightmap[X, Y] 替换为表示用户颜色的整数

4

3 回答 3

0

问题可以分为两部分：

  1. 检测路径何时关闭。一种方法是在路径中的连续图块之间建立链接：当您迈出一步时，如果您的一个新邻居以前曾被访问过，并且您无法在当前邻居中追踪您的路径回到它，那么您已经关闭了路径（您可能需要建立额外的链接来处理沿着您的路径返回的情况）。这也将告诉您内部区域位于路径的哪一侧（左侧或右侧）。在方格纸上玩这个，它应该变得清晰。每一步都是 O(1)。
  2. 填充封闭区域。一旦您找到该区域中的单个图块，迭代其邻居，然后是它们的邻居，依此类推。对于面积为 n 的区域，这在时间上为 O(n)，在内存中平均为 O(sqrt(n))，具体取决于几何形状（最坏情况下为 O(n)）。
于 2010-09-28T12:09:56.093 回答
0

“问题是每次用户走路时服务器都需要执行循环”......

您可以通过为游戏中的每个图块分配一个唯一的整数，拥有一个包含图块数量的数组，然后为每一步在数组中标记此图块，可以消除骑车走过的图块。当然，还要检查之前是否已经走过瓦片（即它是否在数组中被标记），如果有，你有一个循环（可能是零区域）。这种方法没有在步行瓷砖等上循环，而只是对每一步进行一次查找。

于 2010-09-28T02:49:25.050 回答
0

假设您有一个矩形字段，左上角位于 (0, 0) 中，右下角位于 (M, N) 中。然后您可以使用以下伪代码填充算法：

find the upper and bottom cells of the path (yTop, yBottom)

for (int y = yTop; y != yBottom; ++y)
{
    find leftmost and rightmost path cells (xLeft, xRight) for that y
    bool isInside = true;
    for (int x = xLeft+1; x<xRight; ++x)
    {
        if ((x, y) is path cell)
            isInside = !isInside;
        if (isInside)
            fill(x, y);
    }
}
于 2010-09-28T12:27:49.337 回答