5
\$\begingroup\$

I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine.

Update

Here is my code for DFS

-(void)callDfs:(int)startR:(int)startC:(int)color{

notVisitedBubblesArr = [[NSMutableArray alloc]init];


//reset visited matrix to false.
for(int i = 0; i < R; i++)
    for(int j = 0; j < C; j++)
        visited[i][j] = FALSE;

//reset count
count = 0;
isFound = NO;
bubbleBlastCount = 0;
[self dfs:startR :startC :color :false];

[self bubbleFalling];


}
-(void)dfs:(int)ro:(int)co:(int)colori:(BOOL)set{
    coundown++;
    for(int dr = -1; dr <= 1; dr++)
        for(int dc = -1; dc <= 1; dc++)
            if([self ok:ro+dr :co+dc]) // 4 neighbors
            {
                int nr = ro+dr;
                int nc = co+dc;

                if ((([[[bubbles_Arr objectAtIndex:nr] objectAtIndex:nc]   integerValue]==colori) && !visited[nr][nc])) {
visited[nr][nc] = true;
count++;
[self dfs:nr :nc :colori :set];
if(count>2)
{
// pass row and colom will start dfs
//  if (nr >= touchClum && nc >= touchROW) {
isFound = YES;
bubbleBlastCount++;
[[bubbles_Arr objectAtIndex:nr] replaceObjectAtIndex:nc withObject:NOCOLOR];
[bubbles[nc+1][nr+1] setTexture:[[CCTextureCache sharedTextureCache] addImage:@"blank.png"]];
}
}
}
}

Now i am trying to implement bubble falling using DFS, i studied this link. i got all unvisited nodes after DFS but i am not able to verify with node is connected to top.

Here is my code for bubble falling

-(void)bubbleFalling{

for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){    
if (!visited[i][j]) {
    //NSLog(@"Array :  %d %d", i,j);

    NSLog(@"Value : %d",[[[bubbles_Arr objectAtIndex:i] objectAtIndex:j] integerValue]);

    BOOL canReach = [self canreachTop:i :j];
    if(canReach){
        NSLog(@"Yes");


    }
    else{
        NSLog(@"NO");
        [[bubbles_Arr objectAtIndex:i] replaceObjectAtIndex:j withObject:NOCOLOR];
        [bubbles[j+1][i+1] setTexture:[[CCTextureCache sharedTextureCache] addImage:@"blank.png"]];
    }

}


    }
}
}

-(BOOL)canreachTop:(int)ro:(int)co{
   int topNode = [[[bubbles_Arr objectAtIndex:R-1]objectAtIndex:C-1] integerValue];

BOOL success = FALSE;
for(int dr = -1; dr <= 1; dr++)
    for(int dc = -1; dc <= 1; dc++)

        if([self ok:ro+dr :co+dc]) // 4 neighbors
        {
            int nr = ro+dr;
            int nc = co+dc;

            if ((([[[bubbles_Arr objectAtIndex:nr] objectAtIndex:nc] integerValue]== topNode) && !visited[nr][nc])) {
            success = TRUE;
            }
        }

return success;
}


-(BOOL)ok:(int)r:(int)c{
    return r >= 0 && r < R && c >= 0 && c < C;
}

Below is the screenshot of my iPhone simulator in that green bubble should fall because it is not connected with any bubble, i think we have to check whether it is connected with the top bubble or not or i have to follow some other approach?

screenshot

This is my first game and i am not getting what is wrong with my bubble falling code.

Thanks in advance.

\$\endgroup\$
  • \$\begingroup\$ "I don't want to implement flood-fill", I hope there is a reason other than I don't want to? Another thing, If you already implemented search using DFS, I don't see how falling bubbles are different can you elaborate ? \$\endgroup\$ – concept3d Jan 27 '14 at 7:38
  • \$\begingroup\$ As far as i understand searching can be implemented using flood-fill and DFS, so i have implemented DFS. Now i have already implemented DFS so why should i implement another algorithm. \$\endgroup\$ – Champ Jan 27 '14 at 9:04
  • \$\begingroup\$ Yes, my primary question is why a falling bubble is different. your question is not clear in its current form. \$\endgroup\$ – concept3d Jan 27 '14 at 9:05
  • 1
    \$\begingroup\$ Without further details on how you're implementing things, it's unclear what kind of answer you're expecting here. Depending how you're using DFS, it should be suitable for this situation. You may want to confirm your code is working properly by using the debugger. \$\endgroup\$ – MichaelHouse Jan 27 '14 at 17:24
  • 1
    \$\begingroup\$ @LuisEstrada - Yes i have studied that i have implemented that as well, please check my updated question. \$\endgroup\$ – Champ Jan 27 '14 at 18:49
1
\$\begingroup\$

If you are using DFS starting from the top, all unvisited nodes should drop. The top should be an invisible node connected to all top bubbles (in the top row). One thing worth noting, is that unlike the current DFS which is checking for color equality, the functionality you should use for deciding which bubbles to drop because they are hanging in the air should ignore color and simply be content with bubbles being accessible from the top.

  1. Run DFS from the newly added bubble with same color condition to see which bubbles to drop.
  2. Run DFS from the top with no color condition and drop all bubbles that are hanging in the air.

I will try to clear it up. You are checking if a bubble can reach the top.. Don't. Run your DFS starting from the top and simply remove (drop) unvisited nodes.

\$\endgroup\$
  • \$\begingroup\$ No if bubble color doesn't match bubble can't fall. \$\endgroup\$ – Hemant Singh Rathore Jan 29 '14 at 9:07
  • \$\begingroup\$ If the color doesn't match but the bubble is hanging in the air it should fall. \$\endgroup\$ – wolfdawn Jan 29 '14 at 9:08
  • \$\begingroup\$ Yes for the bubble falling there is no need of color matching, but if we only drop unvisited node some other bubbles fall as well. In canReachTop method i have put a condition if ((([[[bubbles_Arr objectAtIndex:nr] objectAtIndex:nc] integerValue]== topNode) && !visited[nr][nc])) { if i remove color condition many other bubbles falls. \$\endgroup\$ – Hemant Singh Rathore Jan 29 '14 at 9:10
  • \$\begingroup\$ There are two steps here. 1. Check which bubbles are same color and could be visited (with DFS) from the bubble you just shot. 2. Check which bubbles are still accessible from the top, drop the rest. It's two different kinds of DFS, one checks for color, the other does not. \$\endgroup\$ – wolfdawn Jan 29 '14 at 9:13
  • \$\begingroup\$ in second step you suggested that we need to check which bubble is accessible from top, if you see the question that is all we need to do verify which bubble is connected to top. \$\endgroup\$ – Hemant Singh Rathore Jan 29 '14 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.