0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ i think recursion is only when a functions calls its own. you are using iteration. your code shows no problem. can you tell which line throws that exception? \$\endgroup\$ – virtouso Nov 9 at 9:22
  • \$\begingroup\$ Hi @virtouso, this line throws the exception: List<Bubble> neighbors = FindAllRecursiveNeighbors(FindPositionOfBubble(bubble)); It is calling the method again, and I guess that's causing a stack overflow problem somehow . . . p.s. you can safely ignore FindPositionOfBubble call. . .it just uses positions to search instead of Bubbles. I might write an overload for more beautiful code :) \$\endgroup\$ – e-mag Nov 9 at 10:02
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think I understand. So the basic idea is that I send to the next generation the list of all the bubbles I searched in this generation? And each level check against this list (which is one and the same) whether to check for the bubble or not. \$\endgroup\$ – e-mag Nov 10 at 21:34
1
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Hi @iQeW, thank you for your answer. I do check if the list already contains the Bubble before adding it. And the bubbles are created dynamically for the gameplay. For example if you shoot it, it stays there and is added to the grid. . . \$\endgroup\$ – e-mag Nov 9 at 10:24
  • \$\begingroup\$ How do you make sure that your algorithm is not checking bubbles it has already checked for? If you call this method recursively on every bubble then you need to make sure that there's no double checking otherwise you run into a situation where you check bubble a then call to check bubble b which then calls to check bubble a which then calls to check bubble b and so on. \$\endgroup\$ – iQew Nov 9 at 10:33
  • \$\begingroup\$ You're right @iQew, that might be the cause. . .How can I send that information deeper into the recursion? \$\endgroup\$ – e-mag Nov 9 at 10:37
  • \$\begingroup\$ @e-mag I don't know the architecture of your full code and I'm definitely not an expert on recursion (it's always tricky). Maybe you can simply add a bool to a bubble and set it to true when it has been checked and then not check the bubble again, if it was already checked. Then when your whole recursion is done you set all the bools to false again to re-enable it for the next time. \$\endgroup\$ – iQew Nov 9 at 10:42
  • \$\begingroup\$ Thanks @iQew, that's a great idea, I'll try that and let you know ;) \$\endgroup\$ – e-mag Nov 9 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.