# How can I avoid a stack overflow when recursively checking adjacent game objects?

I am building a simple game on Unity to learn the system. I am using C#.

The game is a basic "blocks" game, whereby when the player clicks on a block, the block and its neighbours of the same colour all disappear (get destroyed).

My process is this:

• To keep a track of which blocks are neighbours of the same colour, on each refresh each block checks their details on the event OnCollisionEnter and adds these collision neighbours to a List of valid neighbouring gameobjects.

• When a block is clicked, this list is checked and each neighbour has its own neighbours list checked, after list checking each block is distroyed.

Somehow, this process is causing a StackOverflowException

StackOverflowException
UnityEngine.GameObject.GetComponent[setupscript] () (at C:/buildslave/unity/build/artifacts/generated/common/runtime/GameObjectBindings.gen.cs:35)
setupscript.checkNeighbours () (at Assets/scripts/setupscript.cs:86)
setupscript.checkNeighbours () (at Assets/scripts/setupscript.cs:87)
setupscript.checkNeighbours () (at Assets/scripts/setupscript.cs:87)
setupscript.checkNeighbours () (at Assets/scripts/setupscript.cs:87)
....

Here is my script, first my List establishment:

 private List<GameObject> neighbours = new List<GameObject>();


Next, here is how the neighbours list is populated:

void OnCollisionEnter (Collision other)
{
Rigidbody other_rb = other.rigidbody;
if(rb.velocity.magnitude < 1f && other_rb.velocity.magnitude < 1f
&& other.gameObject.tag == tagName && !neighbours.Contains(other.gameObject)) {
/***
* Same tag so add to list of valid neighbours
***/
}
}


Now, there are four conditions [above] to check when adding to the list:

• Is the current block stationary.
• Is the "other" colliding block stationary (so they're at rest next to each other).
• do these blocks have the same tag (so they're the same type/colour)
• does this block not already exist in this list.

So once all four conditions are met, the block GameObject is added to the List.

( On conditions of OnCollisionExit blocks are removed from the List in a similar fashion. )

Now, my CheckNeighbours() script:

public void checkNeighbours(){
if (neighbours.Count > 0) {
foreach (GameObject othercube in neighbours) {
setupscript otherCubeScript = othercube.GetComponent<setupscript>();
otherCubeScript.checkNeighbours();
}
}

Destroy (gameObject);
}


This should, as far as I understand it, run once through each List element and check that element for any neighbours who match.

As I write this question out I think I'm realising that the issue is that we're in a loop as block 1 references neighbour block 2, which references neighbour block 3, which references neighbour block 1, etc. etc.

But my StackOverflow exception occurs when there are only two blocks, so one refers to the other, refers to the first, etc. But as they should destroy after running the reference, this shouldn't (ideally) be an issue? Do I need to make the checkNeighbour() a Corountine to allow it to not hold up destroying the GameObject?

If this [repetition cycling] is indeed what's going on, what would be the best way of getting each neighbour to be checked only once? Or checking that the GameObject referenced in the List still exists in the game itself?

I have a quick edit here:

foreach (GameObject othercube in neighbours) {
if (othercube != null){
setupscript otherCubeScript = othercube.GetComponent<setupscript>();
otherCubeScript.checkNeighbours();
}
}


But I'm not sure this will work as I feel this List will purely be a reference rather than the actual GameObject in the level?

• I am going to give you a suggestion which is to try and implement a "toggling" game via arrays and NOT linked grids of objects. An array can be of boolean type and you can just make the click event determine the index being clicked and then (without recursion) change the adjacent squares. There will be edge cases, but those are easy to deal with by using if statements. – The Great Duck May 20 '17 at 21:05

You are correct in that your problem is caused by two objects referencing each other. That causes each object to call "check neighbors" forever on its neighbor.

checkNeighbors calls checkNeighbors on adjacent objects before it even attempts to Destroy a game object, although fixing that ordering problem would likely lead you to a different issue: trying to call checkNeighbors on a destroyed object (Destroy will not, on its own, remove an object from a neighbor list).

A typical way to handle these kinds of "flooding" recursive algorithms is to mark objects you have visited already. You can do this with a flag on the object itself, although this is somewhat brittle. You can also do it by keeping a HashSet<T> or similar of all the objects you have visited.

checkNeighbors would then take an extra parameter, this set, and would do something like:

if (set.Contains(thisObject)) {