Maury Markowitz Posted May 4, 2018 Share Posted May 4, 2018 An interesting thread has started over on the retrocomputing SO board: https://retrocomputing.stackexchange.com/questions/2998/what-implementations-of-basic-had-a-robust-flood-fill-operator Is anyone willing to try this on their Atari? The second post, for the Amstrad, should port fairly directly. Quote Link to comment Share on other sites More sharing options...
JamesD Posted May 4, 2018 Share Posted May 4, 2018 An interesting thread has started over on the retrocomputing SO board: https://retrocomputing.stackexchange.com/questions/2998/what-implementations-of-basic-had-a-robust-flood-fill-operator Is anyone willing to try this on their Atari? The second post, for the Amstrad, should port fairly directly. I think the first BASIC to include a flood fill that was built in, was Extended Color BASIC on the CoCo. I remember running out of mem when doing a flood fill on a screen with a spiral pattern. Most flood fills use the stack for temporary storage, and the BASIC stack is usually pretty small. That could be an even bigger problem on the 6502. Quote Link to comment Share on other sites More sharing options...
tebe Posted May 4, 2018 Share Posted May 4, 2018 (edited) mad pascal/lib/graph.inc procedure FloodFill(a,b: smallint; newcolor: byte); //---------------------------------------------------------------------------------------------- // Fill an area with a given color, seed fill algorithm //---------------------------------------------------------------------------------------------- var ir, nf: word; c: cardinal; oldcolor: byte; FloodFillStack: array [0..0] of cardinal; procedure FloodFillExec; var i: byte; xr,yr: smallint; yes: Boolean; begin for i:=0 to 3 do begin case i of 0: begin xr:=a+1; yr:=b; yes:=(xr<smallint(ScreenWidth)); end; 1: begin xr:=a-1; // yr:=b; yes:=(xr>=0); end; 2: begin xr:=a; yr:=b+1; yes:=(yr<smallint(ScreenHeight)); end; 3: begin // xr:=a; yr:=b-1; yes:=(yr>=0); end; end; if yes then if GetPixel(xr,yr) = oldcolor then begin PutPixel(xr, yr); inc(nf); FloodFillStack[nf]:= word(xr) shl 16 + word(yr); end; end; end; begin FloodFillStack:=pointer(dpeek(560)-2048); SetColor(newcolor); oldcolor:=GetPixel(a,b); nf := 1; ir := 1; FloodFillStack[nf] := word(a) shl 16 + word(b); FloodFillExec; while nf>ir do begin inc(ir); c:=FloodFillStack[ir]; a := hi(c); b := lo(c); FloodFillExec; if (nf>500) then begin nf := nf-ir; if nf>500 then exit; move(FloodFillStack[ir+1], FloodFillStack[1], nf shl 2); // for i := 1 to nf do fill[i] := fill[ir+i]; ir := 0; end; end; end; the same code i used in Atari Graphics Studio (AGS) Edited May 4, 2018 by tebe 2 1 Quote Link to comment Share on other sites More sharing options...
dmsc Posted May 4, 2018 Share Posted May 4, 2018 Hi! An interesting thread has started over on the retrocomputing SO board: https://retrocomputing.stackexchange.com/questions/2998/what-implementations-of-basic-had-a-robust-flood-fill-operator Is anyone willing to try this on their Atari? The second post, for the Amstrad, should port fairly directly. All flood-fill algorithms can run out of buffer space if you fill a complex enough area, look at this TurboBasic XL program, converted from the second one in the link: If you run it, it runs out of space at about 75% of completion: TurboBasic XL uses a scan-line fill algorithm, this avoids using too much memory on simpler paths and is faster than naive point at a time algorithms. Fell free to post above program (and the result) over stackexchange.com if you want. 1 Quote Link to comment Share on other sites More sharing options...
Irgendwer Posted May 4, 2018 Share Posted May 4, 2018 void Dye(BYTE x, BYTE y, BYTE color) { static BYTE xStack[FILLSTACKSIZE]; static BYTE yStack[FILLSTACKSIZE]; BYTE stackentry = 1; BOOL spanAbove, spanBelow; BYTE oldColor = Locate(x,y); if (oldColor == color) return; do { while (x > 0 && Locate(x-1,y) == oldColor) --x; spanAbove = spanBelow = false; while(Locate(x,y) == oldColor) { PLOT(x,y,color); //Plot(x, y, color); if (y < (IMAGEHEIGHT-1)) { BYTE belowColor = Locate(x, y+1); if (!spanBelow && belowColor == oldColor) { xStack[stackentry] = x; yStack[stackentry] = y+1; ++stackentry; spanBelow = true; } else if (spanBelow && belowColor != oldColor) spanBelow = false; } if (y > 0) { BYTE aboveColor = Locate(x, y-1); if (!spanAbove && aboveColor == oldColor) { xStack[stackentry] = x; yStack[stackentry] = y-1; ++stackentry; spanAbove = true; } else if (spanAbove && aboveColor != oldColor) spanAbove = false; } ++x; } --stackentry; x = xStack[stackentry]; y = yStack[stackentry]; } while (stackentry); } Guess the game... Quote Link to comment Share on other sites More sharing options...
flashjazzcat Posted May 4, 2018 Share Posted May 4, 2018 Interesting discussion. I remember trying to write a flood-fill in assembler in the early Nineties (I recall eventually giving up). I think it scanned lines and pushed boundaries (above and below the current line) onto a stack as it found them. I never quite decided how to cope with a pattern fill scenario, however, since unless every pixel will filled with the same colour, my algorithm would have failed completely (since - if using a dithered fill - it would have pushed new coordinates onto the stack every other pixel, believing them to be potential new areas to fill). Quote Link to comment Share on other sites More sharing options...
Rybags Posted May 5, 2018 Share Posted May 5, 2018 (edited) I remember Analog magazine had a diamond algorithm fill that I played around with using a more efficient pixel plot routine. It's a somewhat slower algorithm than the flood fill but has the big advantage that the required buffer can be much smaller - IIRC equal to about 4 times the largest possible 45 degree line length for the given mode. I played around with flood fill, don't remember if I only used Basic or did it in assembler. I think it could actually exceed the bitmap data size in extreme cases for the buffer requirement. Found it - Analog #16 from Feb 1984: http://www.atarimania.com/mags/pdf/analog_no_16.pdf The Atarimania magazine PDF is big and annoyingly slow though - found another copy of the article with the program https://web.archive.org/web/20060308092706fw_/http://www.cyberroach.com:80/analog/an16/default.htm ed - that took an eternity to download. Sadly the PDF has pretty poor OCR and the text even when you can select it is full of errors. So, I typed in the listing for 4-way fill assembler routine: ; Fill routine using CIO ; ; CIO equates used ; cio = $e456 iccom = $342 icblen = $348 cgbinr = $07 cpbinr = $0b ; bufa = $cb ; addresses for ind,y bufb = $cd ; addressing for bufc = $cf ; pixel coordinate bufd = $d4 ; storage ; xpos = $55 ; x coordinate see OS ypos = $54 ; y coordinate ; color = $d1 ; color to plot ; ; the following locations can only ; be used temporarily because they ; are reserved for the floating point ; routines. ; colover = $e6 ; color to cover countnew = $e7 ; # new pixels countold = $e8 ; # pixels to test around ; xpstor = $e9 ; store original xpos ypstor = $ea xp = $d6 yp = $d7 tem = $eb ; to store y index ; ; the fill routine uses page 6 ; *=$600 ; or use .org $600 ; pla ; # of args pla ; high byte not used pla ; the color to plot sta color lda $6fe ; bufd address stored sta bufd ; here because of the lda $6ff ; limited free space sta bufd+1 ; in page 0 ; lda #0 sta countnew ; initialization ldy #1 ; one pixel first time lda xpos ; from os sta (bufa),y sta xpstor sta xp ; for the first locate lda ypos ; from os sta (bufb),y sta ypstor sta yp ; for the first locate sty countold ; one pixel jsr locate ; get pixel to cover sta colover cmp color ; itself? bne preloop rts ; if itself quite or get ; infinite loop! ; preloop jsr plot loop lda (bufa),y sta xp ; x for current pixel lda (bufb),y sta yp ; y for current pixel ; loop0 inc xp ; test to right cmp #80 ; rhs limit to screen bcs loop1 jsr locate ; if within screen ; then see if the pixel contains ; the color to be overwritten. ; the locate routine contains ; the compare. ; bne loop1 jsr keep ; plot it and mark it ; for its own test the next time ; through the list of locations. ; loop1 dec xp dec xp lda xp cmp #255 ; check screen lhs beq loop2 jsr locate bne loop2 jsr keep ; loop2 inc xp inc yp ; test below lda yp cmp #80 ; bottom of screen bcs loop3 jsr locate bne loop3 jsr keep ; loop3 dec yp dec yp lda yp cmp #255 beq loop4 jsr locate bne loop4 jsr keep ; loop4 dec countold beq doneloop ; all points done iny ; else do next point jmp loop ; doneloop ldy countnew beq return0 ; if no new points ; in the color to cover remain ; sty countold ; this becomes the ; new # pixels to plot and test ; transfer lda (bufd),y sta (bufb),y lda (bufc),y sta (bufa),y dey bne transfer ; move buffers ldy #1 lda #0 sta countnew ; initialize jmp loop ; begin again ; ; the subroutines ; keep jsr plot ; y reg in tem inc countnew beq return2 ; buffer overflows ldy countnew lda xp ; store the coord sta (bufc),y ; of this pixel lda yp ; for plotting and sta (bufd),y ; testing ldy tem ; recover y reg ; locate jsr pos lda #cgbinr sta iccom,x jsr cio ; cio locate ldy tem cmp colover ; pixel in a reg. rts ; pos sty tem lda xp sta xpos ; position x lda yp sta ypos ; and y ldx #$60 ; to use in locate lda #0 ; and in plot sta icblen,x ; one pixel as sta icblen+1,x ; in accum. rts ; plot jsr pos lda #cpbinr sta iccom,x lda color ; the one to plot jsr cio ldy tem rts ; return0 lda ypstor sta ypos lda xpstor sta xpos rts ; return2 jsr return0 pla ; we exited a subroutine pla ; so pop return address rts ; to basic ; Edited May 5, 2018 by Rybags Quote Link to comment Share on other sites More sharing options...
tebe Posted May 6, 2018 Share Posted May 6, 2018 (edited) thx Irgendwer for the example 'fill by horizontal line' fill_test_1 -> horizontal fill_test_2 -> diamond 'Diamond' algorithm is more efficient then 'Horizontal Line' floodfill_test.zip floodfill_color.zip Edited May 6, 2018 by tebe 1 Quote Link to comment Share on other sites More sharing options...
Irgendwer Posted May 6, 2018 Share Posted May 6, 2018 (edited) thx for the comparison 'Diamond' algorithm is more efficient then 'Horizontal Line' Not really. I used the single plot since the speed was fast enough for my game and I liked to have a traceable way of filling for the user so decided against "high-speed". The advantage of the horizontal line is, that you normally estimate a span for filling and draw then the complete horizontal span, which is way faster than plotting single pixels. Drawing diagonal lines involves more calculations... Edit: And you second (color) example runs even faster in horizontal mode anyway? (while your first gives an obvious advantage due to the more "diagonal-base-pattern"?) Edited May 6, 2018 by Irgendwer Quote Link to comment Share on other sites More sharing options...
+CharlieChaplin Posted May 6, 2018 Share Posted May 6, 2018 Hmmm, my children once tested a flood fill mode in the bathroom by opening the water tap... think it used a horizontal line... and the parents were not happy ! 6 Quote Link to comment Share on other sites More sharing options...
Irgendwer Posted October 18, 2018 Share Posted October 18, 2018 Just to prevent unsuccessful tries using the code I posted above, here is a correction: http://atariage.com/forums/topic/284075-anybody-have-a-good-flood-fill-code-snippet/?do=findComment&comment=4136733 2 Quote Link to comment Share on other sites More sharing options...
tebe Posted October 19, 2018 Share Posted October 19, 2018 (edited) stack array 2048 bytes procedure FloodFill(a,b: smallint; newcolor: byte); //---------------------------------------------------------------------------------------------- // Fill an area with a given color, seed fill algorithm //---------------------------------------------------------------------------------------------- const FILLSTACKSIZE = 512; var stackPointer, stackEntry: word; c: cardinal; oldcolor: byte; FloodFillStack: array [0..FILLSTACKSIZE-1] of cardinal; procedure FloodFillExec; var i: byte; xr,yr: smallint; yes: Boolean; begin for i:=0 to 3 do begin case i of 0: begin xr:=a+1; yr:=b; yes:=(xr < ScreenWidth); end; 1: begin xr:=a-1; // yr:=b; yes:=(xr >= 0); end; 2: begin xr:=a; yr:=b+1; yes:=(yr < ScreenHeight); end; 3: begin // xr:=a; yr:=b-1; yes:=(yr >= 0); end; end; if yes then if GetPixel(xr,yr) = oldcolor then begin PutPixel(xr, yr); inc(stackEntry); FloodFillStack[stackEntry]:= word(xr) shl 16 + word(yr); end; end; end; begin SetColor(newcolor); oldcolor:=GetPixel(a,b); stackEntry := 1; stackPointer := 1; FloodFillStack[stackEntry] := word(a) shl 16 + word(b); FloodFillExec; while stackEntry > stackPointer do begin inc(stackPointer); c:=FloodFillStack[stackPointer]; a := hi(c); b := lo(c); FloodFillExec; if (stackEntry > FILLSTACKSIZE shr 1) then begin stackEntry := stackEntry - stackPointer; if stackEntry > FILLSTACKSIZE shr 1 then exit; move(FloodFillStack[stackPointer+1], FloodFillStack[1], stackEntry shl 2); stackPointer := 0; end; end; end; stack array 8192 bytes procedure Dye(x,y: smallint; color: byte); var xStack, yStack: array [0..4095] of smallint; stackEntry: word; spanAbove, spanBelow: Boolean; oldColor, belowColor, aboveColor: byte; begin oldColor := GetPixel(x,y); if (oldColor = color) then exit; SetColor(color); stackEntry := 1; repeat while (x > 0) and (GetPixel(x-1,y) = oldColor) do dec(x); spanAbove := false; spanBelow := false; while (x < ScreenWidth) and (GetPixel(x,y) = oldColor) do begin PutPixel(x,y); if (y < smallint(ScreenHeight-1)) then begin belowColor := GetPixel(x, y+1); if (spanBelow=false) and (belowColor = oldColor) then begin xStack[stackEntry] := x; yStack[stackEntry] := y+1; inc(stackEntry); if stackEntry > sizeof(xStack) then exit; spanBelow := true; end else if (spanBelow=true) and (belowColor <> oldColor) then spanBelow := false; end; if (y > 0) then begin aboveColor := GetPixel(x, y-1); if (spanAbove=false) and (aboveColor = oldColor) then begin xStack[stackEntry] := x; yStack[stackEntry] := y-1; inc(stackEntry); if stackEntry > sizeof(xStack) then exit; spanAbove := true; end else if (spanAbove=true) and (aboveColor <> oldColor) then spanAbove := false; end; inc(x); end; dec(stackEntry); x := xStack[stackEntry]; y := yStack[stackEntry]; until stackentry=0; end; test is failed if stack array is smallerfloodfill_test2.zip Edited October 19, 2018 by tebe Quote Link to comment Share on other sites More sharing options...
Irgendwer Posted October 19, 2018 Share Posted October 19, 2018 (edited) test is failed if stack array is smaller * there was never any doubt that the diamond algorithm memory usage is more conservative * you spoil 512 bytes for the diamond fill and 2048 for the scan line one, so the numbers are more or less 1,5k vs. 6k * your synthetic test fits better to the diamond fill, anyhow the scan line one is a bit faster: approx: 5:34 vs. 5:25 * changing (like suggested) to draw lines for the fill (attached), you get the following numbers: 5:34 vs. 4:30 (even I do not know how well the madpascal line function is optimized for horizontal lines and the test case is again very badly suited for horizontal spans) * I'm not participating in a contest - I still have problems what are you trying to demonstrate. That the madpascal flood-fill is superior? Depends on the time-constraints. (Maybe the usual trade memory vs. speed story?) * I even may change a future version of "dye" to use the diamond fill, not because it uses less memory (enough there - and for the images in the game a page of stack is sufficient), but for "entertainment" purposes: I find the process of the filling more attractive and like said, speed doesn't matter in this case. Have fun! fill_test_1.zip Edited October 19, 2018 by Irgendwer 1 Quote Link to comment Share on other sites More sharing options...
tebe Posted October 19, 2018 Share Posted October 19, 2018 (edited) it's not contest, i search more efficient solution (speed, size of code, size of array), and i learn with you Edited October 19, 2018 by tebe 1 Quote Link to comment Share on other sites More sharing options...
Irgendwer Posted October 19, 2018 Share Posted October 19, 2018 it's not contest, i search more efficient solution (speed, size of code, size of array), and i learn with you Regarding your skills and output I doubt that you can learn very much from me... Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.