c# - 寻路算法来查找每个部分是否连接到特定对象

Question

我正在制作一款游戏，玩家必须旋转管道才能将它们连接到水源，但我在某个时刻遇到堆栈溢出，而且我不知道在哪里和为什么。有适合这种情况的寻路算法吗？

到目前为止的第一个级别如下所示:

“网格”是 9x9。蓝色十字是水源，其他管道必须检查是否有通往水源的有效路径。

每个管道对象如下所示:

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

现在关于代码:

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

寻路方法如下:

    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 遍历该列表。
• 如果目标对象不在已检查对象的列表中，则继续。
• 在目标对象中获取相同的脚本，并将该对象添加到已检查的对象列表中。
• 如果标签与目标对象数学运算，则清除已检查的对象列表并返回 true。这意味着调用该方法的对象已连接到水源。
• 如果标记不匹配，请将此对象添加到目标已检查对象的列表中(以防止无限循环)。
• 现在它调用目标的 FindSourceOfWater 方法。
• 如果调用的方法返回 true，则此实例也返回 true。
• 如果没有，则继续处理下一个碰撞对象。

更新期间调用这些方法:

    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);
        }
    }

StackOverflow 错误链接到此行:

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

就上下文而言，这个问题空间被称为 Graph Traversal (如果您想进一步研究这类事情)并且这里似乎不需要递归。此外，您的变量名称中包含“list”意味着您正在使用 List<T>但是 HashSet<T> 执行Contains()除了确保其内容是唯一的之外，还需要 O(1) 时间(而不是 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> (这使得这是一个深度优先遍历)。