- Home /
Problem searching grid using recursive function
Hello, I am working on a falling-block puzzle game similar to Tetris or Lumines. Players guide blocks as they fall stack them on the bottom of a grid. The way blocks are cleared is that each block needs to be "marked" by a nearby bomb block is exploded. Once all blocks in a chain (connected blocks of same color) are marked, that chain is cleared from the board.
I wrote a series of functions to check and see when a chain is completely marked and to clear it. However I am having a problem where blocks are getting cleared before the entire chain is marked.
I use this function on each marked block to see if the chain it is in is completely marked or not. It is supposed to check each connected marked (called primed in code) block of the same color and return false as soon as one block in the chain is connected to an unchecked block of the same color, and return true otherwise. So the function should assume the chain is fully marked until a single block is determined to be in the chain that is not marked, at which point it should stop working and return false.
public bool checkFullChain(int x, int y, int type) //return true if the chain is full
{
bool check = true;
gridSearched[x,y] = true; // mark each block as searched to avoid infinite looping
if(connectedToUnprimed(x, y, type)) //this function determines if the block is touching an unchecked block or not
{
Debug.Log("incomplete chain at: " + x +","+ y);
check = false; //the chain is incomplete if a single primed block is touching a single unprimed block
return check;
}
else
{
if(this.GetComponent<gameController2>().grid[x+1,y] == type && gridSearched[x+1,y] == false && check == true) //check to see if the rest of chain is connected to an unprimed block or not
{
check = checkFullChain(x+1, y, type);
}
else if(this.GetComponent<gameController2>().grid[x-1,y] == type && gridSearched[x-1,y] == false && check == true)
{
check = checkFullChain(x-1, y, type);
}
else if(this.GetComponent<gameController2>().grid[x,y+1] == type && gridSearched[x,y+1] == false && check == true)
{
check = checkFullChain(x, y+1, type);
}
else if(this.GetComponent<gameController2>().grid[x,y-1] == type && gridSearched[x,y-1] == false && check == true)
{
check = checkFullChain(x, y-1, type);
}
}
return check; //return true if the chain has no unprimed blocks in it
}
So do you think that this function works as intended? I feel like the error I'm getting is that as soon as the seed block for a chain is not touching an unchecked block, it is clearing it out, as if the entire chain isn't being checked. Am I using recursion wrong? I'm thinking that the function is returning true as soon as a single recursive statement returns true, or something. What do you think? I want to at least determine if this function works properly or not so I can know if I should check a different function.
Thanks for any help.
Answer by VioKyma · Aug 04, 2013 at 01:59 AM
For clarity you may even want to use one Boolean for each adjacent block position, then
if(left && right && top && bottom)
{
return true;
}
else
{
return false;
}
this is more for your own ability to follow the logic, but this seems to be where the problem lies so it may help in show the issue.
It seems that Jamora is right. The else if usage means that if one of those cases is true, the rest will be skipped, which is not what you want to happen (if I understand your algorithm correctly). If you want the algorithm to check every one of those conditions, simply remove the else from all the if statements (EDIT: that is lines 17, 21 and 25) and it will sequentially check each case.
Thanks a lot for your help guys. I got it working now by switching to a 4-boolean system as suggested by viokyma. Thanks!
Please mark this as the answer if it has helped so others can see this question is resolved. Thanks :)
Answer by Jamora · Aug 02, 2013 at 04:05 AM
One thing that strikes odd is that you use else if's. Only one of your if clauses are being entered... Maybe I just didn't understand your algorithm properly.
I actually had my code like that before and it still had the same problem (in fact there's no discernible difference between using if statements and else if statements).
$$anonymous$$y code now looks like this but I still have the same problem:
public bool checkFullChain(int x, int y, int type) //return true if the chain is full
{
bool check = true;
gridSearched[x,y] = true; // mark each block as searched to avoid infinite looping
if(connectedToUnprimed(x, y, type))
{
Debug.Log("incomplete chain at: " + x +","+ y);
check = false; //the chain is incomplete if a single primed block is touching a single unprimed block
return check;
}
else
{
if(this.GetComponent<gameController2>().grid[x+1,y] == type && gridSearched[x+1,y] == false && check == true) //check to see if the rest of chain is connected to an unprimed block or not
{
check = checkFullChain(x+1, y, type);
}
if(this.GetComponent<gameController2>().grid[x-1,y] == type && gridSearched[x-1,y] == false && check == true)
{
check = checkFullChain(x-1, y, type);
}
if(this.GetComponent<gameController2>().grid[x,y+1] == type && gridSearched[x,y+1] == false && check == true)
{
check = checkFullChain(x, y+1, type);
}
if(this.GetComponent<gameController2>().grid[x,y-1] == type && gridSearched[x,y-1] == false && check == true)
{
check = checkFullChain(x, y-1, type);
}
}
return check; //return true if the chain has no unprimed blocks in it
}
So do you see anything else that could be wrong, or is my problem probably in a different function?
It would seem that the last condition in your ifs act much akin to an else clause. Remove the && check == true
and ins$$anonymous$$d deter$$anonymous$$e the state of check
with
check = check && checkFullChain(x, y-1, type);
Could you elaborate a little more? Where should that line of code that you written go? Is it part of the if statement or inside each if statement?
You're saying each If statement should look like this?
if(this.GetComponent<gameController2>().grid[x,y-1] == type && gridSearched[x,y-1] == false)
{
check = check && checkFullChain(x, y-1, type);
}
Correct. I still have see$$anonymous$$gly the exact same problem. $$anonymous$$y code looks like this now:
public bool checkFullChain(int x, int y, int type) //return true if the chain is full
{
bool check = true;
gridSearched[x,y] = true; // mark each block as searched to avoid infinite looping
if(connectedToUnprimed(x, y, type))
{
Debug.Log("incomplete chain at: " + x +","+ y);
check = false; //the chain is incomplete if a single primed block is touching a single unprimed block
return check;
}
else
{
if(this.GetComponent<gameController2>().grid[x+1,y] == type && gridSearched[x+1,y] == false) //check to see if the rest of chain is connected to an unprimed block or not
{
check = check && checkFullChain(x+1, y, type);
}
if(this.GetComponent<gameController2>().grid[x-1,y] == type && gridSearched[x-1,y] == false)
{
check = check && checkFullChain(x-1, y, type);
}
if(this.GetComponent<gameController2>().grid[x,y+1] == type && gridSearched[x,y+1] == false)
{
check = check && checkFullChain(x, y+1, type);
}
if(this.GetComponent<gameController2>().grid[x,y-1] == type && gridSearched[x,y-1] == false)
{
check = check && checkFullChain(x, y-1, type);
}
}
return check; //return true if the chain has no unprimed blocks in it
}
I just want to make sure this function is working how it is supposed to (maybe another part of my code is working wrong), although I'm pretty sure this is the function causing the problem. As soon as a marked block is touching 2 or more other marked blocks and isn't touching an unmarked blocks, all marked blocks in the chain get cleared.
Your answer
![](https://koobas.hobune.stream/wayback/20220613111410im_/https://answers.unity.com/themes/thub/images/avi.jpg)