I need a fill function

Hi

I have a grid that is based on an array: Grid[8,8]
Its 8x8 grid with block size 32x32.



How do I fill the black area with the white blocks?
Starting with my mouse at the red cross.

I know I should do it in the array, and then draw the grid based on the array.

Any one have an idea?

you might consider a reccursive function... perhaps something like this..:
- check the 8 (or 4 if you don't want diagonal) slots around the current point. (starting f.ex. from the top left)
- if one of the slots is "open", run the same function again, jumping to that current "open" slot.. it will the check the slots around the new point/slot.

when it's done, all open slots should be filled...

I hope you understood what I meant..

you could try converting this: http://www.blitzbasic.com/codearcs/codearcs.php?code=314
or this:
http://www.blitzbasic.com/codearcs/codearcs.php?code=263

LarsG:

I think that your method will stop in one of the corners and not fill the entire area.

Perturbatio:

I'll look into thoose, see if I can get them to work.

Thanx both of you!

No, what happens is that when you enter the function you fill the pixel and then check each of the surrounding pixels in turn. If the pixel is unfilled, then you call the function again. When the pixel is already filled and you've checked all 4 or 8 neighbouring pixels, the function returns where the checking that was being done is resumed.

A function calling itself is called recursion. You do have to be careful with it though, as you could cause the system to crash if it doesn't back out correctly - causing stack overflows and killing your system.

The pseudo code would look something like this.

Function FillPoint(x,y,colour)
  Plot x,y
  If <pixel at x,y-1 open> Then FillPoint(x,y-1,colour)
  If <pixel at x+1,y open> Then FillPoint(x+1,y,colour)
  If <pixel at x,y+1 open> Then FillPoint(x,y+1,colour)
  If <pixel at x-1,y open> Then FillPoint(x-1,y,colour)
  Return
End Function

The above doesn't check for diagonals, but remember it is just pseudo code.

Hope it helps.

And maybe it can add an empty point to some kind of list.
Then when is finshed, take a point from that list and start again.

Every time a point is used from that list it is deleted.

Maybe that way I can get it filled.

Because its Recursive, LarsG's function will fill everything because when a function quits it continues where it got called from. On "end function", execution continues from where the function was called each time...

You mean it will try to fill everything and get a stack overflow error. lol
I tried recursion and got a stack overflow, but only when the area was like 250x250 or larger.

I got it to work.

Heres how I did it:
1) Make a list
2) Add the first point to the list as a string ("4,4")
3) Split the "4,4" string into to INT's
4) Check the array with thoose two INT's
5) Check the 8 slot around my point (4,4)
6) If any of the slots is empty insert their coordinate
into the list.
7) Remove point from list (delete "4,4")
8) Do a While Wend until ListIsEmpty

This way it fills the grid shown above.
It's not fast, but it fills the grid.

Theres still some minor ajustments to make, but its coming along.

Thanx to everyone!

B.t.w I used RobK's StringUtils for the Split function

When I'm done I'll post my code in the archives!

TGD - looks like you've cracked the problem, but I recommend leaving stings alone. Just use types with fields x and y - saves conversions and should be faster.

@Coorae: I use an array, and store how deep the recursion goes. Now, whenever the recursion gets too deep, store the location that would have been next in the array, and dont fill it.

Now, at the end of the function when recursions=1, Go through and call the function once at each of these points. :)

Aren't there any other funky algorithms that also fill a given area?

I am wondering .... if the area that needs to be filled is a specific color or value which doesn't exist anywhere else within the array or image, you don't have to do a complicated recursive fill routine. All you need is a remapping routine. You just go through the whole thing and when you find a pixel or value that is the color or value of the inside of the fillable area, you change it to the fill color/value. I don't know if this works in your case but it's sure simpler and maybe even faster than a flood-fill.

I'm actually using this for 400x400 grid.

My code works but if I try to fill the hole area it's takes a long time. I tried it just to testand it was very slow.

But as I don't need this function to fill a 400x400 grid it works okay. I'll only be using it to fill smaller areas.

But I have been thinking about Falkens suggestion and try using Types

Here is a recursive routine for your fill problem. Enjoy.

;
; Flood Fill example... by Brien King
; Check out FrostByte Freddie at <a href="http://www.arcaderestoration.com" target="_blank">http://www.arcaderestoration.com</a> under "Software"
;
Graphics 800,600,8

Dim G_grid(10,10)

;------------------------------------
; Initialize our grid to all Zeros
;------------------------------------
For x% = 1 To 10
	For y% = 1 To 10
		G_grid(x%,y%) = 0
	Next
Next

;------------------------------------
; Now create a block that we want
; to fill in.
;------------------------------------
For x% = 4 To 7
	For y% = 4 To 7
		G_grid(x%,y%) = 1
	Next
Next

G_grid(3,3) = 1
G_grid(3,4) = 1
G_grid(8,3) = 1

;------------------------------------
; Display our "Before" block
;------------------------------------
For y% = 1 To 10
	temp$ = ""
	For x% = 1 To 10
		temp$ = temp$ + G_grid(x%,y%)
	Next
	Print temp$
Next

;------------------------------------
; This FILL should do nothing as it
; won't find the color we want to
; fill in here.
; We want to fill COLOR 1 with
; COLOR 2.
;------------------------------------
FloodFill(1,2,1,1)

Print 
Print "The next grid should look just like the one above"
Print
;------------------------------------
; Display the Results of our fill
; they should be the same as before
;------------------------------------
For y% = 1 To 10
	temp$ = ""
	For x% = 1 To 10
		temp$ = temp$ + G_grid(x%,y%)
	Next
	Print temp$
Next

;------------------------------------
; Now lets fill in the block in
; the Center.  We want to fill
; COLOR 1 with COLOR 3.  We should
; see the 1's turn into 3's and
; the 0's stay the same.
;------------------------------------
FloodFill(1,3,5,5)

Print 
Print "The next grid should have all 3's in the center"
Print

;------------------------------------
; Show us the Results....
;------------------------------------
For y% = 1 To 10
	temp$ = ""
	For x% = 1 To 10
		temp$ = temp$ + G_grid(x%,y%)
	Next
	Print temp$
Next

;------------------------------------
; Now lets fill outside block in
; the Center.  We want to fill
; COLOR 0 with COLOR 5.  We should
; see the 0's turn into 5's and
; the 3's stay the same.
;------------------------------------
FloodFill(0,5,1,1)

Print 
Print "The next grid should be 5's, 3's and a single 1"
Print

;------------------------------------
; Show us the Results....
;------------------------------------
For y% = 1 To 10
	temp$ = ""
	For x% = 1 To 10
		temp$ = temp$ + G_grid(x%,y%)
	Next
	Print temp$
Next

WaitKey
;---------------------------------------------------
; This function Recursivly fills in an area. of a
; Grid...  
;
; NOTE: This does not handle Diagnols 
; as you will see the Upper Right 1 doesn't change.
; If you need that and can't figure it out,
; let me know.  Also you should keep in mind that
; if you have a HUGE area to fill you could run into
; stack overflow issues.  But that would have
; to be a VERY LARGE area.
;---------------------------------------------------
Function FloodFill(P_colorToFill%, P_color%, P_x%, P_y%)

	;---------------------------------------------
	; If the spot we are on is not the color we
	; want to fill then exit the function, else
	; fill in the color.
	;---------------------------------------------
	If G_grid(P_x%,P_y%) <> P_colorToFill% Then
		Return
	Else
		G_grid(P_x%,P_y%) = P_color%
	EndIf
	
	;---------------------------------------------
	; We start by looking behind our current 
	; position to see if have the color we want.
	;---------------------------------------------
	If P_x% > 1 Then
		FloodFill(P_colorToFill%, P_color%, P_x%-1, P_y%)
	EndIf

	;---------------------------------------------
	; Now look in front of our current 
	; position to see if have the color we want.
	;---------------------------------------------
	If P_x% < 10 Then
		FloodFill(P_colorToFill%, P_color%, P_x% + 1, P_y%)
	EndIf

	;---------------------------------------------
	; Now look above our current 
	; position to see if have the color we want.
	;---------------------------------------------
	If P_y% > 1 Then
		FloodFill(P_colorToFill%, P_color%, P_x%, P_y%-1)
	EndIf

	;---------------------------------------------
	; Now look below our current 
	; position to see if have the color we want.
	;---------------------------------------------
	If P_y% < 10 Then
		FloodFill(P_colorToFill%, P_color%, P_x%, P_y%+1)
	EndIf

End Function

Thanks

I'll see if I can use it.

the problem with recursive functions like someone already said is that you easily get a stack overflow if the gris is too big... so then you can simulate(convert) you recursive function to an iterative one... Since I recently wrote a fill function myself, here is how I did it (and it's pretty fast... got it filling a grid of 30x30 tiles wich gives you 900 tiles and it took only about 4-5 seconds):

let's say you click on the tile x,y

1) store the "color" of that tile and add that tile in an array. While this array is not empty, here is what to do with it:

Loop Until Lenght(Array)=0 (<- pseudo code of course)
3) test the last tile of the array (change its color if needed) and remove it from the array
4) then test the tile [x-1,y], if you must change its color, add it to your array, then test the tile [x+1,y] and add it to your array if you have to change its color, then do the same for the tiles [x,y+1] and [x,y-1]
End Loop

the array will be empty once all the good tiles are filled because you'll be removing the last tiles without adding any new one (since no more tiles will have to be changed)... that's it, and the algo is fast and shouldn't take more than some 20 lines of code.

in fact, you just emulate the recursive algo, but use an array instead of the stack (and an array is hard to "overflow")...

here it is using types
this is not optimised for speed.

Type dot
	Field x,y
End Type

SeedRnd MilliSecs()
Graphics 800,600,0,2
SetBuffer BackBuffer()

Local sizex=50,sizey=50
Dim array(sizex,sizey)

;make random array
For fy=0 To sizey-1
	For fx=0 To sizex-1
		If fy>0 Then oldup=array(fx,fy-1)
		old=Rand(0,3-(old=0)-oldup)
		array(fx,fy)=(old=0)
		If old=0 And fy>0 Then
			If Rand(0,1) Then 
				array(fx+1,fy-1)=1
			EndIf
		EndIf
	Next
Next

ts=10
;main loop
Repeat
	;draw
	For fy=0 To sizey-1
		For fx=0 To sizex-1
			If array(fx,fy) Then
				Rect fx*ts,fy*ts,ts,ts
			EndIf
		Next
	Next
	
	;click
	If MouseHit(1) Then
		fillfast(MouseX()/ts,MouseY()/ts,sizex,sizey,0)
	EndIf
	If MouseHit(2) Then
		fillfast(MouseX()/ts,MouseY()/ts,sizex,sizey,1)
	EndIf
	
	If KeyHit(1) Then End
	
	Oval MouseX(),MouseY(),6,6
	Flip
	Cls
Forever


;flood fill
Function fillfast(startx,starty,arraysizex,arraysizey,fillnumber)
	Local d.dot,newd.dot
	Local dir
	Local fillover
	
	;this is the color that will be replaced
	fillover=array(startx,starty)
	
	;the color you want to fill with is already there.
	If fillnumber=fillover Then Return

	;make first dot
	newd=New dot
	newd\x=startx
	newd\y=starty
	array(startx,starty)=fillnumber

	;each dot will try to make a new dot in all directions	
	For d=Each dot
		For dir=0 To 3
			Select dir
			Case 0 ;right
				x=d\x+1
				y=d\y
			Case 1 ;down
				x=d\x
				y=d\y+1
			Case 2 ;left
				x=d\x-1
				y=d\y
			Case 3 ;up
				x=d\x
				y=d\y-1
			End Select
			;try to make a new dot in this direction
			
			;make sure the new spot is in the boundary of the array
			If x>=0 And y>=0 And x<arraysizex And y<arraysizex Then
			
				;make sure this is the color that you can replace
				If array(x,y)=fillover Then

					;make a new dot
					newd=New dot
					newd\x=x
					newd\y=y
					
					;change the array
					array(x,y)=fillnumber
				EndIf
			EndIf
		Next
		Delete d
	Next
End Function