Core Dump - Work In Progress

## January 13, 1998 : Aiming bullets

In most games, there are things that shoot at you (the player). When you are the coder, you decide how this works. But there arent's many options.

Let's suppose that our bullet-firing meanie is at the center of a grid, at (0,0), and that the grid orientation is as usual. (Note that this is different from the MSX-situation, where the Y axis runs from top to bottom, which is exactly opposite to the usual situation.)

Now the player is at (PX,PY), and the meanie wants to fire a bullet at the player. First he calculates the angle of the player:

angle=ATAN (py/px)

The bullet has to be fired in that direction. Now we have to move the bullet. Let's assume it has speed S. At time T, the bullet is at the following location:

BX=T*S*COS(angle)
BY=T*S*SIN(angle)

So far for the theory. It's really a polar coordinate conversion, but that doesn't matter. What matters is, is that although this aiming is perfect in theory, your MSX has a bit of a problem with it. In fact, all (regular) computers use approximations of sinus/arctangent functions.

Doing this on an MSX

The sinus/cosinus isn't a problem, because you can just use a table for the function y=sin(x) whith 0 <= x < .05 PI. If you introduce a new unit for angle, with has 256 degrees in a circle, you only need to store 64 values, and that's enought to compute all sinus/cosinus data. And it can be done really quickly.

But the arctangent poses a new problem, for it cannot be computed so easily. The reason for this is the fact that the domain of the function is all real numbers. With the (co)sinus function, we could reduce the actual domain to [0, 0.5 PI], and store only discrete steps (64 to be exact).

Konami's ATAN

Let's have a look at the professionals, and get your dissassembler working on Metal Gear (I). Maybe you noticed that sometimes, the guards' bullets miss you, even when you're not moving. This would indicate that the are using some estimated value.

Investigation learns that they use a function which looks a bit like this:

angle=ATAN(y/x)
they use a help function (table):
angle=HELP(int(x/16),int(y/16)

First, the convert negative x or y values into positive ones. This is stored, and used afterwards to generate the correct angles from the table value retrieved. (But someone with a bit of feeling for maths can easily reconstruct that). X and y are pixel distances, so the won't exceed 255. Divide them by 16, and the are in the range of 0..15. The "HELP" table thus contains 256 values. Using this method, the arctangent function is computed in O(1) time, which means pretty fast. And it means that it can be used in an MSX game, most of the time...

But this is obviously an approximated value, because this aiming routine thinks that all pixels in a 16 by 16 block are at the same angle! That's why the guards sometimes miss. But there is a really amusing way to improve on this, without increasing the table size!

Aiming in Black Cyclon

In Black Cyclon, I used a method quite like the one Konami used, but with one big improvement. The new arctangent function becomes more accurate as the target gets closer. This is just like in real life aiming, so that makes it perfect for a game.

Recall that the table contained 16x16 values, and that the pixel offsets were in the range of [0..255]. Now, suppose that PX and PY are both less than 128, and this in the range [0..127]. For this range, we could use the table in the way we used it for [0..255], but we only need to divide by 8! So for x<128 and y<128, the arctangent becomes:

angle=HELP(int(x/8),int(y/8)

In other words, for x<128 and y<128, all pixels in an 8 by 8 pixel block are considered at the same angle! Thus, we have increased the "resolution" of our arctangent by a factor of two.

This trick can be used on lower levels. In fact, when a bullet is fired to a pixel with (x<16, y<16), the resoltion really is one pixel unit, which is the most accurate you can get. I will now present the algorithm in pseudo-C code (although I will use Z80-like bit operators):

```int atan(unsigned int x, unsigned int y)
{
if (x==0 || y==0) return HELP(x/16,y/16);

while (bit(7,x)==0 && bit(7,y)==0)
{
x=2*x;
y=2*y;
}
return HELP(x/16,y/16)
}
```

Note that the "x=2*x" commands can be implemented by logical shifts, and these are also really quick on any computer. I left out the bit about "when x or y is negative", and "how to create the HELP table", but I'll leave this as an exercise to the reader (BIG grin)

Anyway, this all leaves you with a really quick arctangent routine (time complexity O(1)), which is not too difficult to implement an MSX.

Why weren't there aiming bullets in Akin?

Speed wasn't the problem, with these routines. You can use the pixel version just as well on the 8x8 block scroller for computing angles...

And that is where new the problem arises. If you would fire a bullet at an angle of, say, 35 degrees, it would look really awful, because the bullet will seem to "jump" from one 8x8 block to another. Because of the scroll, sprites also move on an 8x8 pixel block grid, but that means aimed bullets can look quite dreadful. So I didn't use that in Akin.

But it will be done in Core Dump, because this last problem was solved. Sjees... I can hardly wait for the next entry!