Flood fill example in C
|
|
This flood fill code is adapted from a Tetris clone called "Tetanus On Drugs" by Damian Yerrick. It's licensed under the GNU Lesser General Public License (in addition to the GNU FDL that covers all of Wikipedia) and comes with ABSOLUTELY NO WARRANTY.
#define BOARD_WIDTH 10
#define BOARD_HEIGHT 20
typedef struct MAP
{
unsigned char b[BOARD_HEIGHT][BOARD_WIDTH];
} MAP;
static void flood_loop(MAP *map, int x, int y,
unsigned int dst_c, unsigned int src_c)
{
int fillL, fillR, i;
int in_line = 1;
//unsigned char c = src_c, fillC = dst_c;
/* find left side, filling along the way */
fillL = fillR = x;
while( in_line )
{
map->b[y][fillL] = dst_c;
fillL--;
in_line = (fillL < 0) ? 0 : (map->b[y][fillL] == src_c);
}
fillL++;
/* find right side, filling along the way */
in_line = 1;
while( in_line )
{
map->b[y][fillR] = dst_c;
fillR++;
in_line = (fillR > BOARD_WIDTH-1) ? 0 : (map->b[y][fillR] == src_c);
}
fillR--;
/* search top and bottom */
for(i = fillL; i <= fillR; i++)
{
if( y > 0 && map->b[y - 1][i] == src_c )
flood_loop(map, i, y - 1, dst_c, src_c);
if( y < BOARD_HEIGHT && map->b[y + 1][i] == src_c )
flood_loop(map, i, y + 1, dst_c, src_c);
}
}
void flood_fill(MAP *map, int x, int y, unsigned int c)
{
flood_loop(map, x, y, c, map->b[y][x]);
map->b[y][x] = c; /* some buggy optimizers needed this line */
}
This is the same algorithm adapted by Claudio Santana for the Java programming language:
int checkPixel(int[] oldPix, int[] newPix)
{
return (newPix[0] == oldPix[0] &&
newPix[1] == oldPix[1] &&
newPix[2] == oldPix[2] &&
newPix[3] == oldPix[3] ? 1:0);
}
void floodLoop(WritableRaster raster, int x, int y, int[] fill, int[] old)
{
int fillL, fillR,i;
int in_line=1;
int[] aux = {255,255,255,255};
// find left side, filling along the way
fillL = fillR = x;
while(in_line!=0)
{
int[] p = raster.getPixel(fillL,y,aux);
raster.setPixel(fillL,y,fill);
fillL--;
in_line = (fillL < 0) ? 0 : checkPixel(raster.getPixel(fillL,y,aux),old);
}
fillL++;
// find right side, filling along the way
in_line = 1;
while (in_line!=0)
{
raster.setPixel(fillR,y,fill);
fillR++;
in_line = (fillR > d.width-1) ? 0 : checkPixel(raster.getPixel(fillR,y,aux),old);
}
fillR--;
// look up and down
for( i=fillL; i<=fillR; i++ )
{
if ( y>0 && checkPixel(raster.getPixel(i,y-1,aux),old)!=0 )
floodLoop(raster,i,y-1,fill,old);
if ( y<d.height-1 && checkPixel(raster.getPixel(i,y+1,aux),old)!=0 )
floodLoop(raster,i,y+1,fill,old);
}
}
// Initial method you must call
void floodLoop(WritableRaster raster, int x, int y, int[] fill)
{
int[] aux = new int[] {255,255,255,255};
// validation so we don't fall in an infinite loop trying to
// paint in the same color
if ( checkPixel(raster.getPixel(x,y,aux),fill)!=0 )
return;
floodLoop(raster,x,y,fill,raster.getPixel(x,y,aux) );
}