RetroBASIC

Retrogamecoding(.org) => Examples => Topic started by: Cybermonkey on January 12, 2013, 04:44:26 PM

Title: Flood-fill
Post by: Cybermonkey on January 12, 2013, 04:44:26 PM

Any idea how to implement a simple flood-fill algorithm in EGSL?  :P

Title: Re: Flood-fill
Post by: Mopz on January 12, 2013, 06:55:29 PM

I'm lousy at EGSL, but the principle of a rather inefficient flood fill is simple. pseudo:

Code: [Select]

Procedure floodfill(x, y, bgcolor, pencolor)
   If color(x, y) = bgcolor
      Set color x, y, pencolor
      floodfill(x + 1, y, bgcolor, pencolor)
      floodfill(x - 1, y, bgcolor, pencolor)
      floodfill(x, y + 1, bgcolor, pencolor)
      floodfill(x, y - 1, bgcolor, pencolor)
   Endif
Endproc

floodfill(x, y, color(x, y), pencolor)

There are better algorithms (there are no worse), so if someone figures one out or finds it somewhere it'd be fun to see it :)

Title: Re: Flood-fill
Post by: Mopz on January 12, 2013, 07:17:43 PM

You asked for EGSL code, not NaaLaa, but I checked the pseudo code in NaaLaa and atleast it works:

Code: [Select]

set redraw off

for i = 0 to 100
draw line rnd(640), rnd(480), rnd(640), rnd(480)
next

set caret 320, 0
set color 255, 255, 0
center "Click to make a flood fill"

do
redraw
wait mousebutton
x = mousex()
y = mousey()

set color 255, 255, 0
proc floodfill x, y, pixeli(x, y)
loop

procedure floodfill(x, y, bgcolor)
if x < 0 or x >= 640 then return
if y < 0 or y >= 480 then return

if pixeli(x, y) = bgcolor
set pixel x, y
proc floodfill x + 1, y, bgcolor
proc floodfill x - 1, y, bgcolor
proc floodfill x, y + 1, bgcolor
proc floodfill x, y - 1, bgcolor
endif
endproc
However, you better not click in areas that are too large, because then the program crashes because of a "stack overflow" ;)

Title: Re: Flood-fill
Post by: Mopz on January 12, 2013, 07:32:31 PM

Added another rather clumbsy thing that doesn't use recursion for the horizontal fills, floodfill2:

Code: [Select]

set redraw off

for i = 0 to 100
draw line rnd(640), rnd(480), rnd(640), rnd(480)
next

set caret 320, 0
set color 255, 255, 0
center "Click to make a flood fill"

do
redraw
wait mousebutton
x = mousex()
y = mousey()

set color 255, 255, 0
proc floodfill2 x, y, pixeli(x, y)
loop

procedure floodfill(x, y, bgcolor)
if x < 0 or x >= 640 then return
if y < 0 or y >= 480 then return
if pixeli(x, y) = bgcolor
set pixel x, y
proc floodfill x + 1, y, bgcolor
proc floodfill x - 1, y, bgcolor
proc floodfill x, y + 1, bgcolor
proc floodfill x, y - 1, bgcolor
endif
endproc

procedure floodfill2(x, y, bgcolor)
if x < 0 or x >= 640 then return
if y < 0 or y >= 480 then return
if pixeli(x, y) = bgcolor
xstart = x
xend = x
while xstart >= 0 and pixeli(xstart, y) = bgcolor
xstart = xstart - 1
wend
xstart = xstart + 1
while xend < 640 and pixeli(xend, y) = bgcolor
xend = xend + 1
wend
xend = xend - 1
for xx = xstart to xend
set pixel xx, y
next
for xx = xstart to xend
proc floodfill2 xx, y - 1, bgcolor
proc floodfill2 xx, y + 1, bgcolor
next
endif
endproc
It still recurses like hell, but atleast it works better on the larger areas.

Title: Re: Flood-fill
Post by: Cybermonkey on January 12, 2013, 08:43:40 PM

Ok, thanks. I will try to port this to EGSL, at least the first example looks simple enough.
Here's the first example the EGSL way  ;) :
(And yes, big areas cause a stack overflow ... trying to port the second one)

Code: [Select]

function floodfill (x,y,bgr,bgg,bgb,penr,peng,penb)
  if (screenred (x,y) == bgr) and (screengreen (x,y) == bgg) and (screenblue (x,y) == bgb) then
     colour (penr,peng,penb)
     dot (x,y)
     floodfill (x+1,y,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x-1,y,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x,y+1,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x,y-1,bgr,bgg,bgb,penr,peng,penb)
  end
end


screen (800,600,0,"FloodFill")
backcolour (200,200,200)
cls()
colour (0,0,100)
circle (400,300,150)
sync()
inkey()
floodfill (420,320,200,200,200,250,250,0)
sync()
inkey()
closewindow()
It draws a circle and waits for a keypress and then fills that circle.

Title: Re: Flood-fill
Post by: Cybermonkey on January 12, 2013, 09:00:35 PM

Still the first one with mouse "draw":

Code: [Select]

function floodfill (x,y,bgr,bgg,bgb,penr,peng,penb)
  if (screenred (x,y) == bgr) and (screengreen (x,y) == bgg) and (screenblue (x,y) == bgb) then
     colour (penr,peng,penb)
     dot (x,y)
     floodfill (x+1,y,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x-1,y,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x,y+1,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x,y-1,bgr,bgg,bgb,penr,peng,penb)
  end
end


screen (800,600,0,"FloodFill")
backcolour (200,200,200)
cls()
colour (0,0,100)
for i=1,20 do
circle (int(rnd()*800)+1,int(rnd()*600)+1,int (rnd()*150))
end
sync()
repeat
key=getkey()
mx =mousex()
my=mousey()
if mouseb()==1 then
   floodfill (mx,my,200,200,200,250,250,0)
end
sync()
until key == 27
closewindow()


Title: Re: Flood-fill
Post by: Cybermonkey on January 12, 2013, 09:18:40 PM

Yep, it works!! Thanx Mopz, again a complicated topic easy done by you.
Both versions are inside the code, I think we can recommend the floodfill2 ...

Code: [Select]

function floodfill (x,y,bgr,bgg,bgb,penr,peng,penb)
   if x < 0 or x >= screenwidth() then
      return
   end
  if y < 0 or y >= screenheight() then
     return
  end

  if (screenred (x,y) == bgr) and (screengreen (x,y) == bgg) and (screenblue (x,y) == bgb) then
     colour (penr,peng,penb)
     dot (x,y)
     floodfill (x+1,y,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x-1,y,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x,y+1,bgr,bgg,bgb,penr,peng,penb)
     floodfill (x,y-1,bgr,bgg,bgb,penr,peng,penb)
  end
end

function floodfill2 (x,y,bgr,bgg,bgb,penr,peng,penb)
   if x < 0 or x >= screenwidth() then
      return
   end
  if y < 0 or y >= screenheight() then
     return
  end
  if (screenred (x,y) == bgr) and (screengreen (x,y) == bgg) and (screenblue (x,y) == bgb) then
xstart = x
xend = x
while xstart >= 0 and  (screenred (xstart,y) == bgr) and (screengreen (xstart,y) == bgg) and (screenblue (xstart,y) == bgb) do
xstart = xstart - 1
end
xstart = xstart + 1
while xend < screenwidth() and  (screenred (xend,y) == bgr) and (screengreen (xend,y) == bgg) and (screenblue (xend,y) == bgb) do
xend = xend + 1
end
xend = xend - 1
for xx = xstart , xend do
                        colour (penr,peng,penb)
                        dot (xx,y)

end
for xx = xstart , xend do
floodfill2 (xx, y - 1,bgr,bgg,bgb,penr,peng,penb)
floodfill2 (xx, y + 1,bgr,bgg,bgb,penr,peng,penb)
end
end
end

screen (800,600,0,"FloodFill")
backcolour (200,200,200)
cls()
colour (0,0,100)

for i=1,30 do
    circle (int(rnd()*800)+1,int(rnd()*600)+1,int (rnd()*250))
end
sync()

repeat
key=getkey()
mx =mousex()
my=mousey()
if mouseb()==1 then
   floodfill2 (mx,my,200,200,200,250,250,0)
end
if mouseb()==4 then
   floodfill2 (mx,my,200,200,200,250,0,0)
end
sync()
until key == 27
closewindow()

Can we call it "art"?  ;D

Title: Re: Flood-fill
Post by: Mopz on January 13, 2013, 08:41:19 AM

No problems, and it does look like art to me  :)