How to find groups/islands in a 2d array (of gameobjects)

[zzeettoo]

Hi there.
As the title says, i have a 2d array containing gameobjects.
All gameobjects (which are some sort of cubes) have a type(a number/color) and they are generated randomly and added to the 2d array.

Every gameobject knows its 4 neighbours(if there are some, otherwise the entry is null) and they know their own type.

I now want to find the groups/islands within the 2d array and want every gameobject to have some kind of collection, lets say a list which has all gameobjects in it which belong to this group.

So if this is my table/2d-array, the orange 1’s in the top-left corner would be one island/group.
Each of them shall have a list with all 7 gameobjects in it.

I tried many things up to now but could not find a solution or a proper algorithm to do this.
I’ve read something about flood fill algorithms but trying to implement this led to a crash so i had some infinite loops.

My last approach was to ‘exchange’ both gameobjects when they meet. so i iterate through all gameobjects and when a go has a neighbour with the same color, the go gets written into this neighbours list and vice versa.
After that, the go writes itself into all gameobjects that are already in the neighbours list and it writes the neighbour is written into all gameobjects which already are in the current gameobjects list.

This works quite okay but will give me wrong results for the last gameobjects in long lines(longer than 3). In the lists of these objects, entries are missing.

[nicolasjr]

Hi, Zzeettoo.

So, what I’d do is to create a list in the class that you’re using, and a method to Set it.
After that, you’d start from the first entry, in that case, the array[0][0]. First, you’d add the first entry to the list. Now, you’d get it’s type and search on it’s neighbors for another one with same type. Once you found it, you add that neighbor to the list and set the neighbor list to the one you already have. Now, do the same with the neighbor you just added. In the method you do this verification, you must have a condition, that says that it’ll only add the object to list as long as it’s not already there.

After that, you go to next position, array[0][1], and run the same algorithm.

Before running the algorithm, you need to verify if the list is null, or size zero. If it’s not, just go to the next array position.

Does any of that makes sense?