This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.
Messages - ZippyDee
Pages: 1 ... 5 6 [7] 8 9 ... 51
91
« 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, 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 >.<
92
« on: February 09, 2012, 10:38:49 am »
welcome to Omnimaga!  GRAMMAR LESSON TIME! Hello! This is a pretty large community, so I am sure you will find folks with whom to discuss. (that is my second time I have ever intentionally used the word "whom" and I have no clue if I used it properly o.o )
You are using it correctly. "Whom" is an object; "who" is a subject. "Who are talking to?" is technically grammatically incorrect, because the subject is you, not the person you are talking to. Because of that error, the sentence ends with the word "with," which is a preposition. The sentence really should be "With whom are you talking?"
93
« on: February 08, 2012, 03:39:36 am »
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.29I 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
94
« on: February 06, 2012, 01:53:43 pm »
Well the current FZero engine only has 3 levels of grayscale, so that's why I only did 3.
95
« on: February 06, 2012, 04:53:41 am »
Semi-Parsing of certain types of "project" (like, if this is an Axe Source, do something fancy)
My understanding is that XDE was going to be an IDE for Axe programming, not necessarily for BASIC or Grammer or things like that...Not that it couldn't be that, I just don't think that's what it was intended to be...
96
« on: February 06, 2012, 04:31:10 am »
Reporting for duty! I'll give some sprites a go!
Also...this looks absolutely amazing. I was thinking about making a Fruit Ninja, but I couldn't think of a good control scheme. Yours is genius.
97
« on: February 05, 2012, 04:32:47 pm »
No, I think it is more logical. I considered that to be the order... I don't know that I ever used the Pt-Mask()r command though, so I wouldn't have figured it out.
98
« on: February 03, 2012, 06:34:48 pm »
NUGGET: this thread is for sprites to share, not show off.
With that approach, you won't get many sprites to be given here; Instead, by providing open sprites as well as example sprites, you can help others along with formulating their own, which is just as important to do, if not more important. The more people can then learn by example and become better, the more sprites in general you will have, some for example, some for sharing. I'll just say, it's a common thing done in the spriting world, and it's more influential and supporting to budding talented spritists than it is detrimental.
You can provide your examples wherever you want. The whole point of this thread is to have a compilation of sprites that are all available to be used. So someone could just look through this thread and find a sprite they needed without having to worry if it's okay to use or not. That's the issue that's going on here.
99
« on: February 03, 2012, 01:32:32 am »
That's the plan I've proposed anyway. I think it'd work like a charm. So as long as we've convinced the programmers that be, we're golden.
100
« on: February 01, 2012, 09:00:44 pm »
Well, the surface level would have some exclusive tiles, as would the underground and cloud. You can exclude those and have specific loading sets for each, saving a few spaces.
Example: Lava isn't found on the surface (as far as I've seen anyways  ), Cloud and CloudCactus are only in the clouds, and InfiniteFall isn't on the surface either. That brings it to 16 for the surface.
I made that suggestion earlier, as well when I first suggested we keep the tiles under 17.
101
« on: February 01, 2012, 06:58:55 am »
I thought some people might enjoy these.
102
« on: February 01, 2012, 01:24:32 am »
You could store the map using the basic grass/stone/sand terrain, and then when you loaded the level you could do the conversion required to update all the different sprites.
Yeah, I was just thinking about that, too. As long as we keep the number of "root" tiles to less than 17, we can still have as many sprite variations as we want for when it's loaded. That or you just change the tilemapper to look at nearby tiles when displaying a sprite
That was kind of my first suggestion there...And it would only have to look at nearby tiles if it were drawing a mountain tile anyway. EDIT: willrandship, there's more than that. Wheat Water Tree Stone Stairs Sapling Sand Rock Ore Lava InfiniteFall Hole HardRock Grass Flower Farm Dirt Cloud CloudCactus Cactus
103
« on: February 01, 2012, 01:16:18 am »
Well I was just thinking that if we could keep the number of tiles for each map type (air, top, underground) to at most 16 different tiles, we could cut the sizes of the maps in half for storage.
104
« on: January 31, 2012, 07:11:31 pm »
But then you'd have to be walking on trees in order to get to it...So it wouldn't look like that.
105
« on: January 31, 2012, 12:57:55 am »
Need a new avatar?
Why not Zoidberg?
Pages: 1 ... 5 6 [7] 8 9 ... 51
|
Show Posts