Recursively find neighbors

Question

I'm making a Bubble Shooter game in Unity. I came to the point where I can hit another bubble and it destroys all of its neighbors.

Now I'm trying to use recursion to destroy all of its neighbors neighbors and it causes a stack overflow.

private List<Bubble> FindAllRecursiveNeighbors(Vector2Int originPosition)
{
    List<Bubble> allNeighbors = FindNeighbors(originPosition);
    List<Bubble> result = new List<Bubble>();

    foreach (Bubble bubble in allNeighbors)
    {
        if (result.Contains(bubble)) { continue; }
        result.Add(bubble);
    }

    // Recursion starts here.
    foreach (Bubble bubble in result)
    {
        List<Bubble> neighbors = FindAllRecursiveNeighbors(FindPositionOfBubble(bubble));
        foreach (Bubble neighbor in neighbors)
        {
            if (result.Contains(neighbor)) { continue; }
            result.Add(neighbor);
        }
    }
    return result;
}

Answer 1

You're trying to limit double-counting using your results list:

if (result.Contains(neighbor)) { continue; }
    result.Add(neighbor);

The trouble is, you're using a different result list in each iteration:

1. We call FindAllRecursiveNeighbours with bubble A's position.

2. We make a new result list for A, and find all A's neighbours, including bubble B.

3. Bubble B is not in A's result list (it's a new, empty list), so we add it.

4. We walk through A's result list and recurse on its contents.

5. In this walk, we call FindAllRecursiveNeighbours with bubble B's position.

6. We make a new result list for B, and find all B's neighbours, including bubble A.

7. Bubble A is not in B's result list (it's a new, empty list - we didn't pass our results so far from the A steps above), so we add it.

8. We walk through B's result list and recurse on its contents.

9. In this walk, we call FindAllRecursiveNeighbours with bubble A's position.

10. ...uh-oh, we're back at a situation identical to the beginning of this process. So we repeat the steps above infinitely, ping-ponging back and forth between bubble A and bubble B, because each generation of the search doesn't know they've already been checked in past generations.

To fix this, we need to make the later generations aware of what we've searched so far. That can look like this:

public static void FindNeighboursRecursively(Bubble start, List<Bubble> foundSoFar) {

    foundSoFar.Add(start);

    foreach(var bubble in FindNeighbors(FindPositionOfBubble(start))) {
        if(foundSoFar.Contains(bubble))
            continue;

        FindNeighboursRecursively(GetPositionOf(bubble), foundSoFar);
    }
}

Now all the recursive calls share one result list, foundSoFar, so we can skip bubbles found later that were already visited in earlier generations.

Also, passing this in as an argument means the calling code can choose to keep one persistent list as a member variable, and recycle it between uses, saving some unnecessary re-allocations. That's how Unity's NonAlloc physics queries do their work too.

Just remember to clear the list before starting a new search:

private List<Bubble> connectedBubbles = new List<Bubble>();

void UpdateConnections(Bubble start) {
    connectedBubbles.Clear();
    FindNeighboursRecursively(start, connectedBubbles);
}

One note on List.Contains(): this searches the whole list, checking if the argument matches each entry along the way. So as your list grows, this search takes longer (\$O(n)\$). If you're gathering collections of dozens of bubbles, it's likely not an issue. If you're working with hundreds or more though, you'll likely want to use a different method to mark & check whether an item has been visited already - like a boolean flag on each item as iQew suggested, or a Hashset, both of which will give you \$O(1)\$ lookups.

Answer 2

The thing is that you look for neighbours and then you call the same method again on the neighbours, which means that you can find the origin again, as well. This causes an infinite loop meaning StackOverFlow in this case. It might make more sense to find a clever way to give each Bubble an Array or List of Bubbles (Neighbours) and set them during the level creation. So when you shoot a bubble and want to destroy all neighbours, you have more control since some bubbles might have neighbours set and some don't (exit condition).