Floodfill

Материал из SpeccyWiki
Перейти к: навигация, поиск

Алгоритм основан на коде(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, статья ссылается на архив)