Fixed-Memory Flood Fill debugging

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:

Code: Select All | Copy To Clipboard

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

Code: Select All | Copy To Clipboard

#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