Recursion limit

Blitz3D Forums/Blitz3D Programming/Recursion limit

sting

(Posted 2012) [#1]

Below is a quick and dirty implementation of a "Flood Fill" algorithm.

It works fine in all but 2 points.

1) It can't fill any area larger than blitz's recursion limit (I'm thinking its 32,767 (signed short int)) in any single carnal direction from the point of origin.

2) Blitz's image buffer seems to be fine when it comes to wrapping left to right (until now I didn't know it did it on its own), but the moment my function touches the top or bottom I get a MAV. It's odd also because it normally just ends the program. The only time its given me the MAV error box is in Debug. This could be a quirk in Read/WritePixelFast but I'm not sure.

I understand why problem #1 happens but I'm unsure how to fix it, short of redesigning the algorithm. And #2.. I just don't know.

Any feedback, suggestions, fixes are appreciated. This was just practice for me, nothing big.

Graphics3D 600,600,32,2

Global IDw=400,IDh=400            ; Image Dimensions
Global IMG = CreateImage(IDw,IDh)
Global xx=0
Global yy=0
Global offset=100
Global t

;-----------------[[ Make a test image ]]
SetBuffer(ImageBuffer(IMG))
ClsColor 49,200,143
Cls
Color 0,0,0
Oval 50,50,270,100,0
Oval 200,70,80,300,0
;Rect 0,0,IDw,IDh,0  ; Temporary fix for problem 2, A 1 pixel border.
ClsColor 0,0,0

;-----------------[[ Show the IMG initialy ]]
SetBuffer(BackBuffer())
Cls
DrawBlock IMG,offset,offset
WaitMouse

;-----------------[[ click where you want to fill ]]
.another
xx=MouseX()-offset
yy=MouseY()-offset
SetBuffer(ImageBuffer(IMG))
LockBuffer
ff(xx,yy,ReadPixelFast(xx,yy),16763135)       ; <-----[ Flood fill ]
UnlockBuffer
SetBuffer(BackBuffer())
Cls 
DrawBlock IMG,offset,offset
Flip 
WaitMouse : Goto another



;------[ Flood fill : Origin x, Origin y, Color to fill over, Color to fill with ]
Function ff(x,y,o,f)
	If ReadPixelFast(x,y)<>o Then Return
	WritePixelFast(x,y,f)
	t=t+1 : If t => 50 Then test()              ; Comment line for instant fill. Uncomment to see it filling. "t" is the speed (higher is faster).
	If ReadPixelFast(x+1,y)=o Then ff(x+1,y,o,f)
	If ReadPixelFast(x-1,y)=o Then ff(x-1,y,o,f)
	If ReadPixelFast(x,y+1)=o Then ff(x,y+1,o,f)
	If ReadPixelFast(x,y-1)=o Then ff(x,y-1,o,f)
	Return 
End Function

;------[ Testing function just allows for visual filling ]
Function test()
	t=0
	UnlockBuffer
	SetBuffer(BackBuffer())
	Cls 
	DrawBlock IMG,offset,offset
	Flip 
	SetBuffer(ImageBuffer(IMG))
	LockBuffer
End Function

Ross C

(Posted 2012) [#2]

The MAV could possibly be you writing past the dimensional limits of the image. I don't see you checking whether you have exceeded these limits anywhere?

Function ff(x,y,o,f)
	If ReadPixelFast(x,y)<>o Then Return
	WritePixelFast(x,y,f)
	t=t+1 : If t => 50 Then test()              ; Comment line for instant fill. Uncomment to see it filling. "t" is the speed (higher is faster).
	If ReadPixelFast(x+1,y)=o Then ff(x+1,y,o,f)
	If ReadPixelFast(x-1,y)=o Then ff(x-1,y,o,f)
	If ReadPixelFast(x,y+1)=o Then ff(x,y+1,o,f)
	If ReadPixelFast(x,y-1)=o Then ff(x,y-1,o,f)
	Return 
End Function

Should be something like:

Function ff(x,y,o,f)
        If (x>0 and x< IDw-1) and (y>0 and y< IDh) then
	   If ReadPixelFast(x,y)<>o Then Return
	   WritePixelFast(x,y,f)
	   t=t+1 : If t => 50 Then test()              ; Comment line for instant fill. Uncomment to see it filling. "t" is the speed (higher is faster).
	   If ReadPixelFast(x+1,y)=o Then ff(x+1,y,o,f)
	   If ReadPixelFast(x-1,y)=o Then ff(x-1,y,o,f)
	   If ReadPixelFast(x,y+1)=o Then ff(x,y+1,o,f)
	   If ReadPixelFast(x,y-1)=o Then ff(x,y-1,o,f)
	   Return True ; gives you something to check when querying the function

        Else
            Return False ; gives you something to check when querying the function.
        End If
End Function

Last edited 2012

dynaman

(Posted 2012) [#3]

Recursion is fun, whatever problems it is tailor made for solving it can't handle due to the stack size limitation...

I ran into the same problem when writing a flood fill routine - luckily there are a couple floating around in the code archive that work, easiest thing to do is take one of them and modify it (or just use it straight up)

Yasha

(Posted 2012) [#4]

On #2, Ross is probably right. ReadPixelFast doesn't do boundary checks, in order to maximise the speed of the operation, so without testing if you're within the limits of the buffer it will very possibly go over the edges. When this happens, you're reading from "something"... and of course the golden rule when dealing with undefined memory is "there is no rule" (writing is likely to be the more important one here). On some systems and in some programs it won't object, and will show you the Horrors Man Was Not Meant To Know beyond the edges of the allocated world; on others it will crash immediately.

As for #1... Blitz's recursion limit will be set by Windows, which provides the stack, and is one of those things that's really rather hard to change. However, remember that any recursive algorithm can be trivially converted to a loop-plus-stack. All you need to do (in theory) is identify the variables that change from frame to frame (in this case x and y), and allocate them on a manual stack of your own creation (you could extend and retract a bank, or more simply just define a FFStackFrame type and use the list as the stack), then run the executing body of the function in a loop while modifying your own stack as needed. This will require a bit of jumping around since the function as given forms a tree, but it's very doable (the main problem is likely to be speed, but that's your tradeoff). Being able to convert between recursion and iteration 1:1 is a handy skill, so it's well worth practising it. (This gives you the freedom to design algorithms in an elegant recursive way, then "hand compile" them to something that works better and possibly more efficiently at a later time.)

Adam Novagen

(Posted 2012) [#5]

I am rather proud to say that one of my best works as a young coder was a perfectly working flood fill routine, which used Types to avoid the recursion problem. You can find it here: http://blitzbasic.com/codearcs/codearcs.php?code=2157

At the time I made it, I didn't understand the binary shift commands - Shl, Shr and so on - so I used multiplication and GetColor() for the pixel values, which of course was quite a bit slower. _33 modified the function to use ReadPixelFast() and binary shifts, which improved its speed significantly; the improved version is in the comments.

sting

(Posted 2012) [#6]

Awesome. Thanks for all the help.

#2 was a kind of Duh moment for me. I knew I was reaching outside the image but was getting confused when it kept doing it even after I put in some limiting code. After a while I realized that while I was limiting the checking to the size of the image, the code was checking +1 at the border. Now the problem is that limiting it with -1 on the border creates a one pixel border around the entire image. Not a problem as I can just increase the size of the image by 2px and make a "buffer zone" so I can effect all the pixels in the real image for completeness sake.

As for problem #1 I now have a lot to look into, but that's fine because I haven't really had a problem that has required this approach before. Or more like I haven't dealt directly with manually manipulating stacks.
Thanks all. :)

Floyd

(Posted 2012) [#7]

Here's one that's extremely fast. I got it from an earlier version of this site, in 2001 which makes it older than Blitz3D. This is exactly the way it was then except that I changed the Graphics to windowed.


;FastPixelFill 
;Written by Thomas A. Stevenson (wargamer) 
; thomas99@... 
;2/16/01 
;Blitzbasic 1.42 

;This is a super fast floodfill routine that 
;utilizes WritePixelFast and a list of active points 
;to quickly fill any kind of blank area (color 0,0,0) 
;inside or outside a boundry of any non blank color 

;Send me a email if you find it useful 
;but feel free to use it or modify it in any manner 

SeedRnd MilliSecs()

Const scrnw = 800 
Const scrnh = 600 

Global white 
Global currentP,LastP,MaxP=5000,ActiveP,MaxA 
Dim PList(1) 
Dim dirX(8),dirY(8) 
diry(1)=-1 
dirx(2)= 1 
dirY(3)= 1 
dirx(4)=-1 

;main *************************************************** 

Graphics scrnw, scrnh, 0, 2		; originally full screen 
SetBuffer FrontBuffer() 

;Draw a hexagon with fractal sides 
xHand=DrawLumb(400,300,200,20,60) 

;Flood the inside on screen 
OnScreenfloodFill(xHand,100,100) 
WaitKey 
;flood the outside on screen 
OnScreenfloodFill(xHand,2,2) 
WaitKey 

;flood the inside off screen 
Pcolor=255 Shl 16+ 10 Shl 8 + 10 
floodFill(xHand,100,100,Pcolor) 
WaitKey 

;flood the outside off screen 
Pcolor=10 Shl 16+ 255 Shl 8 + 10 
floodFill(xHand,10,10,Pcolor) 

WaitKey 
End 

;Functions ************************************************ 


Function OnScreenfloodFill(source,x,y) 

	SetBuffer FrontBuffer() 
	Cls 
	DrawBlock source, 0,0 
	t0=MilliSecs() 
	Dim PList(maxP) 
	
	Pcolor=100 Shl 16+ 100 Shl 8 + 100 
	currentP=0 
	LastP=0 
	Plist(LastP)=y Shl 16 + x 
	LockBuffer 
	WritePixelFast x,y,PColor 
	Repeat 
	Until NextPoint(Pcolor,scrnW,ScrnH)=0 
	UnlockBuffer 
	
	
	t1=MilliSecs() 
	
	Color 255,255,255 
	Text 700,0,"Time "+Str$(t1-t0) 
	;Text 700,20,"MaxA "+Str$(maxA) 

End Function 




Function floodFill(source,x,y,Pcolor) 

	t0=MilliSecs() 
	w=ImageWidth(source) 
	h=ImageHeight(source) 
	SBuffer=ImageBuffer(source) 
	SetBuffer Sbuffer 
	
	Dim PList(maxP) 
	currentP=0 
	LastP=0 
	Plist(LastP)=y Shl 16 + x 
	LockBuffer 
	WritePixelFast x,y,PColor 
	Repeat 
	Until NextPoint(Pcolor,w,h)=0 
	UnlockBuffer 
	t1=MilliSecs() 
	
	SetBuffer FrontBuffer() 
	Cls 
	DrawBlock source,0,0 
	Color 255,255,255 
	Text 700,0,"Time "+Str$(t1-t0) 

End Function 




Function NextPoint(PColor,w,h) 

	;pull a point off the list of active points 
	ActiveP=ActiveP-1 
	x0=PList(currentP) And 65535 
	Y0=PList(currentP) Shr 16 
	;check the four adjacent pixels 
	For i=1 To 4 
		x=x0+dirX(i) 
		y=y0+dirY(i) 
		If x<0 
		ElseIf y<0 
		ElseIf x>W 
		ElseIf y>H 
		ElseIf ( ReadPixelFast( x, y ) And $ffffff ) = 0 Then  ; ****** see NOTE2  
		; if blank, color and add to active list 
		WritePixelFast x,y,PColor 
		LastP=LastP+1 
		ActiveP=ActiveP+1 
		If LastP>maxP Then LastP=0 ;wrap around if at end 
			Plist(LastP)=y Shl 16 + x ;add pixel list 
		EndIf 
	Next 
	
	;If ActiveP>maxA Then maxA=ActiveP ;for debugging 
	
	;set current point to next on list 
	currentP=currentP+1 
	If currentP>MaxP Then currentP = 0 ;if at end wrap around 
	
	Return ActiveP ;we're done when there's no more active points 

End Function 



Function fracture(x0,y0,x2,y2,H, Power#, counter) 
;Recursive routine for roughing up a line 
	If counter<1 
		Line x0,y0,x2,y2 
	Else 
		x1=(x0+x2)/2+H*Rnd(-1,1) 
		y1=(y0+y2)/2+H*Rnd(-1,1) 
		H=H^(power) 
		fracture (x0,y0,x1,y1,H,Power,counter-1) 
		fracture (x1,y1,x2,y2,H,Power,counter-1) 
	EndIf 
End Function 



Function DrawLumb(cx,cy,r,m,ang) 
	Color 255,255,255 
	
	For i=1 To 6 
		x1=cx+r*Sin((i-1)*ang) 
		y1=cy+r*Cos((i-1)*ang) 
		x2=cx+r*Sin(i*ang) 
		y2=cy+r*Cos(I*ang) 
		amp=r/5 
		fracture(x1,y1,x2,y2,amp,0.8,5) 
	Next 

	;saved it as an image 
	xhand=CreateImage(2*r+2*m,2*r+2*m) 
	GrabImage xhand,cx-r-m,cy-r-m 
	Return xhand 
End Function

Adam Novagen

(Posted 2012) [#8]

I seem to have broken that one already. It got stuck in some sort of infinite loop after the third stage of the demo and crashed.

Tell you one thing though, I had NO IDEA that you could resize an array at any point in the program, including within a function!

Floyd

(Posted 2012) [#9]

That's strange.

Before posting this I tried the original version with no problem. Then I made it windowed mode and tried again, successfully.

It uses random numbers to draw the region to be filled. I guess it occasionally draws something it can't handle.

Mahan

(Posted 2012) [#10]

If it is some kind of overflow/out of range/pixel outside area-problem, you could try to wrap the relevant commands in your own functions, and provide some file-based logging in those functions (of arguments etc).

This way you'll be able, once the crash happens, to look in the logs for some clues as to what might have happened.

I know I sound a bit vague, but that's on purpose. Always first trust your "gut feeling" and log the things you think might go awry.

Also i highly support Yasha's suggestion to "flatten" any recursive function using your own synthetic stack (array, bank etc.) if you cannot set (or know) an absolute limit on how deep it will reach.