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:
We call FindAllRecursiveNeighbours
with bubble A's position.
We make a new result
list for A, and find all A's neighbours, including bubble B.
Bubble B is not in A's result
list (it's a new, empty list), so we add it.
We walk through A's result
list and recurse on its contents.
In this walk, we call FindAllRecursiveNeighbours
with bubble B's position.
We make a new result
list for B, and find all B's neighbours, including bubble A.
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.
We walk through B's result
list and recurse on its contents.
In this walk, we call FindAllRecursiveNeighbours
with bubble A's position.
...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.
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 '19 at 10:02