时间戳

首页 > 解决方案 > 为什么在减去坐标时这种洪水填充方法会导致堆栈溢出？

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

问题描述

我正在尝试为瓷砖系统创建一个油漆桶风格的洪水填充，以创建一个编辑器。

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

遵循此处的示例算法，这段代码感觉它 - 应该 - 工作：

洪水填充算法示例

但是，如上所述，我自己在 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];
}

标签： c#unity3d

解决方案

经过几个小时的尝试，我终于找到了为什么事情不能正常工作的答案。在进入洪水填充步骤之前，还有一些步骤需要确认。

（注：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;
}

然而，虽然这不会崩溃，但它并不完美。在某些情况下，它往往会忽略下一种颜色并用错误的颜色填充整个电路板，所以我的比较仍然需要工作。

推荐阅读