Codesnippets > 2D-snippets

Very fast floodfill

<< < (2/6) > >>

I think I have addressed the crashing problem, the code that checks if it is in bounds

--- Code: (glbasic) ---IF startx<0 OR starty<0 OR startx>=width% OR starty>=height THEN DEBUG "Out of area."
--- End code ---
didn't exit the function if it was passed co-ords that where outside the image, so should read

--- Code: (glbasic) ---IF startx<0 OR starty<0 OR startx>=width% OR starty>=height
DEBUG "Out of area."
--- End code ---
so have amended the above attachment

To test the algorithm I originally used SETPIXEL & GETPIXEL which worked fine but as you know they are seriously slow. Once I knew it was working that is when I abandoned them in favour of SPRITE2MEM for a boost (and what a boost that made lol).

Due to GLBasic being double buffered & the SPRITE2MEM command only working on the back buffer I have yet to figure out an elegant way to do a fill on the entire screen without resorting to using GRABSPRITE prior to calling the fill. So if you want to fill on the entire screen at the moment the following steps are required

* Draw your graphics
* Draw your grabbed sprite so you can select an area to fill
* Call the fill function
* Draw the modified sprite then SHOWSCREEN to see it
The above is not required if filling an existing sprite as you just pass the function the SPRITEID.

Any thoughts or suggestions on the fullscreen issue would be appreciated & I am trying to figure out a better solution at the moment.


This flood fill is just what I need for my current project. Thanks a ton, Fuzzy.  :good:

Hi Fuzzy,

I hope you don't mind, but I have built upon your outstanding fast-fill code to improve its efficiency when filling a lot of small areas on the screen.
The updated function is called FloodFill.

* Instead of operating on the entire screen, we can now flood within a small subset of the screen. This efficiency can provide a nice speed boost when we have a lot of elements on the screen which we need to fill, as with the cells of a game board, for example.
* Definitions and types used by the function are now internal to the function, so that it can better stand alone.
* Many of the parameters are optional. The default values are based on sizes from the full screen. 
* There is now a Preview mode, to help programers see the exact section of the screen they are capturing, and the starting pixel.
* A description of each of FloodFill's parameters is now included in the comments.
* Several example calls to FloodFill are available in the example program, to demonstrate the behavior of the modified function.
   (To use FloodFill as a stand-alone function, delete the demonstration program in favor of your own.)

Check it out.

--- Code: (glbasic) ---SETSCREEN 1000,750,FALSE

// Let's draw an object on the screen and split it in half, so that we can capture the object to a sprite and flood-fill one of the halves.
DRAWRECT 350,350,60,60,RGB(255,255,255);DRAWRECT 351,351,58,58,RGB(0,255,0)
DRAWLINE 351,351,409,409,RGB(255,255,255)

// Activate any of these example FloodFill settings to see how the FloodFill function behaves.
// Note that in each case of flood filling inside the square, the starting x and y pixel locations are set to avoid the white lines.
// ------------------------------
// If you disable all of the floodfill commands below, the screen will show a square with both triangle halves the same green color, on a black background.
// ------------------------------
 FloodFill (351,352,RGB(0,0,255)) // Sets the starting pixel within the lower triangle of the box, and uses the entire screen. Capturing the entire screen to fill a small area is not very efficient, but operating on the entire screen has its uses, such as coloring a border. By default, the entire screen is used.
// FloodFill (03,5,RGB(0,0,255),350,350,60,60) // captures only the drawn-box area and uses pixel 3,10 within that box to avoid the outline. Therefore the lower triangle will be filled in. This focused fill does the same job as the line above, but much more efficiently.
// FloodFill (0,0,RGB(0,0,255)) // Sets the start pixel at x=0,y=0 using the entire screen. Therefor everything around the box will be colored in, because everything shares the background pixel color of pixel 0,0.
// FloodFill (345,345,RGB(0,0,255),325,300) // Captures only part of the screen and fills it, surrounding the box. Because no width or height is given, the defaults are the limits of the screen.
// FloodFill (345,345,RGB(0,0,255),325,300,500,400) // Captures only part of the screen and fills it, surrounding the box. Here a width and height are given, and the flood is limited by the size of the captured screen.
// FloodFill (03,05,RGB(0,0,255),350,350,60,60,TRUE) // Targets only the box, but turns Preview mode on. Preview mode allows you to see exactly what your settings will capture, before the flood, and its position on the screen.
//                                                   // The pixel Pix_Num_X, Pix_Num_Y is marked in white, unless the background is already white, in which case it is marked in Black.
//                                                   // (A single pixel is hard to see, so you will have to look carefully to see it.)
//                                                   // This pixel color is restored to its original color before the flood fill is applied.
// FloodFill (345,345,RGB(0,0,255),325,300,TRUE)     // Preview mode can be called even if one or more optional parameters are omitted.
//  -----------------------------

// ----------------        FloodFill      -----------------------------------
// Adapted from Fuzzies excellent FastFloodFill code from
// October of 2012, by Craig Waterman.
// ---------------------------------------------------------------------------
FUNCTION FloodFill: Pix_Num_X,Pix_Num_Y,fillcol%,screenx%=-1,screeny%=-1,width%=-1,height%=-1,Preview%=FALSE
// Pix_Num_X, Pix_Num_Y This the starting point to flood within the captured area of screen.
//                      These numbers are in relation to the sprite of the captured area, not the location of the pixel on the screen itself.
// fillcol              This is the fill color Floodfill will use to flood. The fill covers all pixels within the captured area which share the original color of
//                      the starting pix_num, and is limited by the edges of the captured area contained in the sprite, and will not cover other colors
//                      or jump lines across the captured area which have some other color.
// screenx,screeny      This is the optional starting x,y for the screen area capture. If no x,y is given, the default is (0,0), the upper left corner of the screen.
// width, height        This is the optional width and length of the screen capture. If no width or height is given, the ending screensize values are used, which is the lower right corner of the screen.
// Preview         When the optional Preview parameter is set for TRUE, the captured screen area is displayed against a grid background;
//                      and the selected starting pixel is set to black, unless the background is already black in which case it is set to white.
//                      As a single pixel is very small and hard to see, so you will have to look very closely to spot it.
//                       (Note: If Preview mode is used, ALL optional parameters must be used.)
//                      This mode is intended for programer use to check his or her screen capture area.
// ---------------------------------------------------------------------------------------------------------------------------------------
LOCAL sw,sh

// If default values are present, set them based on the screen size.

IF screenx < 2 THEN screenx=0
IF screeny < 2 THEN screeny = 0
IF width < 2 THEN width = sw-screenx
IF height < 2 THEN height = sh-screeny

// Errorcheck to avoid overrunning the limits of the screen
IF screenx+width > sw THEN width = sw-screenx
IF screeny+height > sh THEN height = sh-screeny

GRABSPRITE id%,screenx,screeny,width,height 

IF Preview = TRUE

LOCAL PixHold%

DRW_Grid() // Draws a gridwork on the background so the captured section of screen is easy to recognize.
DRAWSPRITE id,screenx,screeny

// Now we display the starting pixel in either black or white, depending on the background.

PixHold = GETPIXEL (screenx+Pix_Num_X,screeny+Pix_Num_Y)
IF PixHold = RGB(0,0,0)
SETPIXEL screenx+Pix_Num_X,screeny+Pix_Num_Y, RGB(255,255,255)
SETPIXEL screenx+Pix_Num_X,screeny+Pix_Num_Y, RGB(1,1,1)
SETPIXEL screenx+Pix_Num_X,screeny+Pix_Num_Y,PixHold // Here we restore the original color of the starting pixel for the flood fill to work on.


TYPE Fillpixel

GLOBAL pixels%[]

LOCAL i[]  AS Fillpixel
LOCAL newi AS Fillpixel
LOCAL newx%,newy%,dir%
LOCAL fillover%,fillcolour%
LOCAL fillmap%[]
LOCAL red%,green%,blue%,alpha%

IF Pix_Num_X<0 OR Pix_Num_Y<0 OR Pix_Num_X>=width% OR Pix_Num_Y>=height
DEBUG "Out of area."

SPRITE2MEM (pixels[],id)

// Convert the fill colour to SPRITEMEM format.
fillcolour=bOR(fillcol, ASL(255, 24))

// Get the colour that will be filled over.
red=bAND(pixels[Pix_Num_X+Pix_Num_Y*width%], 0xff)
green=bAND(ASR(pixels[Pix_Num_X+Pix_Num_Y*width%],8), 0xff)
blue=bAND(ASR(pixels[Pix_Num_X+Pix_Num_Y*width%],16), 0xff)
alpha=bAND(ASR(pixels[Pix_Num_X+Pix_Num_Y*width%],24), 0xff)
fillover=bOR(RGB(red,green,blue), ASL(alpha, 24))

// If the fill pixel is same colour as then abort.
IF fillover=fillcolour THEN RETURN

// CLEARSCREEN;PRINT fillover+" "+fillcolour,50,50;SHOWSCREEN;KEYWAIT;END

// Set the start position.
DIMPUSH i[],newi

// Reset the fill check map.
DIM fillmap[width%][height]

FOREACH pixel IN i[]

// New test position based on the direction.
FOR dir=0 TO 3


CASE 0 // Right
CASE 1 // Down
CASE 2 // Left
CASE 3 // Up

IF newx>=0 AND newy>=0 AND newx<width% AND newy<height // Make sure the new position is in the boundaries of the screen/sprite.
IF fillmap[newx][newy]=0 // If not already checked continue
fillmap[newx][newy]=1 // Flag this pixel as now checked
IF pixels[newx+newy*width%]=fillover // Check pixel colour is the correct fill over colour.
pixels[newx+newy*width%]=fillcolour // Fill and make a new pixel.
DIMPUSH i[],newi
DELETE pixel // Remove pixel from list
MEM2SPRITE (pixels[],id,width%,height)

DIM fillmap[0][0]

// ------------------------------------------------------------- //
// ---  DRW_Grid  --- // Just Some Interesting Wallpaper.
// ------------------------------------------------------------- //

// Red Grid Lines, for lay out. ///////////
CONSTANT RED% = RGB(255,0,0),GREY% = RGB(100,100,100)
LOCAL sw%,sh%
LOCAL cnt%,sw_Inc% = sw/32,sh_Inc%=sh/32
FOR cnt = -16 TO 16
DRAWLINE sw/2-sw_Inc*cnt,0,sw/2-sw_Inc*cnt,sh,GREY
DRAWLINE 0,sh/2-sh_Inc*cnt,sw,sh/2-sh_Inc*cnt,GREY

DRAWLINE sw/2,0,sw/2,sh,RED
DRAWLINE 0,sh/2,sw,sh/2,RED

--- End code ---

I do get the feeling you guys have something really special going on here.
Altough I donĀ“t have an immediate use for such, somehow I think this could be usefull on a free-drawn- screen-> compile-sprite-block situation.

That situation is something I think about a maybe future project.
Thanks for sharing the knowledge! :good:

I am using it for my Hexboard engine. Here is a snapshot of a board captured in mid draw. Each hex has a color assigned to it, so each hex must be flood-filled individually. Working on small screen sections the size of one hex is much faster than filling a single hex on an area the size of the entire screen. This is what motivated me to revise Fuzzy's original program.


[0] Message Index

[#] Next page

[*] Previous page

Go to full version