Using flood-fill to find unconnected nodes in bubble game
2011/09/12 Leave a comment
A previous blog post solved this algorithm with a recursive method. Since then, it became necessary to improve the speed a little.
We will solve it the same way, using the flood/seed-fill algorithm (commonly used in graphics-editing programs Fill/Paint Bucket tool), but improve it by making it iterative and using c++ STL’s stack, vector, and map containers.
-(void) flagConnectedWithIndex:(int)index { Enemytarget *targ = mapAllEnemies_[index]; targ.connected = YES; stack stack; stack.push(index); while(!stack.empty()) { int currIdx = stack.top(); stack.pop(); vector neighbors = [self getNeighborsWithIndex:currIdx]; for(unsigned int x = 0; x < neighbors.size(); x++) { int neighborIdx = neighbors[x]; if(mapAllEnemies_[neighborIdx] != nil) { Enemytarget *t = mapAllEnemies_[neighborIdx]; if(!t.connected) { t.connected = YES; stack.push(t.index); } } } } }
In this method, mapAllEnemis_ is a 1d sparse index array containing all of the bubbles. It is using STL’s map. getNeighborsWithIndex is also using the STL vector class. If we use swap this class to return an NSArray of NSNumber objects, the flagConnectedWithIndex method finishes much more slowly.
In the screenshot, you see there are 9 nodes/bubbles max. per row. On even rows with the black labels, the row is shifted to the right 16 px. On odd rows, shifted to the left.
-(std::vector) getNeighborsWithIndex:(int)index { vector surrIndices; // right - black labels in screen cap if(index/Grid_Num_H %2 == 0) { if( (index+1) %Grid_Num_H != 1) { surrIndices.push_back( index - 1); // left surrIndices.push_back(index - Grid_Num_H -1); // bottom left surrIndices.push_back(index + Grid_Num_H -1); // top left } if( (index+1) % Grid_Num_H != 0) surrIndices.push_back(index +1); // right surrIndices.push_back(index - Grid_Num_H); // bottom right surrIndices.push_back(index + Grid_Num_H); // top right } // left (white labels in screen capture) else { surrIndices.push_back(index - Grid_Num_H); // bottom left surrIndices.push_back(index + Grid_Num_H); // top left if(index % Grid_Num_H != 0 ) surrIndices.push_back(index - 1); // left if(index % Grid_Num_H != 8 ) { surrIndices.push_back(index + 1); //right surrIndices.push_back(index - Grid_Num_H + 1); // bottom right surrIndices.push_back(index + Grid_Num_H + 1); // top right } } return surrIndices; }