bresenham line routine for sprites tracking???

[Heaven/TQA]

guys, for my highscore routine i want to have some "flying chars"... similar to the highscore table of bounty bob strikes back (where the birds are picking up chars and putting them on the right position on the table...)

 

i dug into my source archives but haven't found a generic line routine anymore (all seem to be optimised for this or that effect)...

 

so i reimplemented the bresenham algorithm directly from my lovely book "computer graphics: principle and practice" by foley, etc...

 

BUT this one works for the case x1>x0 and y1>y0... but i want to have a sprite bouncing in sine waves on the bottom of the screen and "out of his mouth" the chars will fly to their desired positions. so here are my questions:

 

a) where can i find a generic line algorithm? of course without any divs and muls

b) is it 100% correct to set the sprite (like setting pixels) every VBL? could it not be that in some cases the slope is greater than 1 pixel so actually my sprite had to move f.e. 2 pixels?

 

here is the code...

 

thanks guys...

 

* calculates the slope for moving chars in the highscore table

move_char lda x1  ;strictly bresenham algo

 	sub x0  ; dx=x1-x0

 	sta dx

 	lda y1  ; dy=y1-y0

 	sub	y0

 	sta	dy

 	clc

 	asl	@  ;d=2*dy-dx

 	sta	incre	;incre=2*dy

 	sub	dx

 	sta d

 	lda dy  ;incrne=2*(dy-dx)

 	sub	dx

 	clc

 	asl	@

 	sta	incrne

 	mva	x0	x	;x=x0

 	mva	y0	y	;y=y0



 	mva	x	x_pos

 	mva	y	y_pos

 	jsr	set_pm	;position sprite

* while x<x1

move_char0	lda d  ;if d<0 then choose incre

 	bpl	move_char1

 	add	incre	;d=d+incre

 	sta	d

 	inc	x  ;x=x+1

 	jmp move_char2;endif

move_char1	add incrne	;d=d+incrne

 	sta	d

 	inc x  ;x=x+1

 	inc y  ;y=y+1

move_char2	mva	x	x_pos;set sprite

 	mva	y	y_pos	

 	jsr	wait_vbl

 	jsr	set_pm;wait for vbl

 	lda	x

 	cmp	x1

 	bcc move_char0

 	rts

 	

incre  dta 0

incrne  dta 0

d  	dta	0

dx  	dta	0

dy  	dta	0

x  	dta	0

y  	dta	0

x0  	dta	0

y0  	dta	0

x1  	dta	0

y1  	dta	0

[/code]

[Sheddy]

2 little divides and you can avoid all that trouble

 

google seems to come up with quite a bit:

 

http://www.google.co.uk/search?q=bresenham...F-8&hl=en&meta=

 

Basically, the slope has to be less than 1 or the "decision" variable can't work. So you use the other axis. IE if y1-y0 > x1-x0 then y = y+1 every time, but if x1-x0 > y1-y0 then x = x+1 every time.

 

you may need to create different routines for the different directions the lines could go ie left to right, right to left, up to down, down to up etc. Or how about 2's complement for dealing with when your line goes the other way? There's nothing to stop the decision variable being negative, and replacing the inc's with a signed add.

 

I do something similar for the aliens' missiles in Space Harrier, although it has a few other wrinkles too - it's in the init_missile routine in the demo source code if you want to look.

 

[Edit] Oh, and you might want to see move_missiles too!

[Heaven/TQA]

thanks shaddy... i am just back from clubbing and had the same idea... in my intro "really unreal" i had signed additions (you find the source on www.uni-karlsruhe.de/~Marek.Tomczyk on the atari pages in the demo section)... but the code there was optimised for unreal...

 

then having some beers i had the simple solution with checking the starting points or the line direction + having signed maths doing the breseham...

 

i'll check that tomorrow night or on sunday as tomorrow i have mario kart double dash! session with my chaps...

 

hve

[EricBall]

This is a routine which should be fairly easy to translate to 6502 ASM.

 

drawline( x0, y0, x1, y1 )

ax = abs(x1 - x0)

ay = abs(y1 - y0)

sx = sgn(x1 - x0)

sy = sgn(y1 - y0)

cx = x0

cy = y0

vx = ay / 2

vy = ax / 2

if ax < ay then

 if ax == 0 then 

   vz = ay

 else 

   vz = ax

 endif

else

 if ay == 0 then

   vz = ax

 else

   vz = ay

 endif

endif

while cx != x1 or cy != y1

 plot(cx,cy)

 vx -= vz

 if vx < 0 then

   vx += ay

   cx += sx

 end if

 vy -= vz

 if vy < 0 then

   vy += ax

   cy += sy

 end if

wend

plot(cx,cy)

[Heaven/TQA]

eric, thanks. if my memories are not cheating me regarding my turbo pascal lessons 20 years ago... sgn(var) gives the sign of a value???

 

just to understand the source...

[EricBall]

sgn(x) = -1 x < 0

sgn(x) = 0 x == 0

sgn(x) = 1 x > 0

[Heaven/TQA]

here are my results... you'll find the complete project in the zip incl. xasm.

 

my feeling still says there is something wrong going on but at the moment it seem to work. (you'll see just random chars filling the "highscore table")

 

if anybody sees any erros any help is welcome...

 

hve/tqa

 

ps. music is done by Xray/tqa and uses just 3 channels so one channel is left free for sound fx... but i like this one to use it as highscore/game over tune...

 

 

* calculates the slope for moving chars in the highscore table

* works only if x1>x0 and y1>y0

move_char  mva	#1	xdir;default x moving direction

 	lda x0	;x0>x1?

 	cmp x1

 	bcc	move_char00

 	lda	#255

 	sta	xdir

move_char00	lda x1  ;strictly bresenham algo

 	sub x0  ; dx=x1-x0

 	sta dx

 	lda y1  ; dy=y1-y0

 	sub	y0

 	sta	dy

 	clc

 	asl	@  ;d=2*dy-dx

 	sta	incre	;incre=2*dy

 	sub	dx

 	sta d

 	lda dy  ;incrne=2*(dy-dx)

 	sub	dx

 	clc

 	asl	@

 	sta	incrne

 	mva	x0	x	;x=x0

 	mva	y0	y	;y=y0



 	mva	x	x_pos

 	mva	y	y_pos

 	jsr	set_pm	;position sprite

* while x<x1

move_char0	lda d  ;if d<0 then choose incre

 	bpl	move_char1

 	add	incre	;d=d+incre

 	sta	d

 	lda	x  ;x=x+xdir

 	add	xdir

 	sta	x

 	jmp move_char2;endif

move_char1	add incrne	;d=d+incrne

 	sta	d

 	lda	x  ;x=x+xdir

 	add	xdir

 	sta	x

 	dec y  ;y=y+1

move_char2	mva	x	x_pos;set sprite

 	mva	y	y_pos	

 	jsr	wait_vbl

 	jsr	set_pm	;wait for vbl

 	lda	x  ;destination postion reached?

 	cmp	x1

 	bne move_char0

* now put the char in the vram of the highscore table

     ;pos on screen = x div 8

 	sub	#48  ;center on screen

 	clc

 	lsr @  ;div 2

 	lsr	@  ;div 2

 	lsr	@  ;div 2

 	tay  	;store in Y



 	lda y_pos

 	sub	#16  	

 	clc

 	lsr @

 	lsr @

 	lsr @

 	tax  	;now get the vram adress

 	lda	linetabl,x

 	sta	v0

 	lda linetabh,x

 	sta	v0+1

 	lda char_no	;now put char on screen

 	sta	(v0),y

 	rts

 	

incre  dta 0

incrne  dta 0

d  	dta	0

dx  	dta	0

dy  	dta	0

x  	dta	0

y  	dta	0

x0  	dta	0

y0  	dta	0

x1  	dta	0

y1  	dta	0

xdir  dta	0

char_no  dta	0 

teaser3.zip