koobas.hobune.stream
How to determine the number of bubbles that share that same color in a cluster and return as a list?
Hello Unity Community,
I am currently working on my first game in unity C# and I have been having problems figuring out a solution to count the total number of bubbles in a cluster and return it as a list.
So far, I have wrote and used a flood fill algorithm found on wikipedia on c# and tested it on visual studio. I had success implementing the algorithm on visual studio, however, I am having problems applying the flood fill algorithm to count the number of bubbles that share the same color and return them as a list.
Whenever I run the particular function using recursion onto visual studio, I get a stackoverflow exception, which I don't know exactly why it is happening:
//stack overflow exception...
public List<char> CharClusterRecursive(char key,char target,int x,int y)
{
List<char> cluster = new List<char>();
//base case
if (key != target && textWorld[y, x] != key)
return null;
//add to cluster if matches criteria
cluster.Add(key);
//left
if(x - 1 >= 0)
cluster.AddRange(CharClusterRecursive(textWorld[y,x - 1],target,x - 1,y));
//right
if(x + 1 < width)
cluster.AddRange(CharClusterRecursive(textWorld[y,x + 1],target,x + 1,y));
//up
if (y + 1 < height)
cluster.AddRange(CharClusterRecursive(textWorld[y + 1, x], target, x, y + 1));
if (y - 1 >= 0)
cluster.AddRange(CharClusterRecursive(textWorld[y - 1, x], target, x, y - 1));
return cluster;
}
I have also tested the same function using recursion above in unity with the following function (game crashed when I run it with the script attached, I assume its also a stackoverflow exception):
Unity Function
public List<Orb> ColorClusterRecursive()
{
//declarations
//step 1 obtain orb's neighbors.
List<Orb> theNeighbors = this.Neighbors ();
//step 2 obtain orb's list by color.
List<Orb> filterByColor = this.FilterByColor (theNeighbors,render.sprite.name);
List<Orb> cluster = new List<Orb> ();
cluster.Add (this);
//base case:
if (filterByColor.Count == 0 || filterByColor == null)
return cluster;
//for every neighbor of the same color as the original orb
//iterate through them and Add potential neighbors of the same color through recursion.
foreach(Orb neighbor in filterByColor)
{
List<Orb> MoreNeighbors = neighbor.Neighbors ();
List<Orb> filterNeighbors = neighbor.FilterByColor (MoreNeighbors,render.sprite.name);
cluster.Add (neighbor);
//breaks game cluster.AddRange (neighbor.ColorClusterRecursive ());
}
return cluster;
}
Neighbors Function
//returns the neighbors the orb may have in the grid.
public List<Orb> Neighbors()
{
//get locallPosition of the balls if in grid.
int row = (int)transform.localPosition.y;
int col = (int)transform.localPosition.x;
List<Orb> list = new List<Orb> ();
// float gridHeight = (float)matrix.dim.height;
// float gridWidth = (float)matrix.dim.width;
Debug.Log (transform.localPosition.x + ":" + transform.localPosition.y);
Debug.Log (row + ":" + col);
//left
if (col > 0f)
{
Debug.Log ("L");
list.Add (gridRef[row,col - 1]);
}
//right
if (col + 1 < gridWidth)
{
Debug.Log ("R");
list.Add (gridRef[row,col+1]);
}
//top
if (row + 1 < gridHeight)
{
Debug.Log ("T");
list.Add(gridRef[row + 1,col]);
}
//bot
if (row - 1 >= 0f)
{
Debug.Log ("B");
list.Add (gridRef[row - 1,col]);
}
return list;
}
FilterByColor Function
//obtains a list of orbs and filters them by color
public List<Orb> FilterByColor(List<Orb> listToSort, string color)
{
List<Orb> listToReturn = new List<Orb>();
for(int i = 0;i < listToSort.Count;i++)
{
if(listToSort[i].render.sprite.name == color)
{
listToReturn.Add (listToSort[i]);
}
}
return listToReturn;
}
Goal: To count the number of bubbles that share the same color and are connected with each other as neighbors.
Are there any better ways of finding a cluster of bubbles that share the same color on a grid in unity? If so, please enlighten me with the knowledge : )
I'm reading this on mobile and that's a lot of code, but I don't see any of those methods excluding the items that were already added to the cluster. I believe if you have 2 matching itemsside by side, the first one will add the neighbour to the cluster, when the neighbor checks for neighbors it will add the original tile to the cluster for$$anonymous$$g an endless loop.
You should probably have a List field where all the clustered items are added to and check with if (!list.Contains(item) ) before you add a new item. Performance wise it would be better to use a alreadyAdded boolean in your item class and to use that so that you don't need to use the slow Contains method (tjat basically loops through the list to see if the item is there)
Hello,
After trying out your suggestion, my code is now only adding one bubble to the list. Here is the updated code in unity:
public List<Orb> ColorClusterRecursive(List<Orb> visited,string orbColor)
{
//declarations
//step 1 obtain orb's neighbors.
List<Orb> theNeighbors = this.Neighbors ();
//step 2 obtain orb's list by color.
List<Orb> filterByColor = this.FilterByColor (theNeighbors,orbColor);
List<Orb> cluster = new List<Orb> ();
//this is the current orb adding to the list.
if (!visited.Contains (this))
{
return cluster;
}
visited.Add (this);
//else add this orb to the cluster.
cluster.Add (this);
//base case:
if (filterByColor.Count == 0 || filterByColor == null)
return cluster;
//for every neighbor of the same color as the original orb
//iterate through them and Add potential neighbors of the same color through recursion.
foreach(Orb neighbor in filterByColor)
{
// List<Orb> $$anonymous$$oreNeighbors = neighbor.Neighbors ();
// List<Orb> filterNeighbors = neighbor.FilterByColor ($$anonymous$$oreNeighbors,render.sprite.name);
// cluster.Add (neighbor);
cluster.AddRange (neighbor.ColorClusterRecursive (visited,orbColor));
}
return cluster;
}
Here is the code that tests the function:
List<Orb> visit = new List<Orb> ();
List<Orb> recurTest = orb$$anonymous$$atrix [0, 9].ColorClusterRecursive(visit,"blue");
Debug.Log ("# of bubbles: " + recurTest.Count);
for (int i = 0; i < recurTest.Count; i++)
{
Debug.Log ("Position: " + recurTest[i].transform.localPosition);
Debug.Log (i + " " + recurTest[i].name + ": " + recurTest[i].OrbColor);
}
@NoseKills After surfing through the web for alternate solutions to the flood fill recursive algorithm in determining a number of orbs to be placed in a cluster, I found the solution for those that are trying to also create a bubbleshooter clone.
I use the following UPDATED code to determine how many orbs belong to a cluster and return it as a list (It now uses a while loop with a stack):
public List<Orb> ClusterTrial3(string color)
{
//create a stack that will process orbs that get pushed onto the data structure.
Stack<Orb> toprocess = new Stack<Orb> ();
//push this instance of orb onto the stack.
toprocess.Push (this);
//set the process flag = true.
this.inProcess = true;
//the cluster list that we return to find out how many orbs are contained in a cluster.
List<Orb> cluster = new List<Orb> ();
//deterministic style loop that exits out once there are no more orbs to pop out from the stack.
while (toprocess.Count > 0)
{
//remove the top item from the stack.
Orb currentOrb = toprocess.Pop ();
//find neighbors of the current_orb
List<Orb> neighbors2 = currentOrb.Neighbors ();
//filter the currentOrb's neighbors by color.
List<Orb> filteredColor = currentOrb.FilterByColor (neighbors2, color);
//add the currentOrb to the list
cluster.Add (currentOrb);
//loop through the list of filteredColors
for (int i = 0; i < filteredColor.Count; i++)
{
//if the filteredColor orb is NOT in PROCESS of being ADDED to the cluster,
if (!filteredColor[i].inProcess)
{
//push it to the toprocess stack
toprocess.Push (filteredColor [i]);
//set it to be in process true.
filteredColor[i].inProcess = true;
}
}
}
return cluster;
SPECIAL THANKS to this website for the solution: http://rembound.com/articles/bubble-shooter-game-tutorial-with-html5-and-javascript
Code is in javascript and html5, but should be easily converted to C# code using the libraries we have for it.
