Grouping 2D array of instances

Question

I have a working solution for this, though I am convinced there must be a better implementation. In a nut shell the problem is this:

I am working on a connect>=3, bejewelled style puzzle game. When the state of the 'board' changes I group all the pieces such that if they are 'connected' horizontally or vertically they share an ID. This is how I do it currently:

[pseudo]

for all( array object* )
{
    if !in_a_group() check_neighbours( this )
}

void check_neighbours( ID )
{
    if ( check_is_same_type( left ) )
    { 
        if !in_a_group() this.ID = ID ; check_neighbours( ID )
        else if( in_a_group ) change_IDs(this.ID, ID ) 
    }
    same for right ...
    up ...
    down ...     
}

That is a really dirty pseudo version of what I do. I recursively call check_neighbours, passing the ID of the first branch piece forward (I use this pointer as an ID rather than generating one).

If I find a piece with a different ID that is connected I overwrite all pieces with that ID with new ID ( I have an ASSERT here cos it shouldn't actually happen. It hasn't so far in lots of testing)

I don't check_neighbours at the original branch unless the piece has no ID.

This works just fine, though my pseudo is probably missing some small logic. My problem is that it has the potential to use many branches (which may be a problem on the hardware I am working on). I have worked on the problem so long now that I can't see another solution. Ever get the feeling you are missing something incredibly obvious?

Also I am new to stackoverflow, reasonably new to programming and any advice on etiquette etc is appreciated.

Answer 1

How would you suggest avoiding recursion?

As I understand it, your algorithm is basically a "flood fill" with a small twist.

Anyway, to avoid recursion, you need to allocate array to store coordinates of unprocessed items and use queue or fifo. Because you know dimensions of grid (and since it is bejeweled-style(?) game, you should be able to preallocate it pretty much anywhere.

pseudocode for any flood-fill-type recursive algorithm.

struct Coord{
    int x, y;
}

typedef std::queue<Coord> CoordQueue;

bool validCoord(Coord coord){
    return (coord.x >= 0) && (coord.y >= 0) 
        && (coord.x < boardSizeX) && (coord.y < boardSizeY);
}

bool mustProcessCoord(Coord coord);

void processAll(){
     CoordQueue coordQueue;
     Coord startPoint = Coord(0, 0);
     coordQueue.pushBack(startPoint);

     while (!coordQueue.empty()){
         const Coord &curCoord = coordQueue.front();
         //do something with current coordinates.
         processCoord(curCoord);

         const int numOffsets = 4;
         const int offsets[numOffsets][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
         for (int offsetIndex = 0; offsetIndex < numOffsets; offsetIndex++){
              Coord neighborCoord = Coord(curCoord.x + offsets[offsetIndex][0],
                    curCoord.y + offsets[offsetIndex][1]); 
              if (!isValidCoord(neighborCoord) || !mustProcessCoord(neighborCoord))
                  continue;
              coordQueue.push_back(neighborCoord);
         }

         coordQueue.pop_front();
     }
}

See ? no recursion, just a loop. Pretty much any recursive function can be unwrapped into something like that.

If your underlying platform is restrictive and you have no std::queue, use array (ring buffer implemented as array can act like fifo queue) instead. Because you know size of the board, you can precalculate size of array. The rest should be easy.