Logic of finding the count of elements of a platform?

Sorry for the vague title but I am not really sure how to ask the question. It is more of a logic problem than an actual programming problem.

Problem:
Imagine you made a platform that is made up off cubes, lets say 10 cubes wide, 3 cubes long. But you subtracted some cubes in the middle so now you have 2 platforms.

Now imagine this on a much larger scale with some randomly placed cubes all over the place.

What I am trying to find out is, How many platforms(groups of cubes) do I have and how many cubes does each platform have. (by groups I mean multiple cubes that are touching each other).

I can write the code if I can wrap my head around the logic, I was trying something like iterating through each cube and checking if there is a cube next to it, then adding the 2 to a group, checking if there is another cube next to them and adding that to the first group but that does not feel like a good way to approach the problem.

The Cubes are procedurally generated.

use voxel or linked list to link one cube to its neighbor.

otherwise your alogorithm has complexity > O(n*n).

If you use a ‘chain’ of Cubes this would be a solution:

private int cubeCount(Cube cube)
{
	int count = 0;
	Cube next = cube;
	while(next != null)
	{
		count ++;
		next = cube.next;
	}

	Cube previous = cube.previous;
	while(previous != null)
	{
		count ++;
		previous = cube.previous;
	}
}

Here is what I ended up doing to be able to pull this off. It is really slow in when there are a lot of blocks. ( I have about 1000 per level.) But it does work pretty well. Not really sure what makes it slow. Do not mind the Debug.logs.

Here it is for anyone running into a similar issue.

Logic behind the code:

  1. Collect all cubes into a list (unsortedCubes)
  2. Take list item [0] and check remove it from the unsorted list. (heroCube)
  3. check which cubes are touching “herocube”
  4. remove them from the unsortedlist
  5. check which cubes are touching the neightbors. If they are in the unsortedlist, remove them from unsorted and ad them and hero and neighbors to group one.
  6. repeat till unsortedCubes is empty.

CODE:

//Identify indivisual groups of cubes
		IEnumerator IdentifyGroups ()
		{
				Debug.LogWarning ("Identifing Groups");
				List<GameObject> unsortedBlocks = GameObject.FindGameObjectsWithTag (assignedTag).ToList ();
				int totalUnsortedBlockCount = unsortedBlocks.Count;
				//Debug.LogError ("Total number of blocks = " + unsortedBlocks.Count.ToString ());
				List<List<GameObject>> groups = new List<List<GameObject>> ();
				int groupCount = 0;
				while (unsortedBlocks.Count > 0) {
						//Debug.LogError ("Creating a Group " + groupCount.ToString ());
						GameObject startBlock = unsortedBlocks [0];
						groups.Add (new List<GameObject> ());
						groups [groupCount].Add (startBlock);
						blacklist.Add (startBlock);
						List<GameObject> unfilteredNeighboringCubes = listOfTouchingCubes (new List<GameObject>{groups[groupCount][0]});
						List<GameObject> neighboringCubes = new List<GameObject> ();
						foreach (GameObject cube in unfilteredNeighboringCubes) {
							
								if (unsortedBlocks.Contains (cube)) {
										neighboringCubes.Add (cube);
										unsortedBlocks.Remove (cube);
								}
						}
						unsortedBlocks.Remove (startBlock);
						foreach (GameObject nCube in neighboringCubes) {
								unsortedBlocks.Remove (nCube);
								if (!groups [groupCount].Contains (nCube)) {
										groups [groupCount].Add (nCube);
										blacklist.Add (nCube);
								}
						}
						int neighboringCubeCount = neighboringCubes.Count;
						while (neighboringCubeCount > 0) {
								Debug.Log ("Neightboring Cubes count is " + neighboringCubeCount.ToString ());
								List<GameObject> repeateTouchingCubes = listOfTouchingCubes (neighboringCubes).Distinct ().ToList ();
								foreach (GameObject repeateCube in repeateTouchingCubes) {
										if (unsortedBlocks.Contains (repeateCube)) {
												Debug.Log ("unsortedBlocks contain Repeate Cube");
												if (!neighboringCubes.Contains (repeateCube)) {
														Debug.Log ("adding repeate block to unsorted blocks");
														neighboringCubes.Add (repeateCube);
														neighboringCubeCount = neighboringCubes.Count;
												}
										} else {
												Debug.Log (" unsortedBlocks did not contain repeate cube");
										}
								}

								unsortedBlocks.Remove (neighboringCubes [0]);
								if (progressBar != null) {
										progressBar.value = 1f - (unsortedBlocks.Count / totalUnsortedBlockCount);
								}
								if (!groups [groupCount].Contains (neighboringCubes [0])) {
										groups [groupCount].Add (neighboringCubes [0]);
										blacklist.Add (neighboringCubes [0]);
								}
								neighboringCubes.RemoveAt (0);
								neighboringCubeCount = neighboringCubes.Count;
								yield return new WaitForEndOfFrame ();
						}
						foreach (GameObject block in groups[groupCount])
								block.transform.position = block.transform.position + new Vector3 (0, levelYPositionOffset, 0);

				                                                                  
						groupCount++;
						yield return new WaitForEndOfFrame ();
				}
				yield return new WaitForEndOfFrame ();
				Debug.Log ("Number of Groups = " + groups.Count);
				for (int i = 0; i< groups.Count; i++) {
						Debug.Log ("Group " + i.ToString () + " Has " + groups *.Count + " Blocks");*

_ if (groups .Count < 5)_
_ foreach (GameObject go in groups*)
Destroy (go);
}
}*_

* // Return a List of Cubes that are touching the inc Cube*
* List listOfTouchingCubes (List originalCubes)*
* {*
* Debug.Log (“Getting list of touching cubes”);*
* List tempCheckCubes = new List ();*
* foreach (GameObject oCube in originalCubes) {*
* List nextPositions = GetNeighborPositions (oCube.transform.position);*
* foreach (Vector3 cubePos in nextPositions) {*
* GameObject blockAt = blockLocatedAt (cubePos);*
* if (!blacklist.Contains (blockAt))*
* tempCheckCubes.Add (blockAt);*
* }*
* }*
* Debug.Log (“Returning " + tempCheckCubes.Count.ToString () + " Cubes”);*
* return tempCheckCubes;*

* }*

* // Get a GameObject Block from a particular location*
* GameObject blockLocatedAt (Vector3 loc)*
* {*
* GameObject[] blockArray = GameObject.FindGameObjectsWithTag (assignedTag);*
* GameObject returnBlock = blockArray [0];*
* foreach (GameObject block in blockArray)*
* if (block.transform.position == loc)*
* returnBlock = block;*
* return returnBlock;*

* }*

* // Get platform memebers*
* List GetNeighborPositions (Vector3 blockPos)*
* {*
* List returnPos = new List ();*
* if (!avaiablePosition (blockPos + Vector3.forward, true))*
* returnPos.Add (blockPos + Vector3.forward);*
* if (!avaiablePosition (blockPos + Vector3.back, true))*
* returnPos.Add (blockPos + Vector3.back);*
* if (!avaiablePosition (blockPos + Vector3.left, true))*
* returnPos.Add (blockPos + Vector3.left);*
* if (!avaiablePosition (blockPos + Vector3.right, true))*
* returnPos.Add (blockPos + Vector3.right);*

* Debug.Log (“Returning " + returnPos.Count + " neighboring position”);*

* return returnPos;*

* }*
* // Check if position is avaiable.*
* bool avaiablePosition (Vector3 incPos, bool blocksOnly)*
* {*
* if (!blocksOnly) {*
* if (incPos.x > rightBorder.position.x)*
* return false;*
* else if (incPos.x < leftBorder.position.x)*
* return false;*
* else if (incPos.z > TopBorder.position.z)*
* return false;*
* else if (incPos.z < BottomBorder.position.z)*
* return false;*
* }*
* Vector3 rayStartPos = incPos + Vector3.up;*
* RaycastHit hit;*
* bool returnValue = true;*
* if (Physics.Raycast (rayStartPos, Vector3.down, out hit)) {*
* if (blocksOnly) {*
* if (hit.collider.gameObject.tag == assignedTag)*
* returnValue = false;*
* else*
* returnValue = true;*
* } else {*

* if (hit.collider.gameObject.tag == ignoreTag)*
* returnValue = true;*
* else*
* returnValue = false;*
* }*
* }*
* return returnValue;*
* }*