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, 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:

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 >.<

Here's a link to the flash file I made to debug this algorithm.

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.

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.

Hmm, maybe I should rewrite my JavaScript minesweeper to use a better algorithm.
I just made mine form scratch, so its probably not efficient.

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 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.

I am working on converting this algorithm to z80 assembly, so I thought I would post some screenshots.

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.