10 replies to this topic

[vapourmile]

This is an age-old problem Games programming problem:

Hi there, I hoped this may capture some imagination.

I am having trouble with one of the oldest problems in computer games. It's simple in essence, but I haven't got a good answer:

In a 2D game, there is an alien craft attacking your player craft with missile. They can be bullet shaped, they don't need to rotate. So, you're at point B and the alien is at point A. So, given a constant velocity, V, and a refresh rate of 60Hz, how do you plot the coordinates of the missile so it makes a straight path at a constant speed, towards your player location.

Most games, I would have thought, must have to tackle similar problems.

My answer looks roughly like this:

Find the difference between Alien.x and player.x, square it. Find the difference between Alien.y and player.y, square this and add to previous result for .x. Square root to give the distance between player and alien (it's basic trig, Pythagoras' theorem).

Then divide the x difference by this distance, this gives the cosine of the angle of incidence. Divide the... (are you getting the picture here, it's a bit long winded isn't it?)... y difference by the distance between the two point, giving the sine. Multiply each of the sin and cos by the speed vector to give the velocity in each of the x and y that must be travelled by the missile in each refresh.

It works, but it's a CPU exhausting solution! There must be a way of avoiding all that math. Mostly the very ugly square root and those two divides it yields.

My only thought is "Why am I wasting time calculating the hypotenuse... I can already assume the right angled triangle I'm working with has the identical aspect of the target triangle which will have a hypotenuse = velocity... so I'm thinking I shouldn't need to work out the length of the diagonal I'm starting with because I'm only interested in the length of the diagonal (the speed) I'm finishing with?

Any light you can shed on this subject would be greatly appreciated and both myself and my friend are losing confidence in ourselves as this has been an issue which has existed since the first ever pixel-mapped graphical video games!

PS. We'd be happy to look at partial solutions... ones that look right even though they may not be strictly accurate, if they're fast. The current solution, which is actually being used in the program, gets the direction of the missile 100% right. But does not adjust the velocity for the diagonals which are therefore travelling too fast (the square-root of two times faster than the horizontals).

If that's too much of a mouthful, the basic question is... how do we get from A to B given a specific speed to move at? Simple?

I'd love to hear your approach, and this question is being asked for a game which is actually being developed and programmed for the Nintendo DS, so please, only serious answers.

[WingedPanther]

Have the bullet store its velocity as a delta-x, delta-y, along with knowing it's position x and y. That way, each update after the first is simple arithmetic.

[vapourmile]

Thanks very much for the response winged panther. However, my own trig solution does exactly what you suggest... and the initial calculation you mention is exactly what the problem is! In other words, it's making that initial calculation satisfactorily fast that I'm failing to do! Or, failing that, getting an end result that uses simpler math which is satisfactorily visually convincing.

Any further suggestions would be greatly appreciated.

Here is a game, your own main craft is a perfect example, which seems to have no trouble whatsoever with this problem:

YouTube - mushihime 06

[WingedPanther]

What are you running this in that sin and cos are slow to compute? You only have to compute them once when the shot is fired, so it shouldn't be a big deal.

Watched the video: since the shots are firing at known, fixed angles, you can pre-calculate the deltas.

[vapourmile]

Yep, you're right. On that game, the deltas can be precalculated as there are few direct shots at angles specified in real-time. I want to get the same effect (bullets that fly at the right speed no matter what direction they're heading) but with the angle decides on the fly so they can be direct shots.

I'm programming on a Nintendo DS. I want to code to be fast and pretty. In my algorithm I use a sqrt function which is notoriously slow and I can't imagine the average sin and cos being fast, although, I'm not using them because I know the hypotenuse I can calculate the sin myself without having to use the library sin function.

I want to program out the sqrt and I believe there is a solution that can cancel out one of the divides. This a technical challenge, so the object of interest from our perspective is how satisfactory a solution we arrive at. The challenge is in finding an ingenious answer.

Take Bresenham's algorithm as a standard to compare to. That solution also joins any two points with a straight line of any angle, given the start and end coordinates of the line also. Only huge difference, this solution doesn't use trig, nor pythagoras nor square root nor any fixed or floating point math. Just integer subtraction. It's brilliant. I feel there must be an answer more like that for this problem in which you can also set the speed you want to travel along that line. After all, Bersenhams must work out the ratio so that point y is arrived at, at the same time as point x is arrived at even though points x and y are different distances away from the start... so he's expressing that interval without using anything but integer math. See where I'm going with that? The trig is the obvious solution... but we're on a tiny CPU and we believe there is a better answer.

Anybody still got any ideas on this please?

In other words, the problem isn't my math letting me down. I know a mathematical solution. I'm quite capable of writing all the sin/cos/sqrt functions myself in assembler. I'm an experienced programmer who's au fait with math. The trouble isn't getting a grip on the math, I find that part easy. The challenge is to think up a smart algorithm to do it.

[WingedPanther]

If you're familiar with calculus, you could use linear interpolation.

[vapourmile]

I'm familiar with calculus, but I am totally mystified by your suggestion this could make for Faster calculation. Can you please provide an example?

[WingedPanther]

Linear approximations based off several known values of square roots would be simple calculations rather than the full deal. You could also implement your own square root function that is only accurate to a couple decimal places (google square root algorithm).

[PythonPower]

I would suggest the Babylonian method for calculating square roots. It is a special-case of the Nth root algorithm. Each iteration roughly doubles the number of correct decimal places since it has quadratic convergence.

In implementations I've used before I simply set x0 to 1 but you will probably get better results setting it to A/2. For a game, consider how many iterations you need to assure accuracy to 1 pixel.

[AlanQ]

I agree with PythonPower.

[Johhny]

wow, you guys are so good with maths. wow, really wow