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

Question

I'm making a game where the player has to rotate pipes to connect them to a source of water, but i'm getting stack overflow at certain point and i don't know where and why. Is there a pathfinding algorithm suitet for this situation?

The first level so far looks like this:

The "grid" is 9x9. The blue cross is the source of water and the other pipes have to check if they have a valid path to the source.

Each pipe object looks like this:

It consists is a parent game object to hold everything, the watered pipe object, a collider to detect the mouse clicks and 3 circle colliders to detect collision with the other pipes. This setup with all of those colliders is what i managed to make work. The empty pipe and the filled pipe both have a polygon collider to prevent colliding with the circe colliders in weird angles. The 3 circle collider objects are needed because of the different entrances of the pipe.

Now about the code:

I tried to create a pathfinding algorithm by myself to check if each tile have a valid path to the water source. I have no idea why it`s causing stack overflow.

Here is the pathfinding method:

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

What the code does:

• Every currently collided item is added to a list. The foreach run through that list.
• If the target object isn`t in the list of already checked objects, proceed.
• Get the same script in the target object and add that object to the already checked objects list.
• If the tag from the target object math, clear the checked objects list and return true. This means that the object that called the method is connected to the water source.
• If the tag don't match, add this object to the target's list of already checked objects (to prevent infinite looping).
• Now it calls the targets FindSourceOfWater method.
• If the method called returns true, then this instance also returns true.
• If not, then proceed to the next collided object.

The methods is called during update:

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

The StackOverflow error links to this line:

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

Its intended to return true if it has a valid connection to the water source tile. But i guess its calling the method too many times. Maybe because it`s been called in the update? So everyone is checking for a source of water at the same time.

Answer 1

For context, this problem space is know as 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> performs Contains() in O(1) time (as opposed to List<T> doing in in O(n) time) in addition to ensuring its contents are unique; it's better suited for your problem.

To fix your issue, you can just use a HashSet<T> along with a Stack<T>; one of items you've already checked, and one of items remaining to be checked. While there are still items remaining to be checked, pop one off and evaluate it. If it's connected to anything that hasn't already been checked, add it to the checked set and push it onto the stack.

Here's your algorithm, slightly modified:

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

---

Note: You could also use a Queue<T> for a breadth-first search instead of a Stack<T> (which makes this a depth-first traversal).