Hi there,

I wanted help solving a technical problem a friend has given to me. In fact, both me and my friend have our own solutions but we don't like them because we both feel certain there must be a better, more efficient way than how we're doing it.

The basis is simple: Given a specific speed, how do you get from A to B in 2D?

The exact scenario is typical of zillions of games. An alien baddy wants to shoot you with a missile he can point. We're not worried about the graphics here at all, only the path the missile will take. Assume the screen refreshes at 60Hz (which it does) and out game will sync. We have a fixed speed for the missile of V pixels/frame. My friend is using an integer V, but I'd think you might like to have a fixed point. The speed can vary from bullet to bullet, but it's constant once the bullet is fired. Simple so far?

Now both my friend and I have bothered to come up with answers of out own to this question and both of like neither of our answers. His is not realistic enough and mine is more realistic but too math heavy. His basically works out along which axis the bullet will travel fastest and makes the bullet travel at SPEED pixels per frame in that axis. After dividing to find the ratio of X to Y he then uses a variant of Bresenhams algorithm to calculate the speed in the Other axis (i.e. Substracting the fraction away from the start distance once per frame (and storing the answer for next time) until the subtraction underflows, then adding back on the length you first thought of).

The trouble with this is that all bullets always travel at SPEED pixels/frame in one or the other aixs, meaning the more diagonal the bullet direction, the more unnaturally fast the bullets move. In other words, if we fired a wide shot at a wall, the bullets would all hit the wall at the same time.... they should hit the closer part of the wall first. Get it?

My version also sucks. I get the exact right result, mathmatically speaking, but I'm using trig to get it, which includes a square root and two divides per missle shot. This takes ACRES of CPU time and the solution was discarded without implementation for being too CPU intensive. I agree. This is an answer but not a Result!

Can you *please* think of a better solution?

If your maths is up to it, you might find the equations of motion quite handy.

http://en.wikipedia.org/wiki/Equations_of_motion

What is your target hardware anyway? If it's anything fairly modern then don't worry about trig being 'slow'. Cause it really isn't these days.

Can't you look at the particle by way of position x,y at time t?

Position x at time t = V * t * cos(angle), with the angle being the deviation from a shot straight down the x-axis. Saved to a variable, you'd only have to do that calculation once.

If you don't care about slight variations in angle giving you the same results could just use fixed values based upon a range of angles?

If I'm not mistaken that should greatly lower the cpu overhead.

You really don't even have to get the angle in degrees just use the position of the two points to create a ratio.

If I'm way off on this I apologize.

---

Hi there,

 

Thanks.

 

I have taken a look at the equations of motion, I haven't looked deeply into it as my maths isn't enough to get it off-pat. At first glance it looks like the equations may actually be more acvanced than the one that I'm looking for, for what I need, all the variables except initial velocity will be 0. In fact, I want the simplest equation I can get so it can be computed quickly.

 

The target hardware is the Nintendo DS and my solution uses trig to get the result. I think it's something like:

 

Find difference between start x and end x.

Repeat for y.

 

This gives you the side lengths of a right-angled triangle in which the hypotenuse is the path between the start and end point.

 

Dividing this hypotense value into the y length gives the sine of the angle and doing the same with the x gives the cosine (for those who didn't know, now you know how to get sine and cosine values without sine and cosine keys on your calculator).

 

I then multiply the x distance by the SPEED constant and divide the result by the cosine to get the final x speed... then do the same with the sine, y distance and SPEED.

 

This means a maths hit of a sqrt, two divides and two multiplies.

I feel sure I can simplify this but can't see it.

 

The limited number of angles method was definitely one I'd considered. It's possible, in Assembler language, which is what we're using, to divide a circle into any number of angles just by using compares and arithmetical shifts at the bit level.

It took me a while, but I managed to suppress the square root. The derivation is pretty annoying, so I'll just give the pseudocode if you don't mind.

// int V is the speed of the missile in pixels per frame
// int targetX and targetY set to pixel coordinates of the target
// int shipX and shipY are pixel coordinates of the alien ship

int VSquare = V*V; // it's useful to precompute this value

int directionX = targetX - shipX;
int directionY = targetY - shipY;

// You'll need to do two multiplications here, unfortunately.
int directionXSquare = directionX * directionX;
int directionYSquare = directionY * directionY;

int directionLengthSquare = directionXSquare + directionYSquare; // square of the hypothenuse

/* I suppose these parameters seem pretty magical, but they're also necessary. They follow from the requirement that abs(shipX + n vx - x) // The names F, G and J have no particular meaning.
// If VSquare is a compile time constant, you can optimise these two multiplications into shifts and adds.
int F = VSquare * directionXSquare;
int G = VSquare * directionYSquare;

int J = directionLengthSquare;

int dx = sign(directionX); // i.e. -1, 0, or 1
int dy = sign(directionY);
int errorX = -J;
int errorY = -J;
int errorXInc = F;
int errorXDec = 3 * J; // You could use J + (J int errorYInc = G;
int errorYDec = 3 * J;

int x = shipX; // the position coordinates of the missile
int y = shipY;

while(true)
{
while(errorX >= 0)
{
errorX -= errorXDec;
errorXDec += 2 * J;
x += dx;
}

while(errorY >= 0)
{
errorY -= errorYDec;
errorYDec += 2 * J;
y += dy;
}

errorX += errorXInc;
errorXInc += 2 * F;

errorY += errorYInc;
errorYInc += 2 * G;
}

The actual code doesn't even look that complex, but it's a *** to explain why it's correct. It's all basically a superpowered Bresenham's algorithm with extra tricks to eliminate that nasty square root.

If you want a fixed point value for the speed V, as an example 5/16 (that is, integer 5 with the last 4 considered bits after the radix point), you'll need to adjust the parameters a bit. Since VSquare = 5*5 = 25 wouldn't be the square of the actual speed (which is 25/256), still using F = VSquare * directionXSquare in stead of the mathematically correct F = (VSquare/256) * directionXSquare is the same as multiplying F by 256. (The same goes for G of course). Luckily the algorithm is unchanged by multiplying F, G and J by the same constant. By redefining V as a fixed point with k radix bits, you would already silently have multiplied F and G by (2^k)^2 = 2^(2k). All that's left is to multiply J by that constant. So in stead of int J = directionLengthSquare; use int J = directionLengthSquare You can see how a shift of 2k bits can easily overflow, especially as directionLengthSquare is already a large number, so you should try to keep k small if you do this.

Actually, Ravek, fi that program does what you say it does, then it's a brilliant piece of work. It always struck me that there should be a way of extrapolating a variant of Bresenham's to tie down the x and y velocities. What I'm particularly impressed with right now is that not only is there a noticable absence of square roots, at first glance, I can't even see any divides?

Sorry for not reading the column sooner, but, I admit, I'd lost hope taht I find somebody with the answer I was hoping for. This could be it! Thank you so much for taking the trouble over it. : )

PS. It's great to get a response from somebody who actually understands optimisation these days!

No divides indeed. Those were a lot easier to remove than the square root though. If you want to convince yourself that the algorithm works, I suggest plotting the x and y values against the number of loop iterations and comparing that with the theoretical lines.
I've tested it myself that way, giving pics like the one below. (On the horizontal axis is the number of loop iterations, with pixel values on the vertical axis. The blue points are the values for x, the purple ones for y. The diagonal lines are the theoretical values, and the horizontal lines show the target coordinates. As you can see, the ship's coordinates when firing were (0, 23))



I could also post the entire derivation of the algorithm. I sort of want to, because it's the only way I can guarantee that it actually works, but I find that it's tough to properly write out. Maybe I'll get round to it later.

Thanks. Looking at the example graph, the shot would be moving at about 0.4755 pixels / frame? I haven't traced the program myself yet, I take it it would be for speeds > 1?

I'm curious to know, if you don't mind telling me, what programs you're using to plot the gaph? I'm an assembler programmer and never got to grips with C.

The algorithm should work for any positive value of V. Of course you'd have to use floating point numbers or fixed point integers if you'd want a speed
In the example I plotted, I set V = 0.5 pixels/frame. Since the missile travels from (0, 23) to (17, 10), that's a distance of about 21.4 pixels, so it'd take 42.8 frames to reach the target. From the graph, the algorithm reaches the target in 43 steps, which is as close as you're going to get with integer arithmetic.

In some cases, like going to (17, 9) in stead of (17, 10), the missile would arrive a frame later than the best rounding would be (in this case, it takes 45 frames in stead of 44.05 rounded to 44 frames), since the algorithm takes steps lazily. It only steps if not doing so would mean it'd be further than 1 pixel away from the theoretical position. It should never be two frames late though, so I supposed this is accurate enough for most purposes, and it's a bit difficult to design an algorithm that always does the best possible rounding.

I tested the program in Mathematica, which is a high-level computation software program (or that's what wikipedia calls it). It's pretty useful for things like this, since it's trivial to make plots of things in Mathematica, and it can also calculate to any precision or even do abstract calculations like (a + b)^2 = a^2 + b^2 + 2 * a * b.
It's pretty awesome, but unfortunately expensive ... I only have access because of my university.

Oh excellent. Mathematica. Wow, I have been wanting to get my paws on that program for a while now and I was searching for a nice online app which can plot lines given coordinates to save me having to visualise everything, which is what I normally do. I feel less embarrassed for asking now. Thank you.

A correction to the code in my first post:

This line is wrong:
int errorXDec = 3 * J; // You could use J + (J int errorYInc = G;

It should be these two lines:
int errorXDec = 3 * J;
int errorYInc = G;

The first line had a comment that was supposed to read "// You could use J + (J [left-shift] 1).", with [left-shift] being two smaller-than symbols, but the board software won't allow it.

Rectov:

Oh excellent. Mathematica. Wow, I have been wanting to get my paws on that program for a while now and I was searching for a nice online app which can plot lines given coordinates to save me having to visualise everything, which is what I normally do. I feel less embarrassed for asking now. Thank you.

Python, with pylab.

Rectov:

PS. It's great to get a response from somebody who actually understands optimisation these days!

Who was that really for, Ravek or me?

Hi there Ravek,

I am about to write an implementation of the algorithm you supplied (thanks again). I meant to enquire... the program doesn't comment the variables which are the actual missile plot coordinates. Excuse my code-blindness but I can't see at a glance which bits to use for the plot. Please would you be so kind as to point it out to me?

Having a quick look it would seem to be x & y.

int x = shipX; // the position coordinates of the missile
int y = shipY;

while(true)
{ 
   while(errorX >= 0) 
   { 
      errorX -= errorXDec; 
      errorXDec += 2 * J; 
      x += dx; 
   } 

   while(errorY >= 0) 
   { 
      errorY -= errorYDec; 
      errorYDec += 2 * J; 
      y += dy; 
   }

Thanks for the input Bag, appreciated. You are right as far as I can tell.

I have written an implementation and I need some time to check my code as the missile always travels away from the target. It also seem to wobble, changing in speed and path over time. Looks though.

PS. Yes, I love you too rasta teddy. Better now?

Yeah, the Bag was right.

Sorry for not answering sooner, I hadn't checked the boards in a while.

Actually, sorry I didn't reply sooner... it was because of something I thought I has already posted but, somehow, haven't:

Ok, everybody reading, is free to view my implementation of Ravek's Algorithm (as I think it's fair to call it) at this URL:

Ravek's Missile Tracking Program.

In order that anybody can try the program, and alter it as they please I have implemented it within the easiest-to-learn programming environment I know, the rather brilliant Scratch from MIT, which I recommend anybody remotely interested n programming downloads and tries. Get it here:

Scratch.

The language is drag and drop and so easy to learn you can learn it by trial and error and you won't need to read a thing!

When you have it, please import my implementation of Ravek's algorithm into it and compare it to this version here and let me know where I've gone wrong!

It does appear to work correctly at the moment as the missile (here played by the witch) always seems to both move away from the target (the ball) and also slows down and changes direction over time. So, Ravek in particular, if you'd like to have a go at it and suggest corrections, I'd be more than happy to hear about it! Let's see if we can get this baby working.

You can either comment at the scratch site, or here, and I will read it. Otherwise, just get Scratch to start with and that can be your new toy, because it makes programming a computer fun, and addictive again!

PS plz don't criticise my games too harshly if you look at them, I'll sulk, I only wrote them to play around and get to grips with Scratch (excuses). But above all, please, play around with the Scratch program linked at the top here and write and let me know how you get on, thank you so much, and thanks to the contributors to this thread for contributing to this thread! : )

-Jonathan.