Friday, June 15, 2018

algorithm - Verify which bubble is connected to top using DFS


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.




No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...