Tag Archives: math

Missions of the Reliant: Watch it, you’ve got one on your tail!

Missions of the Reliant version 3.0 now has the framework for enemies, enemy AI, and those infinitely annoying little fighters that everything lauches in droves at you and you can only hit by draining all the charge from your laser couplings. It took some work, let me tell you.

Mike’s original code expresses differences between facing angles as a function of which sprite is being displayed. Efficient. My code expresses differences between facing angles as atan2(-distanceY, distanceX). Mathematically correct and conceptually accurate.

‘Course, then “am I facing the player within a 120-degree arc?” becomes a completely different numerical test. Didn’t help that you kept setting variables you never used anywhere, Mike :-). Originally, I tried to use pretty much identical code for enemy movement as player movement, but it became clear that there were just too many quirks to it.

The fighters especially have an interesting AI about moving:

  1. Calculate distance from me to the player. If too high, return to origin, else continue. (Target determination.)
  2. Calculate angle from me to the player. If I’m not facing that angle exactly (difference between facing and calculated != 0), turn towards it. (Aim.)
  3. If I’m facing the player within 120° of arc, apply thrust N. (Thrust.)
  4. If I’m within distance D1 of the player, reduce speed by 10%. (Falloff.)
  5. If I’m within distance D2 of the player, and I have a loaded torpedo, and I’m facing the player exactly as in step 2, fire my weapon. (Attack.)
  6. Repeat every tick (or every other tick depending on preference setting) of the game timer.

Sounds simple? The fighter has to track its target, its current vector, its ideal vector, the difference between those two, its distance from target, and its firing delay, and constantly adjust all parameters accordingly. The code specifically intended for fighters is 118 lines including comments. Add 134 lines for code that applies to every enemy, 176 lines for code that applies to all game objects, 50 lines for code that applies to anything physics-capable, and 87 more lines for code that applies to everything that needs to do things based on the game timer. Subtract roughly 50 from that for comments and you get 500 lines of code just to drive that simple little AI, not counting the game timer itself or any of the drawing logic.

And I haven’t implemented the weapon, collision detection for the weapon, or the return to origin logic yet. And it’s got a couple of glitches as is, like if the fighter happens to spawn at exactly a 90, 180, 270, or 0-degree angle to the player while said player is at a full stop, it moves in a straight line rather than arcing like it should. Not sure if that bug’s in the original game since it’s next to impossible to set that particular scenario up deliberately without hacking source.

Did I mention that due to several stupid errors on my part, I ended up having to go back to the original fighter model in Infini-D and re-render it, then use Photoshop Elements to recreate the 36-phase sprite from that render? That was a fun two hours. On the other hand, the fighter model looks more “cool” now. It’s also a little harder to see. Sigh.

If anyone’s interested, here’s a couple of screenshots. I’d post a movie but I don’t have any instantly available way of making one and I’m too lazy to pursue the less instant ways.

Missions of the Reliant Fighter 1 Missions of the Reliant Fighter 2

Missions of the Reliant: Something to see at last!

There is now a user-visible change to Missions from all the background work I’ve been doing!

  1. The warp drive physics have been heavily corrected to match the original game rather than ignoring decreases in warp speed and turning the wrong way around.

It’s something, at least. You don’t want to know how much math went into that.

Speaking of which, sqrt(x*x+y*y) is faster than the polar/Cartesian conversion partly because an efficient function, hypot(), exists to perform exactly that calculation quickly already, and the compiler was converting the sqrt() call to __builtin_hypot() for me. The compiler’s smarter than me.

Stay tuned for news that I’ve finally managed to implement the fighter AI. It is coming, I promise!

Missions of the Reliant: I’m haunted by coordinate systems!

As if all the mucking about with coordinates before wasn’t bad enough, next I had to deal with unit vectors, polar/Cartesian coordinate conversion, sign adjustment vs. trigonometric functions… you get the idea.

In this case, my problem wasn’t caused by needing to update the algorithms Mike used at all, but rather by my need to replace the old MacToolbox FixRatio() and AngleFromSlope() functions with modern trigonometrics. Now, I’d already done all this, or else the impulse and warp drives would never have worked for this long, but in poking about in the implementation for mobile enemies, I realized I’d have to generalize the code, or else end up repeating it in about a dozen places, a well-known recipe for disaster.

In literal code, warp speed goes like this:

double diffx = warpCoordX - playerCoordX, diffy = warpCoordY - playerCoordY,
       theta_raw = atan2(-diffy, diffx), theta = round(fma(theta_raw, RAD_TO_DEG_FACTOR, 360 * signbit(theta_raw))),
       // make use of theta in degrees here to calculate a turn factor
       maxSpeed = warpSpeed,
       newDeltaX = cos(theta * DEG_TO_RAD_FACTOR), newDeltaY = -sin(theta * DEG_TO_RAD_FACTOR),
       finalDeltaX = playerDeltaX + newDeltaX, finalDeltaY = playerDeltaY + newDeltaY;
if (fabs(addedDeltaX) >= fabs(maxSpeed) * newDeltaX) finalDeltaX = maxSpeed + newDeltaX;
if (fabs(addedDeltaY) >= fabs(maxSpeed) * newDeltaY) finalDeltaY = maxSpeed + newDeltaY;

Conceptually, this reads:

  1. Calculate the difference between the player’s current position and the destination in Cartesian coordinates.
  2. Take the arctangent of the Cartesian coordinates, adjusted for inverted Y, converted to degrees and adjusted to the range [0,360] (atan2() returns [-Ï€,Ï€]).
  3. Convert the polar coordinates (using the implied mangitude of 1) back to Cartesian coordinates.
  4. Calculate the movement delta with a speed limit.

Why, one wonders, do I do a Cartesian->polar conversion, only to immediately convert back to Cartesian again? Answers: 1) I need the angle to calculate which way to turn the ship towards its destination. 2) The distance between current position and destination is a vector of (usually) rather high magnitude; I need to normalize that vector to get a delta. And the formula for normalizing a Cartesian vector is x/sqrt(x*x+y*y), y/sqrt(x*x+y*y). Two multiplies, an add, a square root, and two divides, all floating point. Without benchmarking I still intuitively think that’s slower (and I’m SURE it’s conceptually more confusing) than cos(atan2(-y, x)), -sin(atan2(-y, x)), two negations, an arctangent, a sine, and a cosine. Maybe I’m crazy.

Of course, typing all this out made me realize that I can, in fact, eliminate the degree/radian conversion entirely, as well as the range adjustment, by changing the conditional in the turn calculation. Once again I fell for the trap of not thinking my way through the code I was porting. At least you weren’t as bad at geometry as me, Mike :-).

Then I had to go and get really curious and benchmark it:

#include #include #include int main(int argc, char **argv) { struct timeval cS, cE, pS, pE; // Volatile prevents compiler from reading the loops as invariant and only running them once. volatile double x1 = 1.0, x2 = 2.5, y1 = 0.4, y2 = 3.2, dx = 0.0, dy = 0.0, inter = 0.0; gettimeofday(&cS, NULL); for (int i = 0; i < 100000000; ++i) { dx = x2 - x1; dy = y2 - y1; inter = sqrt(dx*dx+dy*dy); dx /= inter; dy /= inter; } gettimeofday(&cE, NULL); gettimeofday(&pS, NULL); for (int i = 0; i < 100000000; ++i) { inter = atan2(y2 - y1, x2 - x1); dx = cos(inter); dy = sin(inter); } gettimeofday(&pE, NULL); struct timeval cD, pD; timersub(&cE, &cS, &cD); timersub(&pE, &pS, &pD); printf("Cartesian diff = %lu.%06u\n", cD.tv_sec, cD.tv_usec); printf(" Polar diff = %lu.%06u\n", pD.tv_sec, pD.tv_usec); return 0; } [/c]

Foot in mouth. cos|sin(atan2()) is consistently 3x slower than x|y/sqrt(x^2+y^2) at all optimization levels. Somehow I just can’t see this as being an artifact of the brutal abuse of volatile for the benchmark.

Mike got around the whole issue, in the end. Knowing that he only ever had to calculate cos()/sin() for the angles in the period [0,35]*10, he just precalculated them in a lookup table. And cutting the cosine and sine calls out of the benchmark reduces the difference between the methods to about 1.6x, making his way a win over a four-way compare/branch for the turn calculation.

Live and learn.

Oh, and changes to Missions: Again, nothing you can see in play yet. But at least now I have the right building blocks to make the enemies from.

Missions of the Reliant: Math is fun, or why I wish I hadn’t flunked geometry

At last, an update!

  1. Absolutely nothing visible to the user has changed whatsoever.
  2. The internal structure of the code has been significantly reorganized.

As with the lament of all programmers faced with the demands of the technologically disinclined, I’ve accomplished a great deal, but since it can’t be seen, it might as well be nothing at all. Wasted time, the hypothetical slave driver- I mean, boss- would say. But it isn’t, I swear to all two of you who read this blog!

And now, another math rant.

Once again, as with so many things, the way Mike did things in the original code was correct and logical for the time he did it, but doesn’t fit into the object-oriented model I’m cramming his code into, despite its pitiful cries for mercy from such rigid structure. There are days I wish we were living in times when code could be so freeform as his was and still be comprehensible, but you can’t do that in Cocoa. Oh sure, I could port all the Pascal functions 1-to-1, but the Toolbox calls would be sticky at best. Anyway, in this particular case, I was trying to wrestle with the radar range calculation.

The original code reads something vaguely like: screenPos = Planetabs - (Playerabs - Playerscreen)  inRadarRange = n <= screenPos / 16 <= m. Translating, this means that whether or not a given entity (a planet in this case) is within radar range of the planet is dependant upon the Player’s position in screen coordinates, as well as in the game’s absolute coordinate system.

In the old days, this design made a certain amount of sense. He already had the screen coordinates immediately handy, so why take the hit of indirecting through A5 to touch a global for the absolute position? However, my design makes the screen coordinates a bit dodgy to use. So I had to recalibrate n and m to represent distances in game coordinates.

Algebra to the rescue. The code above, reduced and replacing the inequalities, becomes the algebraic equation (x - (y - z)) / 16 = a, where a is the radar range coordinate. The only screen coordinate term in this equation is z, so solve to eliminate z:

(x - (y - z)) / 16 = a
x - (y - z) = 16a       - multiply both sides by 16
x - y + z = 16a         - distribute the subtraction over the parenthetical expression
x - y = 16a - z         - subtract z from both sides

But, because both a (the radar range) and z (the player’s position on screen) are actually constants, all I had to do was take Mike’s original numbers (let’s use 64 for a and 268 for z) and calculate 16*64 - 268 = 756. Then, retranslating, the equation becomes the inequality inRadarRange = (myPosition - playerPosition) <= 756;. Repeat for the lower and upper bounds of x and y coordinates, and boom, no screen coordinates at all and I can calculate whether or not an object's in radar range based on nothing but its offset from the player.

To be clear, what I did up there was to eliminate a term from the inequalities so that they could be evaluated based on the position of the given entity in game space, rather than on the position of the entity's sprite on the screen.

I can't believe it took me a week to doodle out that bit of math.

Algebraic simplification

I was translating Pascal to C as usual for Missions when I came across the code fragment for computing the time bonus earned on victory given the current game time:

1
2
x := BSR(gCycle, 4) + 1;
x := round(50000 / x) * 10;

Now, I could have translated that to C as timeBonus = (50000 / ((cycle >> 4) + 1)) * 10, but I decided to get clever. Uh oh. I applied algebra to simplify the equation.

To translate it algebraically, I had to convert it to a purely mathematical equation. The right shift operator >> isn’t algebraic, but given the identity that x >> y = x / 2y, a right shift of four bits is an integer divide by 16. “cycle” is just a variable, so call it x, giving us the algebraic equation (50000 / ((x / 16) + 1)) * 10, or:

(50000/((x/16)+1)) * 10

Next, multiply 10 (as 10 / 1) into the equation:

500000 / ((x/16)+1)

Using the equality a/b + c/d = ad + bc / bd, rewrite (x / 16) + 1:

500000 / ((x + 16) / 16)

Rewrite using the equality a / (b / c) = a * (c / b):

8000000 / (x + 16)

Leaving us with two operations (add and divide) where originally there were four (shift, add, divide, multiply). Isn’t math cool?

All equation images generated by Apple’s Grapher program. Nice little feature that thing has, copy equation as TIFF.