Weird recursion problem (flood fill algorithm)

Hey guys,

I figure that I would start a new, more focused, topic relating to my problem. The original thread, "Neighbor search algorithm?", can be found here:

http://www.blitzbasic.com/Community/posts.php?topic=61909

Here is where I'm stuck:

The program tends to crash when I search to the north and to the west O_o

Here is the code:

Method tesRegion(a_color$, x_coord%, y_coord%, region_num%)
		If Container[x_coord, y_coord].getBlockColor$() <> a_color Then Return 
		
		Container[x_coord, y_coord].setRegion(region_num)
		
		If x_coord > 0 Then tesRegion(a_color$, x_coord - 1, y_coord, region_num)
		If x_coord < 13 Then tesRegion(a_color$, x_coord + 1, y_coord, region_num)
		If y_coord > 0 Then tesRegion(a_color$, x_coord, y_coord - 1, region_num)
		If y_coord < 11 Then tesRegion(a_color$, x_coord, y_coord + 1, region_num)

		Return 
		
	End Method 

Here are the calls that I made to test the code:

Global blockContainer:BContainer = New BContainer

blockContainer.tesRegion(blockContainer.getContBlockColor(6,9), 6, 9, 1)

The program doesnt run until I comment out the following lines:

If x_coord > 0 Then tesRegion(a_color$, x_coord - 1, y_coord, region_num)

If y_coord > 0 Then tesRegion(a_color$, x_coord, y_coord - 1, region_num)

Anyone have any idea regarding what may be going wrong? I really dont want to give the impression that I am flooding the forum, but I have asked several other people about this problem and no one seems to be able to figure it out. :(

What is the error you get?
Because from what I see there, it shouldn't crash.

Building main
Compiling:main.bmx
flat assembler  version 1.64
3 passes, 15095 bytes.
Linking:main.exe
Executing:main.exe
Unhandled Memory Exception Error
Process complete

Activate debug mode and try it again. This will give you a more precise point.

The error mentioned can't raise on the above function unless the array was not correctly initialized as this error normally will show you in debug "try to access null" and similar ie trying to access an object not present.

Yes it should crash if you comment out those lines. Why doesn't it run with those lines in? Are you saying those lines won't compile?

Dreamora:

Unfortunately, debug mode wont work :( It just compiles, hangs, then crashes. Here is the output from debug mode:

Building main
Compiling:main.bmx
flat assembler  version 1.64
4 passes, 55196 bytes.
Linking:main.debug.exe
Executing:main.debug.exe

Process complete

My program runs fine if the lines I mentioned are commented out (save for the fact that my floodfill algorithm only half-works).

Just for clarity's sake, elements [0][0] through [11][15] are valid in my container. You can see their printout in the previous thread. [0][15] through [11][15] do not print because they are placeholders for another algorithm (their color is set to "placeholder").

Curtastic:

The program will not run unless I comment out those lines. Otherwise I get a runtime error.

Looks OK - what does setRegion do?

setRegion is a call which declare's a block object's region:

Method setRegion(a_number)
		region = a_number
	End Method 

I actually figured out what the problem is...and it's not my code. For the hell of it, I tried commenting out these following lines of code instead:

If x_coord < 13 Then testRegionPos(a_color$, x_coord + 1, y_coord, region_num)

If y_coord < 11 Then testRegionPos(a_color$, x_coord, y_coord + 1, region_num)

It compiles and runs just fine! When I made two seperate functions for testing north and west, as well as testing south and east, the program runs once again.

It looks like the problem is that BlitzMax's internal stack size for function calls is too small for this particular solution! Is there any way around this?

Now as you mention it:
The problem is your function in general.
You check in all 4 directions, but you are not checking if you are testing a field you already visited. Due to that it jumps forth and back between the same 2 fields which won't work.

So what you need to check before calling tesRegion is if the target region_num is different to the current one or unset. If so, you can call tesRegion, otherwise not.

Dreamora,

Thanks! That fixed it!

Actually, it looks like I'm not out of the woods yet :(

I've been running a few test cases and running into problems like these:

Its normal that you won't find other regions.
Strange thing would only be that the blue part at the bottom is missed, sounds like your break condition is still broken and breaks in wrong cases. (perhaps you checked for the region in the wrong direction or did not change it to the correct one when copy pasting ;) )

The way to analyze this to find all regions is:

Start at 0,0
call your function
While x < max
while y < max
if field is not part of a region: (assign it to the next free region index and call your function)
wend
wend

Your recursive function is only to find out where the current region resides.

As you see due to that structure, doing zone checking directly in that loop will end with far better performance ... and is far easier as well btw (you only need to check the field above and the field left. The other 2 don't need to be checked as they will be checked at a later time anyway)

Heya,

Yeah, I should've been more clear. I'll be finding one region at a time, where the start of the algorithm is determined by a mouseclick. The main issue right now is that the algorithm doesnt allways find all of the tiles in a region. It also crashes from time to time, giving me the same out of memory exception.

Here is the current state of the, non-working, code:

Method testRegion(a_color$, x_coord%, y_coord%, region_num%)
		
		 
		If (x_coord >= 0) And (y_coord >= 0) And (x_coord <= 13) And (y_coord <= 11) Then 
			If Container[x_coord, y_coord].getBlockColor$() <> a_color Then Return 
			If Container[x_coord, y_coord].getRegion() = region_num Then Return 
			
		Container[x_coord, y_coord].setRegion(region_num)

		Else
			Return
		End If  
		
		Container[x_coord, y_coord].setRegion(region_num)

		
		If x_coord > 0 Then testRegion(a_color$, x_coord - 1, y_coord, region_num)
		If x_coord < 13 Then testRegion(a_color$, x_coord + 1, y_coord, region_num)
		If y_coord > 0 Then testRegion(a_color$, x_coord, y_coord - 1, region_num)
		If y_coord < 11 Then testRegion(a_color$, x_coord, y_coord + 1, region_num)


		Return 
End Method 

Hello again,

I've update my code in order to demonstrate some test cases:

Method testRegion(a_color$, x_coord%, y_coord%, region_num%)
		
		 
		If (x_coord >= 0) And (y_coord >= 0) And (x_coord <= 13) And (y_coord <= 11) Then 
			
			If Container[x_coord, y_coord].getChecked() = 1 Then Return 
			Container[x_coord, y_coord].setChecked()
			If Container[x_coord, y_coord].getBlockColor$() <> a_color Then Return 
			If Container[x_coord, y_coord].getRegion() = region_num Then Return 
				
			If Container[x_coord, y_coord].getBlockColor$() = a_color Then Container[x_coord, y_coord].setRegion(region_num)
				
		Else
			Return
		End If  
		

		
		If x_coord > 0 Then testRegion(a_color$, x_coord - 1, y_coord, region_num)
		If x_coord < 13 Then testRegion(a_color$, x_coord + 1, y_coord, region_num)
		If y_coord > 0 Then testRegion(a_color$, x_coord, y_coord - 1, region_num)
		If y_coord < 11 Then testRegion(a_color$, x_coord, y_coord + 1, region_num)


		Return 
		
 	End Method 

The 1's represent the tiles which are within a region, and the C's represent blocks which were visited by the algorithm.

It works in some pretty complex cases. All of the blocks in the orange region were found, and all of the surrounding blocks were flagged as being visited:



Then the algorithm stumbles in other cases. Here, the algorithm found all of the blocks in the region, but it did not properly flag all of the blocks to the south as being visited:



And then it totaly chokes at other times, as seen here:



Also, I still get a 'memory exception' runtime error from time to time. It points to the following line:

If Container[x_coord, y_coord].getChecked() = 1 Then Return

Anyone have any ideas?

What I see from this screenshots is that all screens show that the algorithm is wrong as seperated red / blue / orange regions should get different labels ... At least thats what region detection normally does.

I just need it to test one region at a time. Based on a mouseclick, the program will determine all of the blocks in the region, as well as the total number of blocks. When it clicks in a new region, the old region will be discarded and a new region will be recalculated.

The main issues right now are the crashes and the fact that it doesnt check every block in every case.

w00t! Got it working! It seems like some of my numbers were a bit iffy. A buddy of mine online cought it.

Thank you all for being so helpful and patient!