C# - 停止内部递归（嵌套？）Foreach

Question

我正在尝试使用递归方法搜索特定类型的图块。问题是它变得无限。我认为这是因为它仍然在 foreach 的其余部分调用该方法，所以我想知道你们中是否有人有 improvement/correction。这是我正在使用的代码：

private Tiles LookForCheckedWlakable(Tiles t)
{
    if (t.IsChecked())
        return t;
    else
    {
        foreach (Tiles n in t.neighbours)
        {
            if (!n.visited)
            {
                n.visited = true;
                Tiles result = LookForCheckedWlakable(n);
                if (result != null)
                    return result;
            }
        }
    }
    return null;
}

感谢您的宝贵时间。

编辑：

正如人们所问，这是我的 Tiles class（忽略 Monobehaviour，它是 Unity 的大师 class。另外，一些属性是 public 所以我可以窥探它们在 Unity 编辑器上。我会尽快将其改回私有）：

public class Tiles : MonoBehaviour {

public List<Tiles> neighbours = new List<Tiles>();
public int x, y;
public Boolean isWalkable = false;
public Boolean check = false;
public Boolean visited = false;

/// <summary>
/// Allow other tiles to add themselves as a neighbour of their neighbours and vice versa. Fail if they already know each other.
/// </summary>
/// <param name="t">The tiles you want to add as a neighbour.</param>
public void addNeighbour(Tiles t)
{
    if (!t.getNeighbour().Contains(this))
    {
        this.neighbours.Add(t);
        t.getNeighbour().Add(this);
    }
}

/// <summary>
/// Get the neighbours of this tiles
/// </summary>
/// <returns>A list with all of this tiles' neighbours</returns>
public List<Tiles> getNeighbour()
{
    return this.neighbours;
}
}

感谢您指出由于访问未被重置，此代码只能使用一次，我将对此进行更改。我不知道如何检查这是否是 "just being slow"。我已经有其他算法可以遍历我的地图，并且不会花费无限时间。

编辑 2：

我正在尝试用瓷砖制作 "game board"。它们可以是可步行的、障碍物或洞。我想随机生成它，但需要检查整个图是否仍然是连接的。我使用这种递归方法从一个孤立的瓦片中找到最近的可步行瓦片（我知道它是孤立的，因为我从一个起点开始填充我的图表，即时检查它们。当它们没有被检查时，它们是孤立的。）

大型编辑来解释我能想到的一切：

在这里，你可以看到我生成的图表。左边是我有的，右边是我想要的

（我想post直接图片，但显然我需要声望...）

https://imgur.com/a/LKW5e

可以看到"isolated one"。我想从孤立到 grpah 的其余部分。我知道图表的其余部分已被检查，多亏了这种方法（我从我手动检查的起始图块开始）：

/// <summary>
/// Flood fill, aka check every walkable tiles from the starting tiles
/// </summary>
/// <param name="tiles">The starting tiles</param>
private void Floodfill(Tiles tiles)
{
    //Create queue to flood fill
    Queue<Tiles> queue = new Queue<Tiles>();
    queue.Enqueue(tiles);
    //We flood fill, aka we look for every components in the neighbours and check them.
    //Any non checkes tiles is isolated.
    while (queue.Count != 0)
    {
        Tiles t = queue.Dequeue();
        t.CheckIt();
        foreach (Tiles neighbour in t.neighbours)
        {
            if (neighbour.isWalkable && !neighbour.IsChecked())
                queue.Enqueue(neighbour);
        }
    }
}

之后，我寻找隔离并执行此操作:

void TryConnexe()
{
    //We found the spawn of the player on the left, which is a guaranteed walakable.
    Tiles start = allTiles.Find(t => t.x == 1 && t.y == 9);
    Floodfill(start);

    //Now, we look in every of our tiles.
    foreach (Tiles tiles in allTiles)
    {
        //As soon as it isn't checked, it's an isolated one.
        if (tiles.isWalkable && !tiles.IsChecked())
        {
            //this is the line that makes everything goes infinite.
            Tiles goal = LookForCheckedWlakable(tiles);
            Debug.Log("recursivity ended with : ");
            //we floodfill the remaining one, because we need to check them. Otherwise, the code will restart on a possible next tile.
            Floodfill(tiles);
            Dictionary<Tiles, Tiles> path = Pathfind(tiles, goal);
            Tiles current = path[goal];
            while (current != tiles)
            {
                current.isWalkable = true;
                current.CheckIt();
                current.GetComponentInChildren<SpriteRenderer>().color = Color.green;//walkable
                goal = current;
            }

        }
    }
}

我能想到的就这些了。如果您需要更多解释，请随时询问。

Answer 1

第 99 次看，在我看来，您只是误诊了故障点。我怀疑您的代码在 Tiles goal = LookForCheckedWlakable(tiles); 处并没有真正无限大，相反，它会在接下来的 while-loop

中无限大

while (current != tiles)
{
    current.isWalkable = true;
    current.CheckIt();
    current.GetComponentInChildren<SpriteRenderer>().color = Color.green;//walkable
    goal = current; // bad
}

我的 crystal 球告诉我，你可以通过更正你的循环来解决它 "increment":

while (current != tiles)
{
    current.isWalkable = true;
    current.CheckIt();
    current.GetComponentInChildren<SpriteRenderer>().color = Color.green;//walkable
    current = path[current]; // better, depending on the actual result of Pathfind
}

如果我的 crystal 球错了，请继续我原来的答案并开始寻找你的不同之处。

请参阅下面我的长答案，我在其中深入测试了您的 LookForCheckedWlakable 只是为了发现：它可能没有错。

好的，我尽我所知重现了您的磁贴配置并尝试重现您的问题（variable/function 名称只有一些细微差别）。

结果：代码为运行，没有出现死循环。请随意测试我的代码并将其用作参考，以了解您在实际代码中做错了什么。

据我所知，您遗漏了问题的一些关键细节，因为您不知道自己遗漏了什么，所以我写下这个答案是为了让您有一个起点。

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

    public bool IsChecked { get; set; }

    public bool IsWalkable { get; set; }

    public bool Visited { get; set; }

    private List<Tiles> _neighbours = new List<Tiles>();

    public IEnumerable<Tiles> GetNeighbours()
    {
        return _neighbours;
    }

    public void AddNeighbour(Tiles neighbour)
    {
        if (!_neighbours.Contains(neighbour))
        {
            _neighbours.Add(neighbour);
            neighbour._neighbours.Add(this);
        }
    }
}

public static class TileSolver
{
    // just run this to emulate your example
    public static void RunExample()
    {
        var t1 = GenerateTilePositions();
        var t2 = GenerateTiles(t1);

        var start = t2.First(x => x.X == 0 && x.Y == 8);

        Floodfill(start);

        //Now, we look in every of our tiles.
        foreach (Tiles tile in t2)
        {
            //As soon as it isn't checked, it's an isolated one.
            if (tile.IsWalkable && !tile.IsChecked)
            {
                //this is the line that makes everything goes infinite.
                Tiles goal = LookForCheckedWlakable(tile);

                //we floodfill the remaining one, because we need to check them. Otherwise, the code will restart on a possible next tile.
                Floodfill(tile);

                // no need to for the rest, since you claim LookForCheckedWlakable is at fault
                // and you don't provide code for Pathfind and GetComponentInChildren 
            }
        }
    }

    private static Tiles LookForCheckedWlakable(Tiles t)
    {
        if (t.IsChecked)
            return t;
        else
        {
            foreach (Tiles n in t.GetNeighbours())
            {
                if (!n.Visited)
                {
                    n.Visited = true;
                    Tiles result = LookForCheckedWlakable(n);
                    if (result != null)
                        return result;
                }
            }
        }
        return null;
    }

    private static void Floodfill(Tiles tiles)
    {
        //Create queue to flood fill
        Queue<Tiles> queue = new Queue<Tiles>();
        queue.Enqueue(tiles);
        //We flood fill, aka we look for every components in the neighbours and check them.
        //Any non checkes tiles is isolated.
        while (queue.Count != 0)
        {
            Tiles t = queue.Dequeue();
            t.IsChecked = true;
            foreach (Tiles neighbour in t.GetNeighbours())
            {
                if (neighbour.IsWalkable && !neighbour.IsChecked)
                    queue.Enqueue(neighbour);
            }
        }
    }

    /// <summary>
    /// generate a hexagon of tile positions for the following indexing pattern:
    /// Suppose a triangle with the points: upper left, upper right, bottom center
    /// The parameter N describes the count of Tiles on the edges of the generated hexagon.
    /// The relation of triangle and hexagon is as follows:
    /// 
    ///      (N - 1, 0) (2N - 2, 0)
    ///   (0, 0) . . x x x . . (3N - 3, 0)
    ///           . x x x x .
    /// (0, N - 1) x x x x x (2N - 2, N - 1)
    ///             x x x x
    ///  (0, 2N - 2) x x x (N - 1, 2N - 2)
    ///               . .
    ///                .
    ///           (0, 3N - 3)
    /// 
    /// The indices start at (x=0, y=0) upper left of the triangle, increasing x while going to the right
    /// and increasing y while going down and half-right.
    /// </summary>
    /// <param name="N"></param>
    /// <returns></returns>
    private static List<Tuple<int, int>> GenerateTilePositions()
    {
        int N = 9;
        var result = new List<Tuple<int, int>>();
        for (int x = 0; x < 3 * N - 2; x++)
        {
            for (int y = 0; y < 3 * N - 2; y++)
            {
                if (N - 2 < x + y &&
                    x + y < 3 * N - 2 &&
                    x < 2 * N - 1 &&
                    y < 2 * N - 1)
                {
                    result.Add(new Tuple<int, int>(x, y));
                }
            }
        }

        return result;
    }


    private static void SetNotWalkable(Dictionary<Tuple<int, int>, Tiles> tilesDict, int x, int y)
    {
        tilesDict[Tuple.Create(x, y)].IsWalkable = false;
    }

    private static void TryAddNeighbour(Dictionary<Tuple<int, int>, Tiles> tilesDict, Tiles item, int offsetX, int offsetY)
    {
        Tiles neighbour;
        if (tilesDict.TryGetValue(Tuple.Create(item.X + offsetX, item.Y + offsetY), out neighbour))
        {
            item.AddNeighbour(neighbour);
        }
    }

    private static List<Tiles> GenerateTiles(List<Tuple<int, int>> t2)
    {
        var tilesDict = t2.ToDictionary(
            pos => pos,
            pos => new Tiles
            {
                X = pos.Item1,
                Y = pos.Item2,
                IsChecked = false,
                Visited = false,
                IsWalkable = true, // some will be changed manually
            });

        // connect neighbours
        foreach (var item in tilesDict.Values)
        {
            TryAddNeighbour(tilesDict, item, -1, 0);
            TryAddNeighbour(tilesDict, item, 1, 0);
            TryAddNeighbour(tilesDict, item, 0, -1);
            TryAddNeighbour(tilesDict, item, 0, 1);
            TryAddNeighbour(tilesDict, item, -1, 1);
            TryAddNeighbour(tilesDict, item, 1, -1);
        }

        // Unchecked Green positions after FloodFill:
        //Tuple.Create(8, 0);
        //Tuple.Create(7, 1);
        //Tuple.Create(7, 2);

        // Special positions (red, black)
        SetNotWalkable(tilesDict, 9, 0);
        SetNotWalkable(tilesDict, 14, 0);
        SetNotWalkable(tilesDict, 15, 0);
        SetNotWalkable(tilesDict, 16, 0);

        SetNotWalkable(tilesDict, 8, 1);
        SetNotWalkable(tilesDict, 11, 1);
        SetNotWalkable(tilesDict, 12, 1);

        SetNotWalkable(tilesDict, 6, 2);
        SetNotWalkable(tilesDict, 8, 2);
        SetNotWalkable(tilesDict, 12, 2);
        SetNotWalkable(tilesDict, 14, 2);

        SetNotWalkable(tilesDict, 6, 3);
        SetNotWalkable(tilesDict, 7, 3);
        SetNotWalkable(tilesDict, 10, 3);
        SetNotWalkable(tilesDict, 13, 3);

        SetNotWalkable(tilesDict, 10, 4);
        SetNotWalkable(tilesDict, 12, 4);
        SetNotWalkable(tilesDict, 13, 4);
        SetNotWalkable(tilesDict, 14, 4);

        SetNotWalkable(tilesDict, 3, 5);
        SetNotWalkable(tilesDict, 6, 5);
        SetNotWalkable(tilesDict, 8, 5);
        SetNotWalkable(tilesDict, 9, 5);
        SetNotWalkable(tilesDict, 12, 5);
        SetNotWalkable(tilesDict, 15, 5);

        SetNotWalkable(tilesDict, 2, 6);
        SetNotWalkable(tilesDict, 3, 6);
        SetNotWalkable(tilesDict, 7, 6);
        SetNotWalkable(tilesDict, 9, 6);
        SetNotWalkable(tilesDict, 16, 6);

        SetNotWalkable(tilesDict, 1, 7);
        SetNotWalkable(tilesDict, 3, 7);
        SetNotWalkable(tilesDict, 7, 7);
        SetNotWalkable(tilesDict, 9, 7);
        SetNotWalkable(tilesDict, 12, 7);
        SetNotWalkable(tilesDict, 16, 7);

        SetNotWalkable(tilesDict, 9, 8);
        SetNotWalkable(tilesDict, 12, 8);
        SetNotWalkable(tilesDict, 13, 8);

        SetNotWalkable(tilesDict, 0, 9);
        SetNotWalkable(tilesDict, 1, 9);
        SetNotWalkable(tilesDict, 6, 9);
        SetNotWalkable(tilesDict, 7, 9);
        SetNotWalkable(tilesDict, 8, 9);
        SetNotWalkable(tilesDict, 10, 9);
        SetNotWalkable(tilesDict, 12, 9);
        SetNotWalkable(tilesDict, 13, 9);

        SetNotWalkable(tilesDict, 3, 10);
        SetNotWalkable(tilesDict, 4, 10);
        SetNotWalkable(tilesDict, 8, 10);
        SetNotWalkable(tilesDict, 10, 10);

        SetNotWalkable(tilesDict, 5, 11);
        SetNotWalkable(tilesDict, 6, 11);
        SetNotWalkable(tilesDict, 9, 11);
        SetNotWalkable(tilesDict, 10, 11);

        SetNotWalkable(tilesDict, 4, 12);
        SetNotWalkable(tilesDict, 6, 12);
        SetNotWalkable(tilesDict, 9, 12);
        SetNotWalkable(tilesDict, 11, 12);

        SetNotWalkable(tilesDict, 6, 13);
        SetNotWalkable(tilesDict, 7, 13);
        SetNotWalkable(tilesDict, 9, 13);
        SetNotWalkable(tilesDict, 11, 13);

        SetNotWalkable(tilesDict, 0, 14);
        SetNotWalkable(tilesDict, 2, 14);
        SetNotWalkable(tilesDict, 3, 14);
        SetNotWalkable(tilesDict, 8, 14);
        SetNotWalkable(tilesDict, 9, 14);

        SetNotWalkable(tilesDict, 0, 15);
        SetNotWalkable(tilesDict, 7, 15);

        SetNotWalkable(tilesDict, 0, 16);
        SetNotWalkable(tilesDict, 2, 16);
        SetNotWalkable(tilesDict, 3, 16);
        SetNotWalkable(tilesDict, 4, 16);
        SetNotWalkable(tilesDict, 5, 16);
        SetNotWalkable(tilesDict, 7, 16);

        return tilesDict.Values.ToList();
    }
}

C# - 停止内部递归（嵌套？）Foreach

C# - Stop recursion inside (nested?) Foreach

c#

recursion

unity5