Omnimaga

General Discussion => Technology and Development => Computer Projects and Ideas => Topic started by: ZippyDee on February 10, 2012, 02:56:04 am

Title: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 10, 2012, 02:56:04 am
So, I was trying to write an assembly program to execute a fixed-memory flood fill routine as described by the "flood fill" Wikipedia article here (http://en.wikipedia.org/wiki/Flood_fill#Fixed_memory_method_.28right-hand_fill_method.29), but I realized that the algorithm written there is poorly explained, and also missing a lot of crucial conditions.

After realizing this, I opened up Adobe Flash to try to write an implementation so that I could easily see what was going on at all times, and could therefore debug it a lot more easily.

After hours of debugging and modifications, I finally was able to write an algorithm that actually worked in all situations. Here is the pseudocode I have written out for it:

Code: [Select]
RULE is "right"
FINDLOOP is false
BOTTLENECK is false

CUR is the current pixel
MARK is the first mark, and is not set
MARK2 is the second mark, and is not set

main loop:
if CUR is bound by 4 edge pixels
paint CUR
all possible pixels have been filled, so exit the routine
 
if CUR is bound by 3 edge pixels
paint CUR
move based on RULE
continue main loop

if CUR is bound by 2 edge pixels
if the two bounding edge pixels are not across from each other, and the corner opposite both edge pixels is not filled
paint CUR
move according to RULE
continue main loop
else
if RULE is "right" and  MARK is not set
set MARK to CUR's location and direction
set FINDLOOP to false
else, if MARK is set
if MARK2 is not set
if CUR is at MARK's location
if CUR's direction is the same as MARK's
remove MARK
set RULE to "right"
else
set RULE to "left"
set CUR to MARK's direction
set FINDLOOP to false
else, if FINDLOOP is true
set MARK2 to CUR's location and direction
else
if CUR is at MARK's location
set CUR to MARK2's direction and location
remove MARK
remove MARK2
set RULE to "right"
else if CUR is at MARK2's location
set MARK to MARK2's direction and location
set CUR's direction to MARK2's direction
remove MARK2
if RULE is "right" and MARK is not set
if BOTTLENECK is false
paint CUR
set BOTTLENECK to false
move according to RULE
continue main loop

if CUR is bound by 1 edge pixel
if RULE is "left" and FINDLOOP is false
set FINDLOOP to true
else, if neither  of the corners opposite the bounding pixel are filled
paint CUR
move according to RULE
continue main loop

if CUR is bound by 0 edge pixels
if RULE is "left" and FINDLOOP is false
set FINDLOOP to true
set BOTTLENECK to false
move any direction (use a default direction, not a random one)
continue main loop


##############################
how to move according to RULE:
if CUR is filled or the rule-side-corner is filled
move CUR one step forward
else
if MARK is at the pixel one step forward
set BOTTLENECK to true
else, if MARK2 is at the pixel one step forward
set MARK to MARK2's direction and location
set CUR's direction to MARK2's direction
remove MARK2
if RULE is "left" and FINDLOOP is false
if either the pixel two steps forward is filled or the non-rule-side pixel is filled
set FINDLOOP to true
move CUR one step forward
move CUR one step to the RULE side



##############################
every time you paint:
remove MARK, if set
remove MARK2, if set
set FINDLOOP to false
set BOTTLENECK to false
set RULE to "right"

I'd like to put this into the Wikipedia article so that people can have a much better example to base their code on. Is there any way I should modify this pseudocode to make it look better?

I am also going to create some images explaining what some things are (like what an "open corner" is, as opposed to a "closed corner").

Also, if someone wants to write an ASM implementation of this, please go ahead. I bet your implementation would be better than mine >.<
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: DJ Omnimaga on February 10, 2012, 03:20:50 am
This seems interesting. When you get an ASM or other language version done, it would be nice to see it in action. :)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 10, 2012, 03:45:22 am
Here's a link to the flash file I made to debug this algorithm.

http://megaswf.com/file/2130949 (http://megaswf.com/file/2130949)

The red arrow is the curent location, the blue filled arrow is the first marker, and the blue filed arrow with a green outline is the second marker used for removing unwanted loops.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: jacobly on February 10, 2012, 03:45:24 am
To be consistent, each case in the main loop should probably end with continue main loop. Also, I don't see any code that sets MARK2.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 10, 2012, 03:48:55 am
To be consistent, each case in the main loop should probably end with continue main loop. Also, I don't see any code that sets MARK2.
Oops! I accidentally put MARK instead of MARK2 at the place it should be set. Fixed that now. And I added the "continue main loop" as well.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: DJ Omnimaga on February 10, 2012, 03:58:19 am
Interesting, thanks for the link. I am curious if in some occasions it can loop forever, though? Because once it seemed to go through the same path 5 times until it finally started filling more stuff, and as an ASM program, if it can end up into an endless loop, then that means a battery pull/RAM Clear :P
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Jim Bauwens on February 10, 2012, 03:58:54 am
Hmm, maybe I should rewrite my JavaScript minesweeper to use a better algorithm.
I just made mine form scratch, so its probably not efficient.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 10, 2012, 04:00:01 am
Interesting, thanks for the link. I am curious if in some occasions it can loop forever, though? Because once it seemed to go through the same path 5 times until it finally started filling more stuff, and as an ASM program, if it can end up into an endless loop, then that means a battery pull/RAM Clear :P
No, it will not loop forever. Each time it went through the path, it changed something. It either filled at least one pixel, or it moved the marker to a new location.

Hmm, maybe I should rewrite my JavaScript minesweeper to use a better algorithm.
I just made mine form scratch, so its probably not efficient.
For javascript, you shouldn't have to worry about stack or memory issues, so a simple recursive flood-fill would be best. This one is much too slow to be worthwhile for any system that can handle recursive/stack-based flood-fills.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: DJ Omnimaga on February 10, 2012, 04:03:13 am
Ah maybe I didn't notice, since it was going on pretty fast.

Also I'm curious how fast this would be in z80 ASM, considering you don't have to update the LCD every frame but only at the end.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 10, 2012, 04:07:29 am
Ah maybe I didn't notice, since it was going on pretty fast.

Also I'm curious how fast this would be in z80 ASM, considering you don't have to update the LCD every frame but only at the end.
Yeah, I'm wondering that, too. Seeing as it's such an obnoxiously slow routine, a mostly-speed-optimized ASM version would probably be best. I personally don't feel like I'd be able to make a very good routine in ASM. I'd rather that someone else give it a go...

Maybe someone could even write an Axe implementation just so something exists to base some of the ASM off of. This pseudocode is written in structured English, so it's not really written for easy translation directly into ASM.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: DJ Omnimaga on February 10, 2012, 04:10:41 am
Yeah I agree that translating high level language stuff into such low level language would be a huge challenge. This is why there are so few BASIC games that got converted straight to ASM.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Jim Bauwens on February 10, 2012, 04:58:48 am
For javascript, you shouldn't have to worry about stack or memory issues, so a simple recursive flood-fill would be best. This one is much too slow to be worthwhile for any system that can handle recursive/stack-based flood-fills.
Ah, mine is recursive. Thanks for the information anyway :)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: jacobly on February 13, 2012, 05:24:05 am
I am working on converting this algorithm to z80 assembly, so I thought I would post some screenshots.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Scipi on February 13, 2012, 12:31:44 pm
How fast is this when it only draws to the screen when it finishes rather than plot every pixel individually?
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 13, 2012, 01:15:39 pm
That looks awesome, jacobly!

You know, if the finished version is still quite slow, it may be good to periodically draw to the screen as it fills rather than only at the end, just so people know it's still working and hasn't totally crashed or something.

How fast is this when it only draws to the screen when it finishes rather than plot every pixel individually?
Well, the algorithm itself is going to be slow. There's no way around that. It has to do a lot of tracing of boundaries in order to validate the pixels for drawing. The only question is about how slow it will be. This floodfill will certainly not be anything you'd want to use for dynamic drawing in games or anything. I'd say it would be used solely in on-calc graphics programs. Yes, it will be slow, but the trade off is worth it to have a floodfill that doesn't threaten a stack overflow no matter how large or complex of a shape you are filling.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: jacobly on February 13, 2012, 04:01:48 pm
In those screenshots, the screen is being updated 4-5 times per frame, so the program is spending most of the time updating the screen. Also, I haven't even started optimizing the code, and I have some ideas for how to optimize the algorithm. In fact, filling a blank screen from the center without updating the screen currently takes only 10 seconds (That's 24x faster than the screenshot ;D).

Edit: Updating every 256'th frame looks like this:
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on February 13, 2012, 04:14:34 pm
Hmm, so your flood fill algorithm just traces around the edge of the region until it is all filled? Nice...
I am curious, will it work properly if you have a setup like an hourglass but at the middle (where it is narrow) you have 1 empty pixel with a black pixel on either side?

EDIT: Ah, I see the screenies, now >.>
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Builderboy on February 13, 2012, 05:19:06 pm
This is a very very clever algorithm!  Kudos to its creation, it sounds like a powerful utility for anybody needing a flood fill with no memory overhead associated with it.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 13, 2012, 07:24:39 pm
Hmm, so your flood fill algorithm just traces around the edge of the region until it is all filled? Nice...
I am curious, will it work properly if you have a setup like an hourglass but at the middle (where it is narrow) you have 1 empty pixel with a black pixel on either side?

EDIT: Ah, I see the screenies, now >.>

Yeah, the algorithm traces the edges and only fills in a pixel if it is positive that filling that pixel will not block off another area to fill. If it is unsure, it places a markat that "questionable" pixel indicating the direction it was heading and continues to trace the edges until it comes back to the mark.

If it reaches the mark and the mark is pointing in the direction that it was already heading, then it knows filling that pixel will still allow it to get to the other side.

However, if it reaches the mark and the mark is pointing in a different direction, then there must be some sort of a loop that turns it back onto itself, meaning it wouldn't be able to reach the other side if it filled the pixel.

To eliminate this loop, it turns around and starts backtracking around the loop. Once it reaches another "questionable" pixel in that loop, a second mark is placed on that pixel. It keeps backtracking until it runs into one of the two marks.

If it runs into the second mark before the first mark, it knows the place where it gets turned around on itself must be further into the loop, so it turns around and backtracks again, finding the NEXT "questionable" pixel.

But if it reaches the first mark before the second it knows that filling the pixel at the second mark will get rid of the loop without blocking off the rest of the map. So it fills in the pixel at the second mark, removes both marks, and continues as usual from where the second mark was.


Hope that explanation helps clarify how the algorithm works. It's certainly easier than trying to interpret that pseudocode.


Edit:
In those screenshots, the screen is being updated 4-5 times per frame, so the program is spending most of the time updating the screen. Also, I haven't even started optimizing the code, and I have some ideas for how to optimize the algorithm. In fact, filling a blank screen from the center without updating the screen currently takes only 10 seconds (That's 24x faster than the screenshot ;D).

Edit: Updating every 256'th frame looks like this:
What about updating every Xth time it paints, not every Xth frame? That might go even faster.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: DJ Omnimaga on February 14, 2012, 10:39:54 pm
Wow that's fast Jacobly. To think in Paint Shop Pro it took two seconds to fill an entire 200x200 image on a Pentium 100 MHz...
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on February 16, 2012, 02:20:57 pm
So, uh, I came up with my own algorithm and implemented it in Grammer code. Needless to say, even when updating every frame, it was about as fast as Jacobly's. My calc has crashed so it'll take me a bit to reprogram it, but I wrote down the pseudo code. Before I post it, I want to double check on a few things:
It uses 2 fixed buffers (the graph screen and another 768-byte buffer)
It does not trace around the edge like your code

The code is very simple and you will see why it is fast. I didn't know if using another buffer was okay or not for your implementation.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Builderboy on February 16, 2012, 02:43:38 pm
If you are using another 768 byte buffer, you might as well use a queue method at that point XD
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 16, 2012, 02:46:37 pm
If you ever wanted to add grayscale support then you'd need another buffer, meaning 3 buffers...that's a lot of memory to keep track of... The whole point is that this algorithm uses no extra memory other than what is in the routine itself.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on February 16, 2012, 03:00:40 pm
Oh, that is cool o.o I am still not seeing how it can mark paths though (or is it one at a time?)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: ZippyDee on February 16, 2012, 03:01:25 pm
only one mark is ever placed at a time. yeah.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on February 16, 2012, 03:02:30 pm
Wow, very nice O.O That is indeed an excellent algorithm, then O.O
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: MGOS on April 03, 2012, 11:22:22 am
I'm not sure if this counts to necroposting, but because I need something like that atm I'm now curious to see Xeda's algorithm.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on April 03, 2012, 02:30:25 pm
Hmm, I actually used my algorithm in my TI-Concours entry :) How it works is this:

Setup: I clear a buffer the size of the screen (in Axe, I used L3, originally)

1) Start going in one direction until you hit a barrier, turning pixels ON
     While doing this, check either side of the pixel. If either side is OFF, plot the pixel on the other buffer as well.
2) When you hit a barrier, if you have no other directions, search the buffer for an ON pixel. If your draw buffer has 1 or 0 directions it can go in, pixel-off the back buffer. If it was zero directions, keep searching. If it was one or more, start drawing from there

So, it uses Fixed-Memory, but instead of no extra memory required, it uses a 768-byte buffer as a scrap buffer.

EDIT: I removed a bunch of stuff from my TI-Concour entry so that it just had the flood fill, so I added a screenie. I have a button ([VARS]) that when you are holding it, it will update the LCD to show you what it is doing, so that is why sometimes you see it filling in my screenie and sometimes you don't :)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: DJ Omnimaga on April 03, 2012, 02:59:05 pm
Looks nice Xeda. I think someone should do a drawing program with that kind of algorithm. :)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: MGOS on April 03, 2012, 04:19:26 pm
Wow, Xeda, that's awesome! Thanks, that helped me a lot.  :)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on April 03, 2012, 04:25:53 pm
Cool ! I wasn't sure if I had explained it well enough :)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: MGOS on April 03, 2012, 04:52:37 pm
Well, do you know what a pxl-test returns outside of the screen? Do I have to do exception handeling right there?
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on April 03, 2012, 05:10:50 pm
yeah, in Axe it returns zero. I wrote my own hex code to make a custom pixel test (it returns 1 if the pixel is off and in bounds, otherwise zero)
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: MGOS on April 03, 2012, 05:18:26 pm
That's clever for this use.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on April 03, 2012, 05:27:12 pm
I don't have enough time to post the code, so I squished some screenies together of the call:
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: MGOS on April 04, 2012, 04:15:03 pm
Again, thanks, but I came up with another, also very fast (maybe faster than yours :)) routine for fixed memory flood filling by myself.
It used besides the drawing buffer(s) a stack (L1) and a 768 byte second buffer.
You can imagine that it works like memory swapping on a computer, if the RAM is full, data will be stored on the hard drive instead.
My routine searches iterative for pixels to fill using the stack, but if the stack overflows, it swaps to the other buffer using the slower searching routine.
When the stack empties, the data will be put back on the stack.
Like this I can achieve small areas filled extremely fast and bigger areas also with decent speed.
The only disadvantage is that it uses another 768 byte buffer (L3 when not uing grayscale) and L1 as stack. But I'm able to carry that.

Code: [Select]
:.FLOOD
:Buff(768)→GDB1
:15→A .Coordinates of "paint bucket"
:15→B
:0→S→D→C .Screen buffer size, data buffer size and counting var
:PUS(A,B) .Add the first pixel to stack
:While S+D . as long there's sth in the buffers
:C++
:POP() .Get a pixel
:!If pxl-Test(P,Q) .Test if it's off
:Pxl-On(P,Q) .if yes, turn it on
:P?PUS(P-1,Q) .Put pixels around it on the stack
:P-95?PUS(P+1,Q)
:Q-63?PUS(P,Q+1)
:Q?PUS(P,Q-1)
:End
:C^64??DispGraph .Only display every 64 time; not needed
:ReturnIf getKey(15)
:End
:DispGraph
:Return
:
:Lbl PUS .Push algorithm
:ReturnIf pxl-Test(r1,r2) .only push if the pixel is white
:If D-357 .if stack isn't full yet
:r1→{D*2+L1} .add to stack
:r2→{D*2+1+L1}
:D++ .increment stack pointer
:sub(CHKr,r1,r2) .check if pixel is black on the back buffer, if yes, remove it there
:Else!If pxl-Test(r1,r2,GDB1) .if stack is full, make sure that the pixel isn't in memory yet
:Pxl-On(r1,r2,GDB1) .turn it on on the back buffer
:S++ .increment buffer size
:End
:Return
:
:Lbl POP .Pop algorithm
:If D .if there's something on the stack
:D-- .decremt stack pointer
:{D*2+L1}→P .get the coordinates from the stack
:{D*2+1+L1}→Q
:CHK(P,Q) .check if pixel is black on the back buffer, if yes, remove it there
:Else .if stack empty
:For(Q,0,63 .go on searching the back buffer (slow...)
:For(P,0,95
:If pxl-Test(P,Q,GDB1) .if you got a pixel
:Pxl-Off(P,Q,GDB1) .turn it off
:S-- .decrement the buffer size
:Return .return to main
:End
:End
:End
:End
:Return
:
:Lbl CHK .check algorithm
:If pxl-Test(r1,r2,GDB1) .check if pixel is black on the back buffer
:Pxl-Off(r1,r2,GDB1  .if yes, remove it there
:S-- .decrement the buffer size
:End
:Return
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on April 04, 2012, 04:41:11 pm
Wow, very nice way to combine the two methods. That should indeed be faster! I was limited to just one 768 byte buffer because I had to use the other two for grayscale. Again, nice o.o
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: MGOS on April 04, 2012, 04:51:12 pm
What about using an arbitrary buffer in the program file? I'm gonna have grayscale too, but I think I can afford having that buffer.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: Xeda112358 on April 04, 2012, 04:56:54 pm
Yah, and also, if you really wanted to, you could use your method, but instead:
1) Use one buffer for the backup buffer (in case the stack overflows)
2) Use the other two for gray
3) Use some code to figure out how much RAM is left and then create a tempstring (or TempProg or appvar) with the remaining RAM to use as a stack.
Then, if the user has lots of available RAM, their flood filling will be really fast, but in case they don't have enough they won't need to worry.
Title: Re: Fixed-Memory Flood Fill Pseudocode
Post by: MGOS on April 04, 2012, 05:02:34 pm
That's actually an interesting thought...  ::)
Maybe I'll add that later... firstly, my next step is to get the main program working, and then we'll see.