The thing about seeker missiles (or any sort of "move an entity directly toward another entity at a set speed) behavior is that it's not as simple to get right on the 6502. (at least if you care at all about performance and would like to get more than 1 frame per second in your game).
The reason why is because of trigonometry.
There are two parts to making good enemy-seeking missiles. First is to select which enemy to target (usually the closest, although you might have a priority system instead to that they always target the most dangerous enemy or something. For this post, I'll assume we're targeting the closest enemy)
The way you'd do this on modern hardware is by first finding the closest enemy by using the Pythagorean theorem -- distance is the square root of x2 * y2. You can even omit the square root if you only care about finding the closest -- just find the sum of squares of the x and y distances for each enemy, and the closest is the smallest.
Unfortunately, arbitrary multiplication is slow on the 6502. Without a multiply instruction, you're stuck adding in a loop, (or bit shifts for multiplications times a power of 2). If the x distance is 74, that means adding 74 to itself 74 times in a loop.
That would look something like this (squaring a single 8-bit value into a 16-bit value):
ldx val ;3 cycles
lda #0 ;2
sta result ;3
sta result+1 ;3 (11 cycles for loop setup)
:
lda result ;3
clc ;2
adc val ;3
sta result ;3
lda result+1 ;3
adc #0 ;2
sta result+1 ;3
dex ;2
bpl :- ;3 (24 per each time through loop)
;11 + (24 * 74) = 1787 cycles
I scribbled that down without checking it, so it may be off by 1 or something, but it's something like 6% of a frame just to do that single 74*74 calculation. Good luck trying to also do y2, then computing this for each possible enemy. So we need a better way.
To be honest, I haven't found a perfect solution for this. Luckily, for this part of the problem, we don't really have to be exact. If the missile targets an enemy that's not exactly the closest, I don't really care. So for this first step, I just compare x + y instead of x2 * y2. Sure, that overestimates how far away enemies are that are more diagonal from the missile, but ... I don't care.
The more interesting part is the second half of the problem. Doing the math to determine the X and Y components of movement to move the missile toward the target.
The easiest solution is just to move at full speed horizontally until your x component matches the target, and also move at full speed vertically until your y component matches the target. The problems with this are obvious though: the missile moves too quickly in a straight diagonal, until it gets even with the target in one dimension, then moves straight until it hits it. This is a fairly obviously ugly movement. It's fine in some cases, particularly if the entity is moving fast enough that you don't really pay attention to the movement itself. I used this method in Super Homebrew War when a player gets the "swap everyone's location" power. I didn't have the programmer time or rom space for something more complicated, so I just went with this. The swapping all happens so quickly that you don't really notice that it's ugly.
Another solution would be to use to a constant TIME instead of constant VELOCITY. If you assume that the missile will always take approximately a second to reach the target, you can divide the x distance into 64 pieces (dividing by 64 is fast with bit shifts), and divide the y distance into 64, and move each by that amount every frame. That will produce a nice even movement, BUT the speed will change based on the total distance traveled. A missile will take the same amount of time to reach enemy A as enemy B, which may be undesired.
But for Halcyon, I want things to look nice and polished, so I wasn't happy with either of the two previous solutions. So trigonometry it is.
For the arctan, I found a pre-written routine that does a pretty good fast estimation of arctan that was written by one Johan Forslöf. I don't pretend to understand the math behind it (he claims it simply "uses logarithmic division to get the y/x ratio and integrates the power function into the atan table"), but it does what I need it to do.
For sin and cos, the trick (like many things on the 6502) is just to use pre-computed tables. If you assume that the angle is a 1-byte value, then there are only 255 possible sin values you have to compute. So you can compute them ahead of time (using a python script or something similar), and just put them into your rom as a lookup table. The cartridge rom that I'm using for Halcyon has plenty of rom space, so a 255-byte table is no big deal. Then to compute the sin, you just look up the precomputed value for any angle. Table lookups are one of the things that the 6502 does best, so this is nice and fast:
ldx angle ;3
lda sinTable,x ;4 (7 cycles total)
For cosine, you can take advantage of the fact that cosine is just sine rotated by one quadrant, so you add (or is it subtract? I never remember) 64 from your angle and use the same table.
So with these tricks, you can have a pretty nicely functioning enemy-seeking missile, without using too much CPU time.
Now if I could only figure out why it's not working, and my missile is just bouncing along in a goofy-looking sine wave pattern.
No comments:
Post a Comment