## Some programming tricks I’ve learned while playing with games

Above is a little video I made of a run of a game I’m working on, called wordwarvi. The latest things I’ve added to it are a radar screen at the bottom, and now, when you shoot things, as before, they blow up in a shower of sparks, but amid the sparks are also chunks of flaming debris which fly and bounce around the terrain.

I used some interesting programming techniques while programming the behavior of the heat seeking missiles in this game, and that’s what I want to write about today.

I made a few missteps along the way, but I think what I’ve got now does pretty well, in that it behaves more or less like a mostly plausible missile, and they aren’t so perfect in their pursuit as to make them unbeatable.

This is a 2D game, so the first thing to notice is that each object in the game has a location, an (x,y) coordinate, and a velocity, a (vx,vy) vector. These are all integer quantities, because this is a game, and it has to run fast. Floating point is usually an unaffordable luxury.

The game engine in this game is triggered by a timer which fires 30 times a second, and with each firing, the main game engine function is called. This function cycles through all the objects in the game, moving them, and drawing those which happen to be in a location which is on screen.

Movement, in the simplest sense, simply involves adding an object’s velocity vector to it’s location coordinates;

x = x + vx; y = y + vy;

With that bit of exposition out of the way, let’s get back to thinking about the heat seeking missiles.

The first problem that comes up is how to draw the missile. In this game, the missile is represented by a simple line. To draw a line requires two coordinates (x1,y1) and (x2,y2) between which a line is drawn (by Bresenham’s magical algorithm, but that is no doubt implemented in a library so you don’t usually have to worry about that — but knowing of it can come in handy if you ever need to say, examine the particular elements of a 2d array which lie on a particular line.) The missile should be drawn at an angle which matches its current velocity — so that it travels like an arrow, moves in a direction parallel to the line which represents it on screen. So, to draw this line, we need two coordinates. We have one of them, as we know where the missile is supposed to be. We’ll say that it’s coords, (x,y) are at the nose of the missile. We just have to figure out where tail of the missile is. We know how long the missile is (it doesn’t change length, and and we just make up how long it is, and make that a constant, say it’s 10), and we know what its velocity in x and y directions are, so we ought to be able to figure out where the tail of the missile is.

So, given (x,y), (vx,vy), and the missile’s length, 10, how do we find (x2,y2) such that the missile is 10 units long, and aimed in the direction that vx,vy are taking it?

I can think of a couple ways, and both use the properties of similar triangles.

Which is to say this equation must hold:

vx/vy == (x2 – x) / (y2 – y);

And this equation must hold:

(x2 – x)^2 + (y2 – y)^2 == 10^2 (pythagorean theorem).

Two equations, two unknowns, solve for the unknowns.

Another way, use trig:

We know that the angle which vx and vy imply must equal the angle which (x1 – x) and (y1 – y) imply (by similar triangles.) The tangent of an angle is the opposite/adjacent side of a triangle, and the angle is the arctangent of that number (correcting for quadrant of the circle, of course).

And we know the x component and y component of a line at a given angle and a given length can be found by multiplyting that given length by the cosine and sine of the given angle, respectively.

I chose the 2nd, trig based approach.

You might be surprised, thinking that this way, with floating point numbers, sine, cosine — *and freaking arctangent!* — wouldl be computationally more expensive than the algebraic approach.. You’re right, it probably is computationally more expensive. But it doesn’t matter.

The reason it doesn’t matter is because I don’t do all these calculations everytime I need them. The trick is to recognize that in a game, when velocities are represented by integers, and not just integers, *low* integers — because whatever value the velocity has, that’s roughly how many pixels the object jumps in each frame — it can’t be too high without looking jerky. Since the velocities are integers, and low integers, there is a finite *small* number of combinations of possible values for vx and vy. We can pre-compute the solutions to the above mess one time at the beginning of the game for all possible combinations of values of (vx,vy), and store these in a table for quick lookup. That is, in a “lookup table.” (long way to go to get to an old concept).

Actually, I didn’t pre-compute all possible values, just one quadrant, the positive values of vx, and vy, and the answers for the other quadrants are trivial to get, given those.

So that covers (in principle) how to draw the missile. Now, how to steer it?

The naive approach might be to find the differential x and y distances to the target object, and using similar triangles, set vx and vy proportional to that distance. That has the effect of making the missile always head directly for the target. Isn’t that what a heat seeking missile does?

No, not really.

Think about what happens if the player is headed due east, and the missile is headed due west on a near collision course. The player zips past the missile. It won’t do for the missile to instantly reverse direction. It’s got to at least sort of skitter around a bit and decellerate, and then accellerate in the new direction.

To accomplish that, I compute a *desired* velocity (dvx,dvy). This is similar to the above, the velocity which would lead directly to the player. I also add in the player’s velocity to the desired target point, to make the missile sort of lead the player. This desired velocity is not the velocity the missile gets. Instead, vx, and vy are incrementally adjusted with each frame of the game to move them closer to the desired vx, and vy. This has a nice effect of giving the missile a bit of inertia. It can’t just turn on a dime.

There is one more cheat that I do in computing the desired vx,vy. rather than go to the trouble of doing some trig calculations, or using a table of such precomputed values, I just figure out which distance x, or y, between the missile and the player is greater. Then, the corresponding desired velocity, x or y, I set to the maximum velocity the missile is allowed to go. The other velocity (y or x), I calculated by similar triangles (a multiply and a divide.) This has the bad effect that the missile can travel faster diagonally than it can horizontally or vertically, by a factor of sqrt(2). But it seems to be unnoticeable unless you’re looking for it.

One other point to make. When doing integer arithmetic, esp, calculating a proportion, and multiplying some value by it (as you do frequently with similar triangles), you must be careful to make sure your coefficient does not go to zero. In other words:

vy = sy/sx * magnitude;

is apt to give the wrong answer, you’d be better off with this:

vy = (sy * magnitude) / sx;

as (sy/sx) — in any units in a 2d coordinate system — are apt to be between zero and one. Mathematically, they are the same, but in integer arithmetic, “between zero and one” means they arezero OR one, but not between, which is to say, they’ll give you the wrong answer. if you do the multiply first to scale it up, before scaling it down with the divide, you’ll get an answer that works.

Ok, enough blathering.

ScaryReasoner:

Hey. This comment is completely out of place, but I saw no better place to put it. I just read your nice plug of The Frame Problem on the blogs that you like list. I’m not sure if I’ve already told you this—I think I might have linked you to a few posts, though—but just to clarify: I too am not a fan of the framing science project of people like Nisbet. It’s simply lying to people about science.

The title of the blog is explained here: http://theframeproblem.wordpress.com/about/

Best,

Ron

ronbrown said this on February 18, 2008 at 6:04 pm |

Sorry about that Ron. Fixed.

scaryreasoner said this on February 18, 2008 at 9:39 pm |

NP. Given the current popular discussion on framing, a title like “The Frame Problem” for a blog which focuses on science and religion is gonna probably generate some expectable associations.

ronbrown said this on February 22, 2008 at 3:55 am |