Flood Fill Function

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|516\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Off Topic -> Flood Fill Function
Mon, 30 Apr 2018, 11:50
spinal	Does anyone have in their code collection a non-recusive flood fill function? I remember about 20 or so years ago using one that filled an area using a diamond shape, rather than lines and it worked no matter the size of the fill area. Everything I am finding uses a stack of some sort, which I can't do (tiny stack, almost no RAM). Any ideas? -=-=- Check out my excellent homepage!
Mon, 30 Apr 2018, 11:50
Jayenkai	Same as my AI Pathfinding code.. Essentially start from x/y, and grow your loop outward until you ain't drawing no more. Needs a secondary grid to keep track of what's been filled, though. That will probably be an issue! Perhaps if you make secondary use of the pixel-values themselves to keep track of what's been filled? (eg, instead of filling with R,G,B, fill with R+500,G,B. Then after the fill is complete, scan through the whole image and remove the +500) ; BlitzBasic/3D/Plus code ; For the love of god, don't try running it with Debug mode on!! Global jscrw=240 Global jscrh=160 Graphics jscrw4,jscrh4,0,2 Graphics jscrw,jscrh,0,3 SetBuffer BackBuffer() Global grid[25000000] ; Big empty grid! Global scan[25000000] ; Big empty grid! For x=0 To jscrw For y=0 To jscrh grid[(yjscrw)+x]=Rand(0,1) Next Next Repeat DrawGrid() If MouseHit(1) Flood(MouseX(),MouseY(),(grid[(MouseY()jscrw)+MouseX()]+1) Mod 4) EndIf Until KeyHit(1) Function Flood(px,py,col) ; Clear the scan For n=0 To 25000000-1 scan[n]=0 Next fromcol=grid[pyjscrw+px] scan[pyjscrw+px]=1 grid[pyjscrw+px]=col lots=jscrwjscrh none=0 For n=2 To lots ; Start at the point, expand to a decent number of points. any=0 ; Set limits of area to scan. A square of range Center +- n l=px-n If l<0 Then l=0 t=py-n If t<0 Then t=0 r=px+n If r>jscrw-1 Then r=jscrw-1 b=py+n If b>jscrh-1 Then b=jscrh-1 ; Within those limits For x=l To r For y=t To b If grid[yjscrw+x]=fromcol ; Check if the current pixel is still the colour we're filling over. ; And then check if any adjacent pixels have already been changed ; If changed, change this one, too. If x>0 Then If scan[(yjscrw)+(x-1)]=1 Then grid[yjscrw+x]=col:scan[yjscrw+x]=1:any=1 If x<jscrw-1 Then If scan[(yjscrw)+(x+1)]=1 Then grid[yjscrw+x]=col:scan[yjscrw+x]=1:any=1 If y>0 Then If scan[((y-1)jscrw)+(x)]=1 Then grid[yjscrw+x]=col:scan[yjscrw+x]=1:any=1 If y<jscrh-1 Then If scan[((y+1)jscrw)+(x)]=1 Then grid[yjscrw+x]=col:scan[yjscrw+x]=1:any=1 EndIf Next Next If (n Mod 50)=49 Then DrawGrid() ; Draw an update every so often ; If none, say we're done. If any=0 Then none=none+1 If none>2 Then n=lots+1 ; Although we'll double check, to be sure. Next If KeyDown(1) Then End End Function Function DrawGrid() Cls For x=0 To jscrw For y=0 To jscrh Color(0,0,0) If grid[(yjscrw)+x]=1 Then Color(255,255,255) If grid[(yjscrw)+x]=2 Then Color(255,128,0) If grid[(yjscrw)+x]=3 Then Color(0,128,255) Plot(x,y) Next If KeyDown(1) Then End Next Flip End Function --v -=-=- ''Load, Next List!''
Mon, 30 Apr 2018, 12:29
spinal	That might take a lot more thinking.... I'm using a palette based screen, probably with only 4 colours... I was thinking along the lines of path finding, that's part of the reason I was trying to hunt through playmycode, I have a maze generator in there somewhere I think. -=-=- Check out my excellent homepage!
Mon, 30 Apr 2018, 13:48
Pakz	I did a very simple flood fill not that long ago. It was for pathfinding as I added numbers from the initial start growing the further they got away. Because it needed to be simple I just continuously looped the array (for x and y)and looked for the current fill number and filled l/r/u/d with the next number if not set before. No stack. I have it in my appgamekit book. cromdesi.home.xs4all.nl/agkmobile/appgamekitmobiletutorial.pdf
Tue, 01 May 2018, 09:12
Dan	The blitzbasic forum still has few flood fill examples: http://mojolabs.nz/codearcs.php?cat=1&order=&asc=&lang_id=1
Thu, 03 May 2018, 16:58
TomToad	I now present to you a non-recursive, no stack, no extra arrays, 2 bit per pixel fill routine. This was a challenging project here and was actually surprised I got it to work the very first time. The program is written in BlitzMax, hopefully you can convert it to whatever language and platform you are using. That is, if you can understand what I am doing. Since I didn't know the exact format of the image you are using, I decided to make an abstract type which you can extend. You only need to implement the two abstract methods WritePixel and ReadPixel which sets/returns the color index at the x,y coordinates, and you need to set the Width and Height fields to the image's dimentions. The example included with the code shows a way to extend the type for use. The example included is a simple paint program, press left mouse button to draw, right mouse button to fill an area with current color, and the number keys 1-4 to change to one of the four colors. Tried a variety of shapes to fill and haven't gotten it to crash yet. SuperStrict 'This type is the base for a 2 bit, 4 color image. To use, just extend it, ' implement the abstract methods, and add whatever functionality you need to it Type T4ColorImageBase Field width:Int Field height:Int Method ReadPixel:Int(x:Int,y:Int) Abstract Method WritePixel:Int(x:Int,y:Int,Index:Int) Abstract Const North:Int = 0 'define some constants for the floodfill method Const East:Int = 1 Const South:Int = 2 Const West:Int = 3 Const Done:Int = 4 Const Left:Int = -1 Const Straight:Int = 0 Const Right:Int = 1 Const Backup:Int = 2 'This method will fill an area of one color index with another ' StartX and StartY is coordinates for where to start the fill and should ' be within the range of (0,0)-(width-1,height-1). Outside this range ' will return with nothing done. ' Color is the index of the color you will be filling the area with. This ' should be in the range of 0-3. Anything outside this range will be ' mod 4, if the color at (StartX,StartY) is the same as Color, then the ' funtion returns doing nothing Method FloodFill(StartX:Int, StartY:Int, Color:Int) If StartX < 0 Or StartX >= Width Then Return 'Do nothing if pixel out of image If StartY < 0 Or StartY >= Height Then Return Color = Color & 3 'Mod color to 2 bits Local SourceColor:Int = ReadPixel(StartX,StartY) If Color = SourceColor Then Return 'do nothing if colors are the same Local CurrentDirection:Int = North 'This is the direction to check next Local NextX:Int, NextY:Int 'The coordinates of the pixel to check Local x:Int = StartX, y:Int = StartY 'The current pixel coordinates Local Turn:Int = Straight 'The direction to turn Repeat Select (CurrentDirection + Turn) & 3 'calculate the next pixel Case North NextX = x NextY = y-1 Case East nextX = x+1 NextY = y Case South NextX = x NextY = y+1 Case West NextX = x-1 NextY = y End Select 'Test if next pixel is within the image and if it equals the source pixel If NextX >= 0 And NextX < Width And NextY >= 0 And NextY < Height And ReadPixel(NextX,NextY) = SourceColor WritePixel(x,y,(SourceColor+Turn+2) & 3) 'write the turn value into the pixel x = NextX 'update the coordinates y = NextY CurrentDirection = (CurrentDirection + Turn) & 3 'Update the direction of travel Turn = Left 'Point the path to the left Else If x = StartX And y = StartY 'if first pixel, then update direction else update turn CurrentDirection :+ 1 If CurrentDirection = Done 'If we have gone all 4 directions, we're through WritePixel(x,y,Color) Return End If Else Turn :+ 1 If Turn = Backup 'We have tried all directions, so back up to the previous cell WritePixel(x,y,Color) Select CurrentDirection 'previous cell is opposite of current direction Case North y :+ 1 Case East x :- 1 Case South y :- 1 Case West x :+ 1 End Select Turn = ReadPixel(x,y)-2-SourceColor 'Get the turn value stored in the cell If Turn < -1 Then Turn :+ 4 'A sort of shifted mod 3 to bring value to -1 - 1 CurrentDirection = (CurrentDirection - Turn) & 3 'turn opposite direction to get the 'original direction value End If End If End If Forever End Method End Type '-------------------------------------------------------------------------- ' ' Example usage ' Left mouse button to draw ' Right mouse button to flood fill ' Number keys 1-4 to choose color. ' '------------------------------------------------------------------------- 'create our 2 bit per pixel image format and define the ReadPixel and WritePixel methods Type T4ColorImage Extends T4ColorImageBase Field BitMap:Int[] Field Color:Int[] = [$000000,$FF0000,$00FF00,$0000FF] Field RowWidth:Int Function Create:T4ColorImage(Width:Int, Height:Int) Local Image:T4ColorImage = New T4ColorImage Image.Width = Width Image.Height = Height Image.RowWidth = Ceil(Width/16.0) Image.BitMap = New Int[Image.RowWidthHeight] 'make enough room for the bitmap Return Image End Function Method ReadPixel:Int(x:Int,y:Int) If x < 0 Or x >= Width Or y < 0 Or y >= Height Then Return 0 Local RowIndex:Int = y RowWidth Local Index:Int = RowIndex + x / 16 Local PixelGroup:Int = BitMap[Index] Local Pixel:Int = x Mod 16 Local Value:Int = (Pixelgroup & (3 Shl (Pixel2))) Shr (Pixel 2) Return Value End Method Method WritePixel(x:Int,y:Int,Color:Int) If x < 0 Or x >= Width Or y < 0 Or y >= Height Then Return Color :& 3 Local RowIndex:Int = y * RowWidth Local Index:Int = RowIndex + x / 16 Local PixelGroup:Int = BitMap[Index] Local Pixel:Int = x Mod 16 Local Result:Int = (PixelGroup & ~(3 Shl (Pixel2))) \| (Color Shl (Pixel 2)) BitMap[Index] = result End Method Method GetColor:Int(x:Int,y:Int) Return Color[ReadPixel(x,y)] End Method Method line(x1:Int,y1:Int,x2:Int,y2:Int,color:Int) 'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle Local Steep:Int=Abs(Y2-Y1) > Abs(X2-X1) 'Boolean If Steep Local Temp:Int=X1; X1=Y1; Y1=Temp 'Swap X1,Y1 Temp=X2; X2=Y2; Y2=Temp 'Swap X2,Y2 EndIf Local DeltaX:Int=Abs(X2-X1) 'X Difference Local DeltaY:Int=Abs(Y2-Y1) 'Y Difference Local Error:Int=0 'Overflow counter Local DeltaError:Int=DeltaY 'Counter adder Local X:Int=X1 'Start at X1,Y1 Local Y:Int=Y1 Local XStep:Int Local YStep:Int If X1<X2 Then XStep=1 Else XStep=-1 'Direction If Y1<Y2 Then YStep=1 Else YStep=-1 'Direction If Steep Then WritePixel(Y,X,color) Else WritePixel(X,Y,color) 'Draw While X<>X2 X:+XStep 'Move in X Error:+DeltaError 'Add to counter If (Error Shl 1)>DeltaX 'Would it overflow? Y:+YStep 'Move in Y Error=Error-DeltaX 'Overflow/wrap the counter EndIf If Steep Then WritePixel(Y,X,color) Else WritePixel(X,Y,color) 'Draw Wend End Method End Type Graphics 800,600 Local Image:T4ColorImage = T4ColorImage.Create(200,150) Local ColorIndex:Int = 1 Local PixelColor:Int Local PixelImage:TImage = CreateImage(5,5) Local Pixmap:TPixmap = LockImage(PixelImage) Pixmap.ClearPixels($FFFFFFFF) UnlockImage(PixelImage) Local MouseFlag:Int = False Local OldX:Int, OldY:Int While Not KeyHit(KEY_ESCAPE) And Not AppTerminate() Cls For Local x:Int = 0 Until 200 For Local y:Int = 0 Until 150 PixelColor = Image.GetColor(x,y) SetColor PixelColor Shr 16,(PixelColor Shr 8) & $FF, PixelColor & $FF DrawImage PixelImage,x5,y5 Next Next Flip If MouseDown(1) Local mx:Int = MouseX()/5 Local my:Int = MouseY()/5 If MouseFlag If mx <> OldX Or my <> OldY Image.Line(OldX,OldY,mx,my,ColorIndex) End If Else MouseFlag = True Image.WritePixel(mx,my,ColorIndex) End If OldX = mx OldY = my Else MouseFlag = False End If If MouseHit(2) Local x:Int = MouseX()/5 Local y:Int = MouseY()/5 Image.FloodFill(x,y,ColorIndex) End If If KeyHit(KEY_1) Then ColorIndex = 0 If KeyHit(KEY_2) Then ColorIndex = 1 If KeyHit(KEY_3) Then ColorIndex = 2 If KeyHit(KEY_4) Then ColorIndex = 3 Wend --v