Plotting a Trajectory in Machine Language

[Schema]

I'm reasonably familiar with 6502 ML, but one big gap in my understanding is how to do floating-point math of any complexity.

For example - I have an idea for an "artillery duel"-type of game written entirely in ML. I have a pretty good idea about how I'd do every single aspect of it except calculating the bullet's trajectory.

I know exactly how I'd go about it in C. In fact, I wrote a function in about 5 minutes to do it (see below).

But I don't even know where to begin to do this in ML. Since the inputs are arbitrary, lookup tables aren't an option. And I'd prefer "sub-pixel resolution" for smooth motion. Does Artillery Duel do this?

I thought of writing just this section in C with CC65 and use it as a binary blob, but CC65 doesn't support floating point.

Can anyone help?

Code: Select all

void main(void)
{	
	trajectory(0,200,45,55);  //Bottom-left of screen, 45 degrees up, half power
}

void trajectory(int startx, int starty, int degrees, int speed)
{
	// (TODO, check valid input)

	// Current object position
	float curx = (float)startx;
	float cury = (float)starty;

	//Object speed
	float fspeed = (float)speed/100.0;

	// Convert degrees input to radians
	float radians = (float)degrees * PIby180;

	// Break speed into component vectors
	float dy =-fspeed * cos(radians);   // -ve because "up" is -ve
	float dx = fspeed * sin(radians);

	while(1)
	{
		// Display on screen
		plot((int)curx, (int)cury);		

		// Move the object
		curx += dx;
		cury += dy;

		// TODO: Check for collision

		// Check for out of screen
		if ((curx > 320) || (curx < 0) || (cury > 200) || (cury < 0))
		{
			printf("Out of bounds!\n");
			return;
		}

		// Simulate gravity
		dy += 0.00098;
	}
}

[bbell]

Hmm... Maybe tying into the BASIC ROM for doing the calculations would be the lowest memory option. I have seen floating point routines out there for the 6502, but none that have sine/cosine.

Here is one example:

http://www.6502.org/source/floats/wozfp1.txt

I do have a copy of "Mapping the VIC". If you want, I will dig up the entry points for the various routines...

[nippur72]

In the "ROM calls and other tricks" message
http://sleepingelephant.com/ipw-web/bul ... .php?t=676

it's explained how to do floating point operations using the basic rom kernel routines. They are quite easy to use once you understand how to put floating point numbers into FAC and AFAC. I guess they are fast enough for an artillery game.

If speed is a problem, you can write your game in fixed-point math. There are several ways to simulate fixed-point math. A simple one is to assume that your bits don't range from 2^7 to 2^0 but (for example) from 2^5 to 2^0, and from 2^-1 to 2^-2 (so to have 0.25 steps). Converting to normal integers is done simply with LSRs. Anyway you have to write routines for multiplication, inversion and sin and cos (some effort is required).

[AndyH]

This might be along the lines that Nippur is suggesting, but in 68000 assembler, I always used to make a sine table which was bit shifted left to be a whole number. The more entries in your table the larger the precision but you just look up your offsets and work with integer values for your X, Y, etc (left bit shifted too).

I found this on a quick search for multiplication (link).

I've not started on any 6502 myself yet, would be interested in hearing how you get on.

[nippur72]

In fixed point math the fractional bits can be stored in a separate byte for a quicker conversion (a simple discard of the fractional byte).

As regards the multiplication, one effective way is to use the so called "Russian Peasant Multiplication" which involves addition and shifting operations only.

Sin and Cos can be calculated without lookup tables by expanding the Taylor series upto a given term (depending on precision). Unfortunately the series requires the calculation of 1/x which is another algorithm.

I would look at http://www.6502.org, I'm sure there is something already done.

[Mike]

You can compute both sin() and cos() with the CORDIC algorithm. This algorithm only needs a small table of arctan() values, and computes one bit of the result with each iteration, without any multiplies.

Here's the Wikipedia article on CORDIC.

Greetings,

Michael

[Schema]

Thanks for the detailed replies everyone. Lots of ideas. Fixed point math was suggested on another forum too, and it seems easiest to implement.

Plus I can make some simplifying assumptions:

The "degrees" input can be limited from 0-90 and always an integer. So a lookup table for SIN and COS is possible, with the result always a byte (representing 256 steps between 0 and 1). SIN and COS always return 0-1 in the range 0-90 degrees anyway.

Similarly "speed" can be limited to be a single byte.

Therefore, the only multiplication I'm doing - speed times the sin or cos of the speed input (to get my starting vectors) - becomes a much simpler problem of multiplying two bytes together, resulting in a 16-bit value. Found some code here that does just that.

[nippur72]

the russian peasant multiplication is very simlpe to implement. it is something like this:

Code: Select all

10 INPUT A,B
20 IF A=0 THEN 70
30 IF A AND 1 THEN C=C+B
40 A=INT(A/2)
50 B=B*2
60 GOTO 20
70 PRINT C

as you can see, only additions, shifts and bit tests. Loop complexity is also O(LOG N).

[Schlowski]

Need an example? Here is my 8bit x 8bit Multiplication, very short in code-terms and should be fast enough for your problem...

Code: Select all

; ---------------------------------------------------------------------	
; 8x8 Bit Multiplication
;
; Input: Byte1 in Val1
;          Byte 2 in Val2
;
; Output: Erg
; ---------------------------------------------------------------------	
Mul8:
    lda  #$00
    ldy  #8
Mul8Lp: 
    asl	
    rol  Val1
    bcc Mul8L1
    clc
    adc  Val2
    bcc  Mul8L1
    inc  Val1
Mul8L1:
    dey
    bne  Mul8Lp
    sta  Erg
    lda  Val1
    sta  Erg+1
    rts

[Schema]

OK, here's what I've come up with. Actually runs on a Commodore 64 though Works pretty well! There's no bounds checking yet so it keeps falling...and falling... You'll see it follows the C code pretty closely.

One thing I need to fix up is the "power" input to give more range. I can just scale down the resulting speed vectors to do that though. Tweaking to the animation speed is needed too.

Any comments?

Code: Select all

sprite8x EQU $D00E
sprite8y EQU $D00F

;Some test code

    processor 6502    
    org $1000


    jsr multiplysetup
    
    ;Show sprite #8
    lda #$80
    sta $D015
    
    ; Note decimal inputs
    lda #100
    sta startx
     
    lda #200
    sta starty
    
    lda #45
    sta angle
    
    lda #1 ;#55
    sta power
    
    jsr trajectory    
    rts


;------------------------------------------------------------------------------
; Input Parameters

startx  
    .byte $00
  
starty
    .byte $00  
     
angle  ;degrees
    .byte $00
     
power
    .byte $00

;------------------------------------------------------------------------------ 
; Lookup tables for SIN/COS, from lookup.xls

sinbyte 
    .byte 0,4,8,13,17,22,26,31,35,39,44,48,53,57,61,65,70,74,
78,83,87,91,95,99,103,107,111,115,119,123,127,131,135,138,142
,146,149,153,156,160,163,167,170,173,177,180,183,186,189,192,
195,198,200,203,206,208,211,213,216,218,220,223,225,227,229,
231,232,234,236,238,239,241,242,243,245,246,247,248,249,250,
251,251,252,253,253,254,254,254,254,254,255

cosbyte 
    .byte 255,254,254,254,254,254,253,253,252,251,251,250,249,248,
247,246,245,243,242,241,239,238,236,234,232,231,229,227,
225,223,220,218,216,213,211,208,206,203,200,198,195,192,189
,186,183,180,177,173,170,167,163,160,156,153,149,146,142,138
,135,131,127,123,119,115,111,107,103,99,95,91,87,83,78,74,70
,65,61,57,53,48,44,39,35,31,26,22,17,13,8,4,0

;------------------------------------------------------------------------------
; "Variables"

curx  ;X-position
  .byte $00,$00   ; First byte is "fraction", second byte is "integer"
  
cury  ;Y-position
  .byte $00,$00   ; First byte is "fraction", second byte is "integer"
  
fspeed ;Scaled initial speed
  .byte $00

dy ; Y component of current speed  
  .byte $00,$00   ; low/high, as above

dx ; X component of current speed
  .byte $00,$00   ; low/high
 

;------------------------------------------------------------------------------
; "Function"

trajectory  
    ; (TODO, check valid input)
    
    ; Current object position - 16 bits
    lda startx
    sta curx+1
    lda #$00
    sta curx
    
    lda starty
    sta cury+1
    lda #$00
    sta cury
    
    ; Object speed
    lda power
    sta fspeed
       
    ; Break speed into component vectors - Y
    ldx angle
    lda cosbyte,x  ; Get cos(angle) from lookup table
    ldy fspeed  	
    jsr multiply8x8
    stx dy     ; Low byte
    sta dy+1   ; High byte
    
    ; Break speed into component vectors - X
    ldx angle
    lda sinbyte,x  ; Get sin(angle) from lookup table
    ldy fspeed
    jsr multiply8x8
    stx dx     ; Low byte
    sta dx+1   ; High byte
    
    ; Negate dy because "up" is negative on the screen  
    ; 16 bit Binary Negation
    SEC             ;Ensure carry is set
    LDA #0          ;Load constant zero
    SBC dy+0        ;... subtract the least significant byte
    STA dy+0        ;... and store the result
    LDA #0          ;Load constant zero again
    SBC dy+1        ;... subtract the most significant byte
    STA dy+1        ;... and store the result

trajloop
	
  	; Display on screen
  	ldx curx+1 ; high byte
  	ldy cury+1 ; high byte
  	stx sprite8x
  	sty sprite8y

    ; Slow the action down so we can actually see it
    ldy #$00
slowdown
    nop
    nop
    nop
    nop
    nop
    nop
    dey
    bne slowdown
     	
  
  	; Move the object - 16-bit addition
    ; X component    
    clc
    lda curx 
    adc dx
    sta curx    
    lda curx+1
    adc dx+1
    sta curx+1
    
    ; Y component
    clc
    lda cury 
    adc dy
    sta cury    
    lda cury+1
    adc dy+1
    sta cury+1
    
    ; TODO Check for collision

    ; TODO check for out of bounds 
    
    ; Simulate gravity
    inc dy       ; Smallest possible, may need to tweak
    bne endloop  ; dy (low byte) did not wrap around to zero
    
    inc dy+1     ; increment the high byte
    
endloop
    jmp trajloop

This is DASM format. http://www.atari2600.org/DASM/

multiply8x8 is from here http://www.6502.org/source/integers/fastmult.htm

[Mike]

OK, here's what I've come up with. Actually runs on a Commodore 64 though

As long as you remember that the VIC also has a nice 160x192 hi-res mode which could be put to use, everything's o.k.

You can draw a nice landscape, with the two cannons. At that scale, the bullet isn't more than a single dot anyway. Collision detection is easy. If it hits another pixel, erase a filled circle around that to simulate the impact. Then check, whether all pixels of your and the enemies cannon are still present.

Tweaking to the animation speed is needed too.

Raster or timer. As always.

Greetings,

Michael