Using flood-fill to find unconnected nodes in bubble game

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

Advertisements