Floodfill
Материал из SpeccyWiki
Версия от 01:12, 8 августа 2017; Maksagor (обсуждение | вклад)
Алгоритм основан на коде(Basic):
5 REM AUTHOR UNKNOWN
10 CIRCLE 128,88,80
20 LET x=100 : LET y = 100 : REM START POINT
30 GO SUB 1000 : STOP
1000 PLOT x,y
1010 IF NOT POINT(x+1,y) THEN LET x=x+1 : GO SUB 1000 : LET x=x-1
1020 IF NOT POINT(x-1,y) THEN LET x=x-1 : GO SUB 1000 : LET x=x+1
1030 IF NOT POINT(x,y+1) THEN LET y=y+1 : GO SUB 1000 : LET y=y-1
1040 IF NOT POINT(x,y-1) THEN LET y=y-1 : GO SUB 1000 : LET y=y+1
1050 RETURN
Alvin Albrecht в статье "A Fast Well-Behaved Pattern Flood Fill" предложил ускоренный вариант, теперь в экранной области не сканируется каждая точка, а заполняется значением #ff, если байт нулевой. исходники в статье содержат неточности, поэтому приводится дизассемблированный текст.
Входные параметры: hl=YX координаты точки заливки области.
fill:
ld bc, 64h
call sub_800B
ret
; =============== S U B R O U T I N E =======================================
sub_800B:
ld a, h
cp 0C0h
ret nc
dec bc
push bc
call sub_80F9
ex de, hl
call sub_814B
jr c, loc_801C
pop bc
ret
loc_801C:
ld ix, 0FFFFh
add ix, sp
push hl
push bc
inc sp
xor a
push af
dec sp
ld c, (ix+1)
ld b, (ix+2)
inc bc
ld l, c
ld h, b
add hl, bc
add hl, bc
ld c, l
ld b, h
ld h, a
ld l, a
sbc hl, bc
add hl, sp
ld (hl), a
ld sp, hl
ld a, 80h
push af
inc sp
ld e, l
ld d, h
inc de
dec bc
ldir
push ix
pop bc
ld hl, 0FFFAh
add hl, bc
ex de, hl
ld l, c
ld h, b
loc_8050:
ld a, (hl)
cp 80h
jr c, loc_8059
push ix
pop hl
ld a, (hl)
loc_8059:
cp 40h
jr c, loc_80B8
ld b, a
dec hl
ld c, (hl)
dec hl
ld a, (hl)
dec hl
inc (ix+1)
jr nz, loc_806B
inc (ix+2)
loc_806B:
push hl
ld l, c
ld h, b
ld b, a
push hl
call sub_8120
jr c, loc_807D
push bc
call sub_814B
call c, sub_80D3
pop bc
loc_807D:
pop hl
push hl
call sub_8135
jr c, loc_808C
push bc
call sub_814B
call c, sub_80D3
pop bc
loc_808C:
pop hl
bit 7, b
jr z, loc_80A3
push hl
ld a, l
dec l
and 1Fh
jr z, loc_80A2
push bc
ld b, 1
call sub_814B
call c, sub_80D3
pop bc
loc_80A2:
pop hl
loc_80A3:
bit 0, b
jr z, loc_80B5
inc l
ld a, l
and 1Fh
jr z, loc_80B5
ld b, 80h
call sub_814B
call c, sub_80D3
loc_80B5:
pop hl
jr loc_8050
loc_80B8:
dec hl
dec hl
dec hl
ld a, (de)
cp 80h
jr c, loc_80C3
push ix
pop de
loc_80C3:
xor a
ld (de), a
dec de
dec de
dec de
ld a, (hl)
cp 40h
jr nc, loc_8050
ld sp, ix
inc sp
inc sp
inc sp
ret
; =============== S U B R O U T I N E =======================================
sub_80D3:
push hl
ld l, (ix+1)
ld h, (ix+2)
ld a, h
or l
jr nz, loc_80E0
pop hl
ret
loc_80E0:
dec hl
ld (ix+1), l
ld (ix+2), h
pop hl
ld a, (de)
cp 80h
jr c, loc_80F0
push ix
pop de
loc_80F0:
ex de, hl
ld (hl), d
dec hl
ld (hl), e
dec hl
ld (hl), b
dec hl
ex de, hl
ret
; =============== S U B R O U T I N E =======================================
sub_80F9:
and 7
or 40h
ld d, a
ld a, h
rra
rra
rra
and 18h
or d
ld d, a
ld a, l
and 7
ld b, a
ld a, 80h
jr z, loc_8111
loc_810E:
rra
djnz loc_810E
loc_8111:
ld b, a
srl l
srl l
srl l
ld a, h
rla
rla
and 0E0h
or l
ld e, a
ret
; =============== S U B R O U T I N E =======================================
sub_8120:
ld a, h
dec h
and 7
ret nz
ld a, 8
add a, h
ld h, a
ld a, l
sub 20h
ld l, a
ret nc
ld a, h
sub 8
ld h, a
cp 40h
ret
; =============== S U B R O U T I N E =======================================
sub_8135:
inc h
ld a, h
and 7
ret nz
ld a, h
sub 8
ld h, a
ld a, l
add a, 20h
ld l, a
ret nc
ld a, h
add a, 8
ld h, a
cp 58h
ccf
ret
; =============== S U B R O U T I N E =======================================
sub_814B:
ld a, b
xor (hl)
and b
ret z
ld b, a
loc_8150:
rra
ld c, a
ld a, b
add a, a
or c
or b
ld c, a
xor (hl)
and c
cp b
ld b, a
jp nz, loc_8150
or (hl)
ld (hl), a
scf
ret
ссылки: http://en.wikipedia.org/wiki/Flood_fill
http://wos.meulie.net/pub/spectrum/games-info/f/FastWell-BehavedPatternFloodFillA.doc (статья содержит подробную статью о структуре экранной области, приведены исходные тексты Basic.) http://www.timexsinclair.org/alvin/tidbits/fillprogs.zip (.TAP-файлы пример программ на Basic, статья ссылается на архив)
