Flood fill algorithm without recursion?

[tyuo9980]

I need to use a flood fill for my program but java limits my stack calls.

How would I be able to implement a floodfill without using recursion or queues?

The reason why i cant use queues is that im using ready to program ide and it only has up to java v1.4 libraries.

code:

public static void calcArea (int x, int y)     {         boolean boundary = false;         for (int i = 1 ; i <= walls ; i++)         {             if (x == wallx1 [i] && x == wallx2 [i] && y > wally1[i] && y < wally2[i]) //vertical             {                 boundary = true;             }             else if (y == wally1 [i] && y == wally2 [i] && x > wallx1[i] && x < wallx2[i]) //horizontal             {                 boundary = true;             }         }         if (!CArea [x] [y] && !boundary)         {             if (x > 9 && x < 431 && y > 79 && y < 551)             {                 CArea [x] [y] = true;                 calcArea (x + 1, y);                 calcArea (x - 1, y);                 calcArea (x, y + 1);                 calcArea (x, y - 1);             }         }                 return; }

[Tony]

tyuo9980 @ Fri Dec 30, 2011 3:10 pm wrote:

I need to use a flood fill for my program but java limits my stack calls.

More likely you're limited by the memory available to the OS than the language of choice.

In specific, you likely just have an infinite loop somewhere.

[tyuo9980]

im 100% sure its java. i increase the stack available in eclipse and it works.

[Tony]

There's BFS, but that uses a queue -- what's the problem with those?

[tyuo9980]

queues came in java 1.5 i think.

ready to program uses 1.4.2 so no go

[Tony]

You can implement a queue with an array. Java 4 has arrays, doesn't it?

[tyuo9980]

how would i use an array to queue?

[Tony]

array is just a datastore. You can also keep data in a linked list, file on disk, or somewhere in the cloud. It doesn't really matter, as you're supposed to put in an API layer in between. That is, implement the interface of Queue<E>. With arrays -- item goes into the queue == item gets added to the end of the array. Item leaves the queue == item gets removed from the front of the array.

[mirhagk]

The recursive algorithm seems like it will call itself infinite times. For instance the first call with then call one with the node to the left, which will then call it with the node to the right (ie the starting node) and it will go back and forth forever. You need some way of figuring out if you've calculated that square before.

[Tony]

Tony @ Fri Dec 30, 2011 3:30 pm wrote:

In specific, you likely just have an infinite loop somewhere.

[mirhagk]

Yeah I know that you mentioned it tony, but it was obvious that he didn't see it, and he'd be going about implementing some queueing algorithms only to end up with the same problem.

[tyuo9980]

there is no infinite loop. the function works very well.

if (!CArea [x] [y] && !boundary)
{
CArea [x] [y] = true;
....

this is where i see if the square has been checked already.

if an area is checked it will be set to true.

this is a video of my function:

http://www.youtube.com/watch?v=mQPbzsALF0M

[mirhagk]

Okay, well then there is no reason why it wouldn't work, as the call stack for java is larger then how large your thing.

[tyuo9980]

how large exactly is java's stack size?

Because this flood fill will reach a maximum of 197400 stacks which is ~5.3mb of space. How would I be able to reduce the usage?

[Tony]

looking into this further, Java does limit the stack size, as it assumes that multiple threads (each with its own stack) will be running. StackOverflow vs. OutOfMemory... Since you have just a single thread, it could safely crank that limit up to be over 9000, but presumably "Ready To Program" is not cool with JVM flags.

You can reduce the stack usage by making less non-terminating method calls.

e.g., filling open areas in larger blocks. If you know you've got a chunk of 10x10 available to you, you can fill the inner 9x9 block and terminate, leaving just the outer perimeter to contribute to the stack-size growth. This would grow the stack at 19% of the previous levels (though, of course, require more computation to figure out if such "optimization" moves are even available).

Alternatively you could just throw the points onto the heap, and not make recursive calls. Which is basically the Queue approach (just, using any other datastore that's available).