koobas.hobune.stream
The question is answered, right answer was accepted
Flood Fill algorithm implementation in C# problem
Hi i am trying to implement flood fill algorithm version 3 from Wiki here and I cant seem to get it right. I have a main method called flood fill and another helper method to get the game Object from a given position. My queue is of gameObject and so are my nodes. I can not seem to find out Why some times some of the tiles get deleted and i get null object reference error. lemme show you. 
Here when in the first image i click i get the next image where the tile at 0,0 gets deleted and then the next click i do gives me NullReferenceException: Object reference not set to an instance of an object.
This error does not nesacary comes up on the 3rd click but sometimes the floodfill method works for alot of clicks before i get a deleted tile and then eventually i get the error.
Can anyone please tell me whats going on. Thanks for any help.
here is the code
public void floodFill (GameObject node, Color targetColor, Color replacementColor)
{
Queue<GameObject> Q = new Queue<GameObject> ();
if (node.GetComponent<SpriteRenderer> ().color != targetColor)
return;
Q.Enqueue (node);
GameObject w, e, y;
while (Q.Count > 0) {
GameObject n = Q.Dequeue ();
if (FindGameObjectFromPos (new Vector3 (n.transform.position.x, n.transform.position.y)).GetComponent<SpriteRenderer> ().color == targetColor) {
w = n;
e = n;
y = n;
while (((w.transform.position.x) > 0) && FindGameObjectFromPos (new Vector2 (w.transform.position.x - 1, w.transform.position.y)).GetComponent<SpriteRenderer> ().color == targetColor) {
//FindGameObjectFromPos (new Vector3 (w.transform.position.x, w.transform.position.y)).GetComponent<SpriteRenderer> ().color = replacementColor;
w.transform.position = new Vector3 (w.transform.position.x - 1, w.transform.position.y, w.transform.position.z);
}
while (((e.transform.position.x < 18) && FindGameObjectFromPos (new Vector2 (e.transform.position.x + 1, e.transform.position.y)).GetComponent<SpriteRenderer> ().color == targetColor)) {
//FindGameObjectFromPos (new Vector3 (e.transform.position.x , e.transform.position.y)).GetComponent<SpriteRenderer> ().color = replacementColor;
e.transform.position = new Vector3 (e.transform.position.x + 1, e.transform.position.y, e.transform.position.z);
}
for (int i = (int)w.transform.position.x; i <= (int)e.transform.position.x; i++) {
//x.transform.position = new Vector2 (i, e.transform.position.y);
FindGameObjectFromPos (new Vector3 (i, y.transform.position.y)).GetComponent<SpriteRenderer> ().color = replacementColor;
if (((y.transform.position.y) > 0) && FindGameObjectFromPos (new Vector2 (i, y.transform.position.y - 1)).GetComponent<SpriteRenderer> ().color == targetColor) {
Q.Enqueue (FindGameObjectFromPos (new Vector2 (i, y.transform.position.y - 1)));
}
if (((y.transform.position.y) < 18) && FindGameObjectFromPos (new Vector2 (i, y.transform.position.y + 1)).GetComponent<SpriteRenderer> ().color == targetColor) {
Q.Enqueue (FindGameObjectFromPos (new Vector2 (i, y.transform.position.y + 1)));
}
}
}
}
}
GameObject FindGameObjectFromPos (Vector2 pos)
{
GameObject go;
Collider2D goc = Physics2D.OverlapPoint (pos);
go = goc.gameObject;
Debug.Log ("go " + goc.gameObject.GetComponent<SpriteRenderer> ().color);
return go;
}
You do some very strange things here. Especially those lines:
w.transform.position = new Vector3 (w.transform.position.x - 1, w.transform.position.y, w.transform.position.z);
e.transform.position = new Vector3 (e.transform.position.x + 1, e.transform.position.y, e.transform.position.z);
This will effectively move your tile to the neighbor position. Why do you do that? All the tiles should stay at their initial position. That's why you get a null reference exception because your "FindGameObjectFromPos" method can't find a tile at the position because you moved it somewhere else. You your variables n, w, e, y are reference type variables. So they all reference the same object.
Besides that your approach is extremely inefficient. You actually have a fix grid, so it would make more sense to populate an array / two dimensional array with all your tiles and just work on that. Also storing gameobjects is a bad idea in general. You are mainly interested in the SpriteRenderer components of the gameobject. So you should store those instead.
Quite some time ago someone asked a very similar question. However he wanted to do a flood fill in a texture, not on a grid of gameobject I've implemented the second alternative algorithm as extension methods for the Texture2D class. Those two extensions are also on the Unity wiki.
Sorry, but as your code stands at the moment it's really hard to follow what happens (and what should happen).
Ok I got it working by changing the variables w,e,y to value type variables. 2 Problems exist 1) it is very slow. I mean after i click on a color it takes some time before it fills 2) If i click on the same color as the flooded color it crashes. to solve this i can add if (node.GetComponent ().color == replacementColor) return;
I still have a queue of gameobjects tho. Do you suggest using a queue of spriterenderer ins$$anonymous$$d? will this help in performance?
here is what i have changed
public void floodFill (GameObject node, Color targetColor, Color replacementColor)
{
Queue<GameObject> Q = new Queue<GameObject> ();
if (node.GetComponent<SpriteRenderer> ().color != targetColor)
return;
Q.Enqueue (node);
while (Q.Count > 0) {
GameObject n = Q.Dequeue ();
if (FindGameObjectFromPos (new Vector3 (n.transform.position.x, n.transform.position.y)).GetComponent<SpriteRenderer> ().color == targetColor) {
int w = (int)n.transform.position.x;
int e = (int)n.transform.position.x;
int y = (int)n.transform.position.y;
while ((w > 0) && FindGameObjectFromPos (new Vector2 (w - 1, y)).GetComponent<SpriteRenderer> ().color == targetColor) {
w--;
}
while (((e < 18) && FindGameObjectFromPos (new Vector2 (e + 1, y)).GetComponent<SpriteRenderer> ().color == targetColor)) {
e++;
}
for (int i = w; i <= e; i++) {
FindGameObjectFromPos (new Vector3 (i, y)).GetComponent<SpriteRenderer> ().color = replacementColor;
if ((y > 0) && FindGameObjectFromPos (new Vector2 (i, y - 1)).GetComponent<SpriteRenderer> ().color == targetColor) {
Q.Enqueue (FindGameObjectFromPos (new Vector2 (i, y - 1)));
}
if ((y < 18) && FindGameObjectFromPos (new Vector2 (i, y + 1)).GetComponent<SpriteRenderer> ().color == targetColor) {
Q.Enqueue (FindGameObjectFromPos (new Vector2 (i, y + 1)));
}
}
}
}
}
Ok i am reviewing the code. I think i misunderstood the algorithm. It said " Move w to the west until the color of the node to the west of w no longer matches target-color." so i moved the tile. What does it mean by "move w" then?
I will eventually want the grid to move infinity to the right. meaning the grid will delete columns from the left and add more to the right. @Bunny83
