检查数字高度图中的闭合路径

Question

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

它应该执行如下操作： http://www.youtube.com/watch?v=kAVUNE2NTUQ - 1:32

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

PS：我正在使用 C#

编辑：当用户在图块上行走时，服务器会自动将高度图 [X, Y] 替换为代表用户颜色的整数

Answer 1

该问题可以分为两个部分：

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

Answer 2

假设您有一个矩形区域，左上角位于 (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);
    }
}

Answer 3

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

您可以通过为游戏中的每个图块分配一个唯一的整数、具有包含图块数量的数组，以及然后对于每个步骤，在数组中标记此图块。当然，还要检查该图块之前是否已经走过（即是否在数组中标记），如果有，则有一个循环（可能是零面积）。这种方法没有循环遍历已走的图块等，而只是对每个步骤进行一次查找。