High resolution vector engine

[TROGDOR]

After a lot of experimentation, I've finally come up with a high resolution vector system for missiles. Here's what the code looks like:

 

	LDA #%00000001		; Using every other frame for plasma ball to slow it down.
AND Frame
BEQ UpdateMissle1

LDA #%00001110		; Because we're using every other frame.
AND Frame
LSR
TAX
LDA FrameBitMask,X
STA Temp1		; Temp1 holds the mask.

LDX PlasmaBallDir

LDA Vector,X
AND Temp1
BEQ NoPlasmaXMove

INC BallX

NoPlasmaXMove
LDA PlasmaBallDir
EOR #%00001111
TAX
INX			; Add 1 because the X map is slightly offset from Y.

LDA Vector,X
AND Temp1
BEQ NoPlasmaYMove

INC BallY

NoPlasmaYMove

 

; Associated data tables

 

FrameBitMask

.byte #%10000000

.byte #%01000000

.byte #%00100000

.byte #%00010000

.byte #%00001000

.byte #%00000100

.byte #%00000010

.byte #%00000001

 

; This table shows the destinations for the 16 angles after 8 frames have passed.

; The +'s are main angles (4 per quadrant). The origin is in the bottom left.

 

;012345678

;+ooo.....8

;...+oo...7

;.....o+..6

;......oo.5

;.......o.4

;.......+o3

;........o2

;........o1

;o........0

 

Vector

.byte #%00000000 ; shot 0

.byte #%00000001

.byte #%00010001

.byte #%00100101

.byte #%00100101 ; shot 1

.byte #%01010101

.byte #%11011010

.byte #%11011010

.byte #%11101110 ; shot 2

.byte #%11101110

.byte #%11111110

.byte #%11111110

.byte #%11111110 ; shot 3

.byte #%11111111

.byte #%11111111

.byte #%11111111

.byte #%11111111

 

This was written for Stellar Fortress, but it can be used in any game that requires a large number of angles for missile vectors. The above model supports 16 directions per quadrant, with 4 quadrants, for a total of 64 directions.

 

Its main purpose is to save RAM. Common high-resolution motion systems require 5 bytes of RAM:

 

XHi

XLo

YHi

YLo

MissileDir

 

By encoding the motion deltas into ROM, you can save 2 bytes of RAM by using 8 bit values for position instead of 16, but still provide the appearance of high-resolution motion.

 

X

Y

Missile Dir

 

Another important factor is applying trigonometric constraints. This means slowing the missile down on diagonal motion. When the missile is traveling horizontally or vertically, it moves one pixel per frame. But if it is traveling at a 45 degree angle, it should move (square root of 2) / 2 pixels per frame, which is less than one.

 

The motion is achieved by encoding a series of 8 deltas into a lookup byte. Each bit of the byte represents one frame. So, if the missile is traveling horizontally, it would use #%11111111, to represent that the missile should move one pixel to the right on every frame. If the missile is traveling at 45 degrees, it uses #%11101110. This is 6 pixels for every 8 frames. 3/4 is approximately (square root of 2) / 2 = 0.707

 

Another feature is the fact that the trig tables are almost symmetrical. To get the Y table, I just EOR the index and add 1, then reuse the X table, so only 16 bytes of ROM are needed to define the table.

 

The above code only supports one quadrant. I'm now working on enhancing it to support all 4 quadrants. The result will be in the next Stellar Fortress WIP release.

 

This code is similar to version 0.20 of Stellar Fortress. But in that version, I was using 16 bits for each angle to define 16 frames, then switching the lookup byte on every other frame. This required a larger ROM table and resulted in some ugly code, so I compressed it down to 1 byte per angle, but it still supports the same 16 directions per quadrant.

 

As a side note, 64 directions may seem excessive for an Atari 2600 game, but there are instances where it is necessary. For this particular game, I need all these angles to ensure that the cannon can hit the player ship at any location on the screen. With only 16 directions, I found there were safe zones where the player could park his ship and the cannon would never be able to hit it.

 

I'm guessing the programmer for the original Star Castle may have run into the same safe zone problem. This is probably where the idea for the expanding cannon attack came from.

Edited February 3, 2008 by TROGDOR

[supercat]

The motion is achieved by encoding a series of 8 deltas into a lookup byte. Each bit of the byte represents one frame.

 

My usual experience with what I call "4089-style" fractional stepping (referring to a CMOS "rate multiplier" chip called the 4089) is that it's a decent approach but there are often some visible jitter artifacts. If you can keep track of one more bit of position data somewhere, (so that on selected frames you advance the thing by 1/2 pixel) that can help a lot.

[TROGDOR]

Can you clarify what you mean by visible jitter artifacts? I'm guessing you're referring to the case where the object moves right on one frame, then down on the next frame, rather than diagonally on a single frame. If that's what you mean, I agree that is a risk. However, with the method I've described, the programmer has full control over the exact path that will be taken for each of the angles, in terms of both time and location, so this problem can be avoided.

 

While I was researching the general problem of defining 8-bit vectors, I did some study on Bresenham's line algorithm. One of my earlier implementations attempted to use this algorithm, but it wouldn't work for diagonals because the algorithm assumes that there is always motion on one of the coordinate axis. I needed to slow down the diagonals to provide realistic motion (proper trigonometric ratios) which means constant motion cannot be assumed and it breaks the algorithm.

 

However, I did pick up something useful from that research. All the vectors that I define must follow the path of a proper Bresenham's line. This will prevent jittering. I haven't checked the vectors yet, but I will walk through them and iron out any poorly traversed diagonals. It may require me to individually define the X and Y deltas in ROM, but the extra 16 bytes is worth it to solve the problem.

 

As for the pause of travel on some frames, that is unavoidable, regardless of the implementation. Unless an object is moving at exactly 1 pixel per frame, there will be some degree of jerkiness to the motion. That's just the nature of the low-resolution beast.

Edited February 4, 2008 by TROGDOR

[supercat]

Can you clarify what you mean by visible jitter artifacts? I'm guessing you're referring to the case where the object moves right on one frame, then down on the next frame, rather than diagonally on a single frame. If that's what you mean, I agree that is a risk. However, with the method I've described, the programmer has full control over the exact path that will be taken for each of the angles, in terms of both time and location, so this problem can be avoided.

 

As a simple example, suppose that you have a path that is supposed to make a shot move one pixel to the right every four frames. Depending upon when the shot is fired, it may move right after the first frame, or not until the fourth. Thus, two shots that are fired consecutively on what should be the same path might in fact go on different paths.

[vdub_bobby]

I haven't looked closely at your code, but at first glance it looks very similar to the code I used (at supercat's suggestion) to control the motion of the elevators in Elevators Amiss without eating up too much RAM. The elevators have, IIRC, 64 possible speeds between 1.5 and 2.5 pixels per frame. Or something like that. It took a big table in ROM, which hurt in 4K, but RAM was tighter!

Went from 3 bytes of RAM per elevator (Yhi, Ylo, speed+direction) to 2 (Y & speed+direction).

 

It is a very slick way to handle sub-pixel speeds.