寻路算法，以查找每个部分是否连接到特定对象

Question

我正在制作一款游戏，玩家必须旋转管道才能将它们连接到水源，但我在某个时候 stack overflow 而我不知道不知道在哪里以及为什么。有针对这种情况的寻路算法套件吗？

目前第一关是这样的：

"grid" 是 9x9。蓝色十字是水源，其他管道必须检查它们是否有通往水源的有效路径。

每个管道对象如下所示：

它包含一个父级 game object 来保存所有东西，浇水的管道对象，一个 collider 来检测鼠标点击和 3 个 circle colliders 来检测与其他管道的碰撞。我设法完成了所有这些对撞机的设置。空管和填充管都有一个 polygon collider 以防止与 circe colliders 以奇怪的角度碰撞。由于管道的入口不同，因此需要 3 个 circle collider 个对象。

现在关于代码：

我尝试自己创建一个寻路算法来检查每个瓦片是否都有通往水源的有效路径。我不知道为什么会导致堆栈溢出。

这里是寻路方法：

    public bool FindSourceOfWater() {
        foreach (var item in collidedList) {
            if (!checkedObjectsList.Contains(item)) {
                Pipe targetObjectScript = item.GetComponent<Pipe>();
                checkedObjectsList.Add(item);
                if (item.CompareTag("Pipes_WaterSource")) {
                    checkedObjectsList.Clear();
                    return true;
                } else {
                    targetObjectScript.checkedObjectsList.Add(gameObject);
                    if (targetObjectScript.FindSourceOfWater()) {
                        checkedObjectsList.Clear();
                        return true;
                    }
                }
            }
        }
        checkedObjectsList.Clear();
        return false;
    }

代码的作用：

每个当前碰撞的项目都添加到列表中。 foreach 运行通过该列表。
如果目标对象不在已检查对象列表中，请继续。
在目标对象中获取相同的脚本并将该对象添加到已检查的对象列表中。
如果标签来自目标对象数学，则清除选中的对象列表并且return 为真。这意味着调用该方法的对象已连接到水源。
如果标签不匹配，将此对象添加到目标的已检查对象列表中（以防止无限循环）。
现在它调用目标的 FindSourceOfWater 方法。
如果调用的方法 return 为真，则此实例也 return 为真。
如果不是，则继续处理下一个碰撞对象。

更新期间调用的方法：

    private void Update() {
        if (collidedList.Count != 0) {
            isConnectedToWaterSource = FindSourceOfWater();
        } else {
            isConnectedToWaterSource = false;
        }
        if (isConnectedToWaterSource && !filledPipe.activeSelf) {
            filledPipe.SetActive(true);
        } else if (!isConnectedToWaterSource && filledPipe.activeSelf) {
            filledPipe.SetActive(false);
        }
    }

Whosebug 错误链接到此行：

if (item.CompareTag("Pipes_WaterSource")) {

它s intended to return true if it has a valid connection to the water source tile. But i guess it调用该方法的次数太多了。也许是因为它在更新中被调用了？所以大家同时在找水源

Answer 1

对于上下文，此问题 space 被称为 Graph Traversal (in case you'd like to further study these sorts of things) and there doesn't seem to be a need here for recursion. Also, your variable names with "list" in them imply you're using List<T> but HashSet<T> 在 O(1) 时间内执行 Contains()（与 List<T> 在 O(n ) 时间) 除了 确保其内容是唯一的 ;它更适合您的问题。

要解决您的问题，您只需使用 HashSet<T> 和 Stack<T>；您已经检查过的项目之一，以及尚待检查的项目之一。虽然仍有待检查的项目，但弹出一个项目并对其进行评估。如果它连接到任何尚未检查的内容，请将其添加到检查集中并将其推入堆栈。

这是您的算法，稍作修改：

public bool FindSourceOfWater() {
    //Prep collections with this object's connections
    var checkedSet = new HashSet<ItemType>(collidedList);
    var remainingStack = new Stack<ItemType>(collidedList);

    //Are there items left to check?
    while (remainingStack.Count > 0) {
        //Reference the next item and remove it from remaining
        var item = remainingStack.Pop();
        Pipe targetObjectScript = item.GetComponent<Pipe>();

        //If it's the source, we're done
        if (item.CompareTag("Pipes_WaterSource")) {
            return true;
        } else {
            //Otherwise, check for new items to evaluate
            //(You'll have to publicly expose collidedList for this)
            foreach (var newItem in targetObjectScript.collidedList) {
                //HashSet.Add returns true if it's added and false if it's already in there
                if (checkedSet.Add(newItem)) {
                    //If it's new, make sure it's going to be evaluated
                    remainingStack.Push(newItem);
                }
            }
        }
    }

    return false;
}

注意：您也可以使用 Queue<T> 代替 Stack<T> 进行广度优先搜索（这使它成为深度优先遍历）。

Answer 2

我会创建一个管理器对象来为您处理这个问题，而不是运行在您拥有的每个管道对象的更新中使用它，您只会在管理器中运行它一次对象并让管理器更新所有管道，或者从管道的更新方法中轮询管理器class。

免责声明：这只是一个示例算法，当然可以对代码进行改进。

public class WaterConnectionManager
{
    static IList<Pipe> WaterConnectedPipes = new List<Pipe>();
    static IList<Pipe> AllPipes = new List<Pipe>();

    static void UpdatePipes()
    {
        //get the starting point for this algorithm
        Pipe waterSource = GetWaterSource();

        //recurse for all connected pipes
        UpdateWaterConnectedPipesList(waterSource);

        //Update each pipe with its current status
        foreach(Pipe pipe in AllPipes)
        {
            pipe.IsWaterConnected = WaterConnectedPipes.Contains(pipe);
        }
    }

    static void UpdateWaterConnectedPipesList(Pipe sourcePipe)
    {
        //create a method that returns connected pipes on your Pipe script.
        IEnumerable<Pipe> connectedPipes = sourcePipe.GetConnectedPipes();

        foreach(Pipe connectedPipe in connectedPipes)
        {
            //prevent infinite recursion
            if (WaterConnectedPipes.Contains(connectedPipe))
            {
                continue;
            }

            //store these connected pipes for later recursions/iterations
            WaterConnectedPipes.Add(connectedPipe);

            //recurse into the connected pipe, to find its connected pipes.
            UpdateWaterConnectedPipesList(connectedPipe);
        }
    }

    static Pipe GetWaterSource()
    {
        return AllPipes.First(p => p.IsWaterSource);
    }

}

寻路算法，以查找每个部分是否连接到特定对象

Pathfinding algorithm to find if each piece is connected to a specific object

c#

unity3d

path-finding