GLBasic forum

Codesnippets => 2D-snippets => Topic started by: fuzzy70 on 2012-Oct-31

Title: Very fast floodfill
Post by: fuzzy70 on 2012-Oct-31
No idea what site the algorithm came from but found it as a text file on my HD, all I do know was it was a very long time ago so I just converted the pseudo code into a GLB function using types & MEM2SPRITE etc.

I made it so it can be used for floodfills on a whole screen or just a sprite & even on my lowly system its very very quick (millsecs rather than seconds  =D )

Lee

Code (glbasic) Select

// --------------------------------- //
// Project: fastfloodfill
// Start: Wednesday, October 31, 2012
// IDE Version: 10.283


// FREE-VERSION:
// Need Premium for Features:
// 3D Graphics
// Network Commands
// INLINE C/C+++ code

SETCURRENTDIR("Media") // go to media files
SETSCREEN 800,600,0
SYSTEMPOINTER TRUE
SEEDRND GETTIMERALL()

TYPE Fillpixel
x%
y%
ENDTYPE

GLOBAL pixels%[]

LOCAL mx%,my%,b1%,b2%,col%,sx%,sy%

GETSCREENSIZE sx,sy

LOADSPRITE "grab.png",0 // Load an image as CBA to write a filled circle function at present to test non-square borders ;)
//GRABSPRITE 0,0,0,sx,sy
REPEAT
MOUSESTATE mx, my, b1, b2
IF MOUSEAXIS(3)
col = RGB(255,255,255)
FillFast(mx,my,sx,sy,col,0)
ENDIF
DRAWSPRITE 0,0,0
SHOWSCREEN
UNTIL KEY(57)
END


FUNCTION FillFast: startx%,starty%,width%,height%,fillcol%,id%

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

IF startx<0 OR starty<0 OR startx>=width% OR starty>=height
DEBUG "Out of area."
RETURN
        ENDIF

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[startx+starty*width%], 0xff)
green=bAND(ASR(pixels[startx+starty*width%],8), 0xff)
blue=bAND(ASR(pixels[startx+starty*width%],16), 0xff)
alpha=bAND(ASR(pixels[startx+starty*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

// Set the start position.
newi.x=startx
newi.y=starty
pixels[startx+starty*width%]=fillcolour
DIMPUSH i[],newi

// Reset the fill check map.
DIM fillmap[width%][height]
fillmap[startx][starty]=1

FOREACH pixel IN i[]

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

SELECT dir

CASE 0 // Right
newx=pixel.x+1
newy=pixel.y
CASE 1 // Down
newx=pixel.x
newy=pixel.y+1
CASE 2 // Left
newx=pixel.x-1
newy=pixel.y
CASE 3 // Up
newx=pixel.x
newy=pixel.y-1
ENDSELECT


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.
newi.x=newx
newi.y=newy
DIMPUSH i[],newi
ENDIF
ENDIF
ENDIF
NEXT
DELETE pixel // Remove pixel from list
NEXT

MEM2SPRITE (pixels[],id,width%,height)

DIM fillmap[0][0]
ENDFUNCTION
   

[attachment deleted by admin]
Title: Re: Very fast floodfill
Post by: Hemlos on 2012-Oct-31
very awesome, love it..

to use this with other size images you need to use this:

GETSPRITESIZE 0,sx,sy
Title: Re: Very fast floodfill
Post by: fuzzy70 on 2012-Oct-31
Originally I just made it for full screen fills then decided to add a width & height parameters to the function to give it a bit more flexibility.

Glad you like it :)).

Next step is gradient fills but don't hold your breath lol

Lee

Sent from my GT-I5700 using Tapatalk 2

Title: Re: Very fast floodfill
Post by: Hemlos on 2012-Oct-31
Cool stuff  :good:

The reason you need to use the sprite size is because the program will crash if the sprite is smaller than the screensize.

Perhaps theres is another solution you can work into the original algorithm.
Title: Re: Very fast floodfill
Post by: fuzzy70 on 2012-Oct-31
I think the algorithm is not a problem, perhaps more checks in the function for sizes passed to it or similar may be required.

Will play around later when back home.

Lee

Btw thanks for moving it to the correct location ^-^
Sent from my GT-I5700 using Tapatalk 2
Title: Re: Very fast floodfill
Post by: fuzzy70 on 2012-Nov-01
I think I have addressed the crashing problem, the code that checks if it is in bounds
Code (glbasic) Select
IF startx<0 OR starty<0 OR startx>=width% OR starty>=height THEN DEBUG "Out of area."
didn't exit the function if it was passed co-ords that where outside the image, so should read
Code (glbasic) Select
IF startx<0 OR starty<0 OR startx>=width% OR starty>=height
DEBUG "Out of area."
RETURN
ENDIF

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

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.

Lee
Title: Re: Very fast floodfill
Post by: CW on 2013-Apr-10
This flood fill is just what I need for my current project. Thanks a ton, Fuzzy.  :good:
-Science_1
Title: Re: Very fast floodfill
Post by: CW on 2013-Apr-17
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.
-CW
Code (glbasic) Select
SETSCREEN 1000,750,FALSE
CLEARSCREEN

// 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.
//
//  -----------------------------
SHOWSCREEN
KEYWAIT
END
//////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// ----------------        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 id% = GENSPRITE()
LOCAL sw,sh
GETSCREENSIZE 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%

CLEARSCREEN
DRW_Grid() // Draws a gridwork on the background so the captured section of screen is easy to recognize.
ALPHATESTING 1.0
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)
ELSE
SETPIXEL screenx+Pix_Num_X,screeny+Pix_Num_Y, RGB(1,1,1)
ENDIF
SHOWSCREEN; KEYWAIT
ALPHATESTING 0.0
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.

ENDIF

TYPE Fillpixel
x%
y%
ENDTYPE

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."
RETURN
ENDIF

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.
newi.x=Pix_Num_X
newi.y=Pix_Num_Y
pixels[Pix_Num_X+Pix_Num_Y*width%]=fillcolour
DIMPUSH i[],newi

// Reset the fill check map.
DIM fillmap[width%][height]
fillmap[Pix_Num_X][Pix_Num_Y]=1

FOREACH pixel IN i[]

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

SELECT dir

CASE 0 // Right
newx=pixel.x+1
newy=pixel.y
CASE 1 // Down
newx=pixel.x
newy=pixel.y+1
CASE 2 // Left
newx=pixel.x-1
newy=pixel.y
CASE 3 // Up
newx=pixel.x
newy=pixel.y-1
ENDSELECT


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.
newi.x=newx
newi.y=newy
DIMPUSH i[],newi
ENDIF
ENDIF
ENDIF
NEXT
DELETE pixel // Remove pixel from list
NEXT
//
MEM2SPRITE (pixels[],id,width%,height)
DRAWSPRITE id,screenx,screeny//;USEASBMP;SHOWSCREEN;KEYWAIT

DIM fillmap[0][0]
RETURN id

ENDFUNCTION
// ------------------------------------------------------------- //
// ---  DRW_Grid  --- // Just Some Interesting Wallpaper.
// ------------------------------------------------------------- //
FUNCTION DRW_Grid:

// Red Grid Lines, for lay out. ///////////
CONSTANT RED% = RGB(255,0,0),GREY% = RGB(100,100,100)
LOCAL sw%,sh%
GETSCREENSIZE 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
NEXT

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

ENDFUNCTION // DRW_Grid

Title: Re: Very fast floodfill
Post by: erico on 2013-Apr-17
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:
Title: Re: Very fast floodfill
Post by: CW on 2013-Apr-17
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.
:)
-CW
Title: Re: Very fast floodfill
Post by: fuzzy70 on 2013-Apr-17
Glad you found a good use for the routine CW & thanks for the improvements

Lee

Sent from my HTC Wildfire using Tapatalk 2

Title: Re: Very fast floodfill
Post by: CW on 2013-Apr-17
Thanks Lee.  :)

P.S. I fixed a minor bug in Preview mode on 04/17/13, and updated the function listing above.
Title: Re: Very fast floodfill
Post by: erico on 2013-Apr-17
That hex board looks really great! :good:
Title: Re: Very fast floodfill
Post by: Brick Redux on 2013-Apr-24
Brilliant!
Title: Re: Very fast floodfill
Post by: erico on 2013-Apr-24
heey brick! back again uh!

Hope all that mailing cd went ok and that you are all fine!
Welcome again! :good:
Title: Re: Very fast floodfill
Post by: fuzzy70 on 2013-Apr-24
Welcome back Brick  :booze:

Lee
Title: Re: Very fast floodfill
Post by: Brick Redux on 2013-Apr-25
Cheers Lee & keep up the good work.
Title: Re: Very fast floodfill
Post by: Brick Redux on 2013-Jul-28
Ive cracked the pattern fill and its very quick.  Its now part of of my Sprite Editor re-write.  Coming soon folks.
Title: Re: Very fast floodfill
Post by: Brick Redux on 2013-Jul-28
Quote from: erico on 2013-Apr-24
heey brick! back again uh!

Hope all that mailing cd went ok and that you are all fine!
Welcome again! :good:

Sorry Erico, I never noticed your reply unitl now - tut-tut - Yes, all is good, back coding with this excellent basic.  Post more of your work buddy.
Title: Re: Very fast floodfill
Post by: Brick Redux on 2013-Aug-30
In my Sprite Editor I found this way to use a sprite/brush as a pattern fill.

First fill the selected area with the set transparent colour.
Copy the selected area to a virtual screen.
Grab it as a Sprite.
Save the Sprite. (only way to later recognise the transparency)
Draw the Pattern in columns & rows inside the virtual screen.
Load the Sprite and draw it over the Pattern.
Copy back to the main screen.

I dunno how this would work with full screen, but it works like a dream in my editor.

Hope it helps anyone exploring this.
Title: Re: Very fast floodfill
Post by: erico on 2013-Aug-30
Nice it works fine. :good:

There was a discussion about alpha sometime ago based on Ian Price´s game "Aquaventure" (go play it, it is wonderful!).
We all gave a go on sorting the alpha thing, it was really a nightmare.

I wonder if your solution could eventually be used on that case and it is fast enough to keep the game up at good speed.
The thread is here:
http://www.glbasic.com/forum/index.php?topic=8906.0

Makes for a good reading...except for the part I said my game is almost done :-[ I added a lot of stuff to it after that and more then 6 months later I´m still on the same stage! (but the added stuff looks great at least :P)
Title: Re: Very fast floodfill
Post by: erico on 2013-Aug-30
About your sprite editor, it would wonderful if it also works on the likes of android or even a caanoo.
Since I got a note II I have been looking for productive tools on this front and alas there are none good enough... :(

Grafx2 may work ok but it is really hard to make it work and it dosen´t read the wacom pen on note II on a fine way, so it is actually useless.
I found a few sound/music programs that are more or less ok.
But I can state that android lacks productive tools to the point that if I had time I would code my own tools.

People may not work on phones, but the note II or bigger tablets are well capable to handle fine art and music for retro games.
Heck, when I´m travelling, time would be well spent drawing game assets on them. :(
I can do some of that stuff on my caanoo that the note II can´t handle at all.

I dream of a pixel sprite editor capable of handling animations and onion skin, it would be a dream come true if such appears on mobiles and tablets.

The best tool so far I found for it is Dr. Pepper´s "Cherry Brush"
http://www.drpetter.se/projects.html

Post a peep on your sprite editor when you can, I would like to see it.
Cheers.
Title: Re: Very fast floodfill
Post by: fuzzy70 on 2013-Aug-30
Thanks for bringing my attention back to this routine of mine as I accidentally overwrote my newer version with an older one when I changed computers (along with a few others as well  :D ). Luckily nothing of great importance was lost as most where just experiments & proof of concept type things.

The way I done a pattern fill from what I recall was just SPRITE2MEM the pattern to use as the fill & a little bit of maths to convert the current fill position to the appropriate array position of the pattern, taking into account pattern size & repeating obviously.

When I have finished my current item I will revisit this routine & try to remember how I done it last time. Also started work on gradient fills on the lost version, but only got as far as RGB to HSV conversion with a straight up linear fill I think (angles & radial type etc was the next stage).

Because I have not had a need for a fill routine for quite some time I mainly the reason I forgot all about it  :whip:

Glad you found a solution that works well in your Sprite Ed Brick  :good:

Lee
Title: Re: Very fast floodfill
Post by: Brick Redux on 2013-Aug-30
Quote from: erico on 2013-Aug-30
About your sprite editor, it would wonderful if it also works on the likes of android or even a caanoo.
Since I got a note II I have been looking for productive tools on this front and alas there are none good enough... :(

Grafx2 may work ok but it is really hard to make it work and it dosen´t read the wacom pen on note II on a fine way, so it is actually useless.
I found a few sound/music programs that are more or less ok.
But I can state that android lacks productive tools to the point that if I had time I would code my own tools.

People may not work on phones, but the note II or bigger tablets are well capable to handle fine art and music for retro games.
Heck, when I´m travelling, time would be well spent drawing game assets on them. :(
I can do some of that stuff on my caanoo that the note II can´t handle at all.

I dream of a pixel sprite editor capable of handling animations and onion skin, it would be a dream come true if such appears on mobiles and tablets.

The best tool so far I found for it is Dr. Pepper´s "Cherry Brush"
http://www.drpetter.se/projects.html

Post a peep on your sprite editor when you can, I would like to see it.
Cheers.

Ok Erico, here you go - a sneek peek at my editor.  The leen eyed will notice no save/load/animate etc icons. Thats because i click the tab under the paintbox from 1 to 2 to display the other icons/options.

Title: Re: Very fast floodfill
Post by: Brick Redux on 2013-Aug-31
In the paintbox Ive selected what I call DOT.  You can also see all the nibs / stamps / brushes or what ever you want to call them :)  I added all of them with speed in mind when designing an image - saves messing around having to creating such a thing and then copy it as a brush.

I like GraFX but find the icons along the bottom annoying at times - my younger self still screams at this when reflecting upon DPaint :).
Title: Re: Very fast floodfill
Post by: erico on 2013-Sep-06
Looks awesome! Can´t wait to check it out, speed it up!

While thinking about an editor, I wondered if the brush tool could support pre-made dither as a color.
Like you would have different sets of dither between 2 colors (main and background)possibly controlled by a slider and it would paint that dither.

Just something that sparked on my mind but I hardly think it really necessary.

Cheers!
Title: Re: Very fast floodfill
Post by: Qedo on 2022-Jan-12
Hi everyone,
speed is certainly an important factor in games and I think it will be of interest to an improved and faster version of the "fastfloodfill" project posted at therad https://www.glbasic.com/forum/index.php?topic=8663.msg78051# msg78051.
The complete project that I enclose "FillFastLine" is at least 4-5 times faster on my computer going from 50 fps to 220.
is a GLB version obtained from the site https://lodev.org/cgtutor/floodfill.html.
I hope you enjoy it and look forward to any comments and improvements in the case.
Ciao
Title: Re: Very fast floodfill
Post by: dreamerman on 2022-Jan-14
Very nice code, and may have other usage as well.
I tried to compare it with my basic FloodFill from path finding routines, and Your code is 2 times faster, so I will try to implement this algorithm in path finding in near time. One thing to check would be using full size array and omit DIMPUSH/DIMDEL, it could bring some minor speed improvement but I'm not sure, it's very good in current state.
And in general the algorithm it self is more that 4-5 times faster, just that Sprite2Mem & FastMem2Sprite take some additional time, but even with them it's really fast, and could be used for some special effects in retro project.
Btw. I remember that lodev.org has also great articles about raycasting :)
Title: Re: Very fast floodfill
Post by: SnooPI on 2022-Jan-15
Very interesting. Thanks for sharing Qedo.
Dreamerman, I remember your path finding routine and this could definitely improve it.
Lode Vandevenne is a very good programmer especially for retro coding.
QuickCG (https://lodev.org/quickcg/) is so coOol  :P