For a while now I've been thinking about writing a fixed-memory flood fill routine. I finally wrote one out....but it doesn't work. I'm not very good at using the wabbitemu debugger, so debugging this is turning into an incredibly difficult job for me. I was wondering if someone could help me look through this and see if they can't assist me in figuring out what's wrong. I can try to clarify any questions you have in any parts of the routines.

Note that this is mostly optimized for speed because of the inevitably slow speed of this flood fill method.

EDIT: I attached a screenshot of what it does right now if you just execute it.

EDIT2: I made some modifications to the routine, but it's still buggy. The screenshot is not entirely accurate anymore. Now is' basically doing the same thing, only to the right of pxl(10,10) rather than to the left of it...

EDIT3: Updated the explanation of how the "right hand rule" should be followed at the bottom of my pseudocode. It should make more sense now...

I wrote this routine based off of the fixed memory flood fill routine loosely described here:
http://en.wikipedia.org/wiki/Flood_fill#Fixed_memory_method_.28right-hand_fill_method.29

I first wrote up this pseudocode:
This algorithm:
http://en.wikipedia.org/wiki/Flood_fill#Fixed_memory_method_.28right-hand_fill_method.29

RULE = right
MARK = null
MARKDIR = null
FINDPASSAGE = false
-----

if 4 bounds painted
        paint cur
        stop
else if 3 bounds painted
        MARK = null
        FINDPASSAGE = false
        RULE = right
        paint cur
        move to open bound
        
//#######################    
else if 2 bounds painted
        if MARK == null && RULE == right
                MARK = cur
                MARKDIR = dir
                FINDPASSAGE = false
        else if cur == MARK
                if dir == MARKDIR
                        MARK = null
                else
                        RULE = left    //.....this stuff here is the "oh no I'm in a loop" stuff.
                        dir = MARKDIR
                        MARK = null
                        FINDPASSAGE = false
                        
        if MARK == null && RULE == right
                paint cur
        move based on RULE         //after moving
                                                //set "dir" to the next direction
                                                //according to RULE (right hand rule or left hand rule)

//######################
                
else if 1 bound painted
        if RULE == left  //then we're in a loop, and this triggers the second stage
                FINDPASSAGE = true
        else
                if both opposite corners are open && MARK == null
                        paint cur
        move base on RULE
else if 0 bounds painted
        if RULE == left
                FINDPASSAGE = true
        paint cur?
        move anywhere :P
        

========================================
   How do you follow the right hand rule? Which is next?

           (Key: _ = empty pixel, # = filled pixel, 0 = current position and direction)
if the corner is filled, just move forward
        ___
        _0_
        _##
...becomes...
        ___
        __0
        _##
but if the corner is empty, there are two possible ways to move
        ___
        _0_
        _#_
first possibility
        ___
        _#0        If the current pixel is painted before moving, move here
        _#_
second possibility
        ___
        ___        if the pixel is NOT painted before moving, move around the corner to the next edge
        _#0        because just going straight would make it now have no borders...



Based on that I wrote my assembly program, which is quite messy, I'm sorry to say...

#include    "ti83plus.inc"
#define     progStart   $9D95
.org        progStart-2
.db         $BB,$6D

;these are all flags used in the "bools" address. I didn't use one of the AsmFlags addresses, because that might be in use by whatever program uses this routine.
bool_color .equ 0 ;unused for now. only fills black.
bool_color2 .equ 1 ;unused for now
bool_rule .equ 2 ;set=right-hand rule,reset=left-hand rule
bool_findpath .equ 3 ;set if
bool_filled .equ 4 ;whether or not the current pixel has been filled. This is set when paintCur is called
bool_mark .equ 5 ;if reset, mark is null. otherwise, mark is in use. Used in the main loop


_init:
ld (save_iy),iy
ld iy,bools
ld hl,(cx)
call getPixel
and (hl)
ret nz ;quit if the current pixel is already filled
_main: ;main program loop.
call safecopy ;safecopy exists for testing purposes only.
res bool_filled,(iy)
ld hl,(cx)
call getEdgePixels
ld (bounds), a
;ld (PlotSScreen),a
call SumNibBits
ld b,a
djnz _not1
_1_bound:
bit bool_rule,(iy)
jr nz,+_
set bool_findpath,(iy)
jr ++_
_:
bit bool_mark,(iy)
jr nz,+_
ld hl,(OppCornMask_LUT)
ld d,0
ld e,(iy+off_cdir)
add hl,de
ld a,(bounds)
and (hl)
jr nz,+_
call paintCur
_:
call MoveByRule
_not1:
djnz _not2
_2_bound:
;if MARK == null && RULE == right
bit bool_mark,(iy)
jr nz,_2elseif
;MARK = cur
ld hl,(cx)
ld (mx),hl
;MARKDIR = dir
ld a,(cdir)
ld (mdir),a
;FINDPASSAGE = false
res bool_findpath,(iy)
set bool_mark,(iy) ;mark is not null
_2elseif:
;else if cur == MARK
ld hl,(cx)
ld a,(mx)
cp l
jr nz,_2if
;if dir == MARKDIR
ld a,(my)
cp h
jr nz,_2if
ld a,(cdir)
ld hl,mdir
cp (hl)
jr nz,_2else
;MARK = null
res bool_mark,(iy)
jr _2if
_2else:
;else
;RULE = left
res bool_rule,(iy)
;dir = MARKDIR
ld a,(hl)
ld (cdir),a
;MARK = null
res bool_mark,(iy)
;FINDPASSAGE = false
res bool_findpath,(iy)
call TurnByRule
_2if:
;if MARK == null && RULE == right
bit bool_mark,(iy)
jr nz,_move
bit bool_rule,(iy)
jr z,_move
;paint cur
call paintCur
;move based on RULE
_move:
call MoveByRule
jp _main
_not2:
djnz _not3
_3_bound:
res bool_mark,(iy)
res bool_findpath,(iy)
set bool_rule,(iy)
call TurnByRule
call paintCur
call MoveByRule
jp _main
_not3:
djnz _not4
_4_bound:
;4 bound
call paintCur
ld iy,(save_iy)
ret ;;QUIT
_not4:
_0_bound:
ld hl,cdir
ld (hl),0
call paintCur
inc hl
inc (hl) ;increase cx
jp _main



bools:
.db 0 | (1 << bool_color) | (1 << bool_color2) | (1 << bool_rule)
cdir: ;current dir. 0=down, 1=left, 2=up, 3=right
.db 0
cx: ;current x. Set to 10 for testing
    .db 10
cy: ;current y. Set to 10 for testing
    .db 10
mdir: ;mark dir
    .db 0
mx: ;mark x
    .db 0
my: ;mark y
    .db 0
bounds: ;holds the bound data
    .db 0 ;bit order: FAHCGDBE
;ABC ;here's how that order lines up with surrounding pixels
;DxE
;FGH
save_iy:
.dw 0

;I reference these using IY+* to load values into other registers. IY points to bools.
;Not all of these are used. In fact, I think only off_cdir is used.
off_cx .equ cx-bools
off_cy .equ cy-bools
off_cdir .equ cdir-bools
off_mx .equ mx-bools
off_my .equ my-bools
off_mdir .equ mdir-bools
off_bounds .equ bounds-bools


;masks for the pixel straight forward, based on dir
.db %00001000, %00000100, %00000010, %00000001
FrontByDirMask_LUT:
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %00001000, %00000100, %00000010, %00000001
.db %00001000, %00000100, %00000010, %00000001

OppCornMask_LUT: ;masks for the two opposite corners from the edges corresponding with FrontByDirMask_LUT
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %01010000, %00110000, %10100000, %1100000

FrontCornRightRuleMask_LUT: ;masks for corners forward/right, based on cdir
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %10000000, %0100000, %00010000, %0010000

FrontCornLeftRuleMask_LUT: ;masks for corners forward/right, based on cdir
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %00100000, %1000000, %01000000, %00010000

.db 1
DirMoveX_LUT: ;LUT for X offsets based on dir. Used in MoveByRule.
.db 0,-1,0
DirMoveY_LUT:
.db 1,0,-1,0


MoveByRule: ;move based on the rule. (this immediately goes into TurnByRule)
bit bool_filled,(iy)
ld e,(iy+off_cdir)
ld d,0
jr z,_moveforward
bit bool_rule,(iy)
ld b,d
ld c,1
ld hl,FrontCornRightRuleMask_LUT
jr z,+_
ld c,-1
ld hl,FrontCornLeftRuleMask_LUT
_:
ld e,(iy+off_cdir)
ld d,b
add hl,de
ld a,(bounds)
and (hl)
jr nz,_moveforward
ld hl,DirMoveX_LUT
add hl,de
add hl,bc
ld a,(cx)
add a,(hl)
ld (cx),a
inc hl
inc hl
inc hl
ld a,(cy)
add a,(hl)
ld (cy),a
_moveforward:
ld hl,DirMoveX_LUT
add hl,de
ld a,(cx)
add a,(hl)
ld (cx),a
inc hl
inc hl
inc hl
ld a,(cy)
add a,(hl)
ld (cy),a


TurnByRule: ;turn based on the rule.
ld hl,FrontByDirMask_LUT
ld d,0
ld e,(iy+off_cdir)
add hl,de
ld e,1
bit bool_rule,(iy)
jr nz,+_
ld e,-1
_:
ld b,(iy+off_bounds)
xor a
ld c,a
_frontloop:
;while front on, rotate opposite from rule
;check front
ld a,b
and (hl)
jr z,_sideloop
dec c
sbc hl,de
jr _frontloop
_sideloopskip:
inc c
_sideloop:
add hl,de
ld a,b
and (hl)
jr z,_sideloopskip
ld a,(cdir)
dec e
jr nz,_leftrotate
add a,c
and 3
ld (cdir),a
ret
_leftrotate:
sub c
and 3
ld (cdir),a
ret



SumNibBits:
;Thank you, Runer112, for this routine
;returns the sum of the lower 4 bits of A
;output: A = sum of bits
;destroys HL
and %00001111
ld hl,SumNibBits_LUT
add a,l
ld l,a
ld a,(hl)
ret nc
inc h
ld a,(hl)
ret
SumNibBits_LUT:
.db 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4
;.db 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5



getPixelByte:
;standard first part of a getPixel routine. Retrieves the byte of the pixel in HL
ld a,h
ld h,0
ld d,h
ld e,l
add hl,hl
add hl,de
add hl,hl
add hl,hl
ld e,a
srl e
srl e
srl e
add hl,de
ld de,PlotSScreen
add hl,de
ret

getPixel:
;just a getPixel routine. Nothing to see here.
call getPixelByte
and 7
ld b,a
ld a,$80
ret z
rrca
djnz $-1
ret

paintCur:
;fills the current pixel (cx,cy) and sets the "bool_filled" flag
ld hl,(cx)
call getPixel
or (hl)
ld (hl),a
set bool_filled,(iy)
ret

getEdgePixels:
;get all 8 surrounding pixels and put them into A in the order specified at the "bounds" label.
push hl ;save x,y for checking offset later
call getPixelByte
push hl
pop ix

and 7
jr z,_specLeft
cp 7
jr z,_specRight
dec a ;get the surrounding bits into the 3 msb of C, D, and E
ld b,a
ld d,(ix-12)
ld e,(ix+12)
ld a,(hl)
jp z,CheckOffScreen
ld c,b
ld a,e
rrca
djnz $-1
ld e,a
ld b,c
ld a,d
rrca
djnz $-1
ld d,a
ld b,c
ld a,(hl)
rrca
djnz $-1 ;d=ABC00000;a=DXE00000; e=FGH00000
ld c,a
jp CheckOffScreen
_specLeft: ;special-case for left-side overflow
ld d,(ix-12)
ld a,(ix-13)
rra
rr d
ld e,(ix+12)
ld a,(ix+11)
rra
rr e
ld c,(hl)
dec hl
ld a,(hl)
rra
rr c
jp CheckOffScreen
_specRight: ;special-case for right-side overflow
ld d,(ix-11)
ld a,(ix-12)
rl d
rra
rra
rra
ld e,(ix+13)
ld a,(ix+12)
rl e
rra
rra
rra
ld a,(hl)
inc hl
ld c,(hl)
rl c
rra
rra
rra
ld c,a

CheckOffScreen:
pop hl ;recall x,y
ld a,l
dec a
cp 62
jr c,_testx
jr z,_fixtop
jr _fixbtm
_fixtop:
ld e,%11100000
jr _testx
_fixbtm:
ld d,%11100000
_testx:
ld a,h
dec a
cp 94
jr c,EdgePixelCombine
jr z,_fixright
jr _fixleft
_fixright:
set 5,c
set 5,d
set 5,e
jr EdgePixelCombine
_fixleft:
set 7,c
set 7,d
set 7,e
EdgePixelCombine:
;Thank you, Runer112, for this routine
;d=ABC00000
;c=DXE00000
;e=FGH00000
ld a,c
xor d
and %10111111
xor d ;a=DBE00000
rlca
rlca ;a=00DBE000
xor e
and %10111111
xor e ;a=0GDBE000
rrca
rrca ;a=000GDBE0
xor d
and %01011111
xor d ;a=ABCGDBE0
rrca ;a=0ABCGDBE
xor e
and %01011111
xor e ;a=FAHCGDBE
ret






;-----> Copy the gbuf to the screen, guaranteed
;Input: nothing
;Output:graph buffer is copied to the screen, no matter the speed settings
;
;in f,(c) is an unofficial instruction.
;It must be noted that you cannot specify any other register. Only f works.
;You may have to add it in order for the routine to work.
;if addinstr doesn't work, you may manually insert the opcodes .db 0EDh,070h

 .addinstr IN F,(C) 70ED 2 NOP 1

SafeCopy:
;di                 ;DI is only required if an interrupt will alter the lcd.

ld hl,PlotSScreen  ;This can be commented out or another entry placed after it
                           ;so the buffer can be provided by option.
ld c,$10
ld a,$80
setrow:
in f,(c)
jp m,setrow
out ($10),a
ld de,12
ld a,$20
col:
in f,(c)
jp m,col
out ($10),a
push af
ld b,64
row:
ld a,(hl)
rowwait:
in f,(c)
jp m,rowwait
out ($11),a
add hl,de
djnz row
pop af
dec h
dec h
dec h
inc hl
inc a
cp $2c
jp nz,col
ret