为什么这种洪水填充方法在减去坐标后会导致堆栈溢出？

Question

为了创建编辑器，我正在尝试为图块系统创建油漆桶样式的洪水填充。

但是，基于四路洪水填充算法会引起问题。 x + 1和y + 1正常工作，但是当它们与x-1和y-1配对时，会导致堆栈溢出。另外，我的比较点是瓷砖的颜色。在某些情况下，它会忽略颜色是否匹配，并在应该退出时仍然覆盖它们。

按照此处的示例算法，此代码看起来像应该工作：

Flood Fill Algorithm Example

但是，如上所述，我自己在C＃中的实现在所有方向上均无法正常工作：

public void FloodFill(int x, int y, Color fillColor, Color oldColor)
{
    if (x < 0 || x >= boardSize) return;
    if (y < 0 || y >= boardSize) return;
    Tile tile = world.GetTileAt(x, y);

    if (tile.currentColor.Equals(fillColor))
    {
        return;
    }

    if (tile.currentColor.Equals(oldColor))
    {
        UpdateTile(tile.currentTile, fillColor);

        FloodFill(x - 1, y, fillColor, oldColor);
        FloodFill(x + 1, y, fillColor, oldColor);
        FloodFill(x, y - 1, fillColor, oldColor);
        FloodFill(x, y + 1, fillColor, oldColor);
    }

        return;
}

我最好的猜测是，它隐喻地跳了过去，但是在比较和返回时不应发生这种情况，以防止执行。这个结论来自对数-在处理正数和负数时，它都会不断跳动。

这是到目前为止的日志：

MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:134)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:136)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:138)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:136)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:138)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:136)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:138)

这是UpdateTile和GetTileAt的代码：

public void UpdateTile(Transform tile, Color color)
{
    Mesh mesh = tile.GetComponent<MeshFilter>().mesh;

    Color32[] nextColor = new Color32[mesh.vertices.Length];

    for (int i = 0; i < nextColor.Length; i++)
    {
        nextColor[i] = color;
    }

    mesh.colors32 = nextColor;
}

public Tile GetTileAt(int x, int y)
{
    if (x > size || x < 0 || y > size || y < 0)
    {
        return null;
    }

    return tiles[x, y];
}

Answer 1

经过数小时的尝试，我终于找到了为什么情况无法正常运行的答案。在进行洪水填充之前，还需要确认一些其他步骤。

（（注意：activeColor是方法之外的公共变量）

private void RevisedFloodFill(int x, int y, Color targetColor)
{
    if (isValid(x, y))
    {
        Tile node = world.GetTileAt(x, y);
        if (node.hasActiveTile)
        {
            if (node.currentColor != activeColor)
            {
                string target = ColorUtility.ToHtmlStringRGB(targetColor);
                string compare = ColorUtility.ToHtmlStringRGB(node.currentColor);

                if (string.Equals(target.Trim(), compare.Trim()))
                {
                    node.currentColor = activeColor;
                    UpdateTile(node.currentTile, activeColor);

                    RevisedFloodFill(x + 1, y, targetColor);
                    RevisedFloodFill(x - 1, y, targetColor);
                    RevisedFloodFill(x, y + 1, targetColor);
                    RevisedFloodFill(x, y - 1, targetColor);
                }
            }

        }


    }
}

private bool isValid(int x, int y)
{
    if (x >= 0 && x < boardSize && y >= 0 && y < boardSize)
    {
        return true;
    }

    return false;
}

但是，尽管这种方法不会崩溃，但并不完美。在某些情况下，它倾向于忽略下一种颜色，并用错误的颜色填充整个电路板，因此我的比较仍然需要工作。

Answer 2

您遇到了递归问题。查看伪代码会有所帮助：

function ColorThisTile()

    if needed set tile color

    check tile on the left
    check tile on the right
    check tile on the top
    check tile on the bottom

在我要使用的示例中，使用棋盘作为参考：

假设我们从B4开始。这意味着该方法将对B4执行以下步骤：

    if needed set B4 color

    check A4
    check C4
    check B5
    check B3

那么check A4意味着什么？这是此方法的另一个实例，对于A4，它执行以下操作

    if needed set A4 color

    check ?4  // This does nothing since there's no tile to the left
    check B4  // The problem is here!
    check A5
    check A3

您最初的B4检查需要检查A4。随后的后续A4检查将导致再次检查B4。此新的B4检查将再次检查A4。该A4检查将再次检查B4。这无限地重复。

为了防止出现此问题，您必须编写逻辑，以避免重复。这可以通过多种方式完成，但是最简单的方法是跟踪您访问过的每个单元格，如果对已经访问过的单元格进行检查，请立即从函数返回。

类似的东西：

public void FloodFill(Cell cell, Color fillColor, List<Cell> visitedCells)
{
    if(visitedCells.Any(visitedCell => visitedCell.X = cell.X && visitedCell.Y = cell.Y) return;

    visitedCells.Add(cell);

    // the rest of the code

    FloodFill(cell.GetLeft(),  fillColor, visitedCells);
    FloodFill(cell.GetRight(), fillColor, visitedCells);
    FloodFill(cell.GetUp(),    fillColor, visitedCells);
    FloodFill(cell.GetDown(),  fillColor, visitedCells);
}

public class Cell
{
    public int X { get; set; }
    public int Y { get; set; }

    public Cell GetLeft()
    {
        return new Cell() { X = this.X-1, Y = this.Y };
    }

    public Cell GetRight()
    {
        return new Cell() { X = this.X+1, Y = this.Y };
    }

    public Cell GetUp()
    {
        return new Cell() { X = this.X, Y = this.Y-1 };
    }

    public Cell GetDown()
    {
        return new Cell() { X = this.X, Y = this.Y+1 };
    }
}

这可确保您不会遇到两个邻居不断检查彼此的问题。

[我添加了Cell类，以避免在每个转弯处都弄乱坐标变量-请确保检查您的环境是否尚不存在表示2D点的现有类/结构。