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;
}