Need help with determing an equation to solve a typical 2d game problem.
Author
Hi everyone,
I have been thinking about the types of problems I would have to solve for simple 2d game situation. Hopefully someone here could point me in the right direction on how to solve this.
I am only trying to solve this in terms of a 2D game world:
An object T (I've been considering it as a point thus far) is moving at a constant velocity on a constant vector (slope, whatever).
Another, computer controlled, stationary object B is attempting to "shoot" T with a projectile (also a point). This projectile travels at its own constant velocity. In order to do this, B must predict where T will be in such a way that the projectile and T will occupy the same location at the same time in order to "hit" T.
I can think of ways to do this iteratively, but thats not how I think it could be done if I only knew the proper math.
So if anyone out there can tell me how to determine this I would be most grateful!
Has this been asked and coded a million times? Is there a free API that solves this I could use?
Thanks everyone.
EDIT: forgot the title.
EDIT #2: Clarification: Object B is not considered to be moving at the time it shoots. The projectile it shoots has its own speed which is constant when fired.
EDIT #3: More Clarification. The current speed and direction is known to B. i.e. B can see T moving and will make his "shot" based on T's speed and direction.
(and thank you for both responses so far!!)
[Edited by - mesquishy on March 30, 2005 2:55:49 PM]
We had the same issues in our project. But to be very honest I've hardly
seen a game i.e: Age of Mythology shooting a projectile while moving...
The core problem is to scann an area while moving. So this is very very time consuming considering a RTS game engine or something that is capable of doing it...
One thing that could might led you into the right direction which has also been
tried before is to solve that problem with Machine Learning...
In oder words: Apply some advanced area scan alg. first and then apply some AI
to predict moving objects.
So I have not done that yet but I am sure it's worth spending some time on this
problem...
seen a game i.e: Age of Mythology shooting a projectile while moving...
The core problem is to scann an area while moving. So this is very very time consuming considering a RTS game engine or something that is capable of doing it...
One thing that could might led you into the right direction which has also been
tried before is to solve that problem with Machine Learning...
In oder words: Apply some advanced area scan alg. first and then apply some AI
to predict moving objects.
So I have not done that yet but I am sure it's worth spending some time on this
problem...
Quote:EDIT #2: Clarification: Object B is not considered to be moving at the time it shoots. The projectile it shoots has its own speed which is constant when fired.
Aha well then... You're only choice is AI anyhow...
This could be done like that. But don't hang me up on that though
it is just an idea...
Before the game starts perform arbitrary (random) path-calculations.
increment each visited area with a probability, in order to record
the most visited paths along your map... (Could also be done mathematically (terrain analysis) but I am sure you don't want this ;-)
So then you have a record of probabilities which might help you to determine
which of the adjacent tiles the enemie might walk next...
Simple but as Jean Connery says doable... ;-)
Here's the variables I used:
p_d_x, p_d_y : projectile's direction vector
t_d_x, t_d_y : target's direction vector
p_s_x, p_s_y : projectile's starting position
t_s_x, t_s_y : target's starting position
i_x, i_y : intersection point
t : time
So I started with this:
Mathomatic rearranged everything into this:
Of course they depend on each other, and there's no mention of speed anywhere in there, so we'll add a new equation to join them together:
speed^2=p_d_x^2+p_d_y^2
This unfortunately resulted in this super ugly formula:
There's a bit of redundancy in there that could be eliminated with temporary variables. Also notice sign2 in there. It can either be -1 or 1, meaning there's two possible solutions.
Assuming that works, I understood what you were asking, and I haven't screwed up yet, you'll also want to solve for t, and choose the solution with the lowest time value that's greater than 0. Trying to shoot your projectiles backwards through time doesn't seem to work well in practice.
p_d_x, p_d_y : projectile's direction vector
t_d_x, t_d_y : target's direction vector
p_s_x, p_s_y : projectile's starting position
t_s_x, t_s_y : target's starting position
i_x, i_y : intersection point
t : time
So I started with this:
i_x = p_s_x + p_d_x * ti_y = p_s_y + p_d_y * ti_x = t_s_x + t_d_x * ti_y = t_s_y + t_d_y * tMathomatic rearranged everything into this:
(p_d_y - t_d_y)*(p_s_x - t_s_x)p_d_x = t_d_x + ------------------------------- (p_s_y - t_s_y) (t_d_x - p_d_x)*(p_s_y - t_s_y)p_d_y = t_d_y - ------------------------------- (p_s_x - t_s_x)Of course they depend on each other, and there's no mention of speed anywhere in there, so we'll add a new equation to join them together:
speed^2=p_d_x^2+p_d_y^2
This unfortunately resulted in this super ugly formula:
#1: p_d_x = (((((2*((t_s_x*((2*(p_s_x^3)*((t_d_y^2) - (speed^2))) + (p_s_x*((p_s_y - t_s_y)^2)*((t_d_x^2) - (speed^2))) + (3*(p_s_x^2)*t_d_y*t_d_x*(t_s_y - p_s_y)))) + ((p_s_x^3)*t_d_y*t_d_x*(p_s_y - t_s_y)) + ((t_s_x^3)*((2*p_s_x*((t_d_y^2) - (speed^2))) + (t_d_y*t_d_x*(t_s_y - p_s_y)))))) + (6*(t_s_x^2)*((p_s_x*t_d_y*t_d_x*(p_s_y - t_s_y)) + ((p_s_x^2)*((speed^2) - (t_d_y^2))))) + (((speed^2) -(t_d_x^2))*((p_s_y - t_s_y)^2)*((p_s_x^2) + (t_s_x^2))) + (((speed^2) - (t_d_y^2))*((p_s_x^4) + (t_s_x^4))))^(1/2))*sign2) + (t_d_y*(p_s_y - t_s_y)*(p_s_x - t_s_x)) - (t_d_x*((p_s_y - t_s_y)^2)))/((2*((p_s_x*t_s_x) + (t_s_y*p_s_y))) - (p_s_x^2) - (t_s_x^2) - (t_s_y^2) - (p_s_y^2))There's a bit of redundancy in there that could be eliminated with temporary variables. Also notice sign2 in there. It can either be -1 or 1, meaning there's two possible solutions.
Assuming that works, I understood what you were asking, and I haven't screwed up yet, you'll also want to solve for t, and choose the solution with the lowest time value that's greater than 0. Trying to shoot your projectiles backwards through time doesn't seem to work well in practice.
Ok this can be done Mathematically ;-)
Hold on I'll make a drawing of it...
Well never mind smart_idiot is right... ! I checked it...
Hold on I'll make a drawing of it...
Well never mind smart_idiot is right... ! I checked it...
If you don't understand SI's formulas (Especially that last one...) you essentially first need to find the intersection of two lines; then you just fire towards that position. This intersection point happens to be exactly TargetVelocity*T from the target and BulletVelocity*T from the shooter and on the targets direction vector, where T is the time until it hits. Given the starting positions of the target and shooter, the velocity of the target, and the scalar velocity of the bullet, SI devised a set of equations which can only all be solved by a single point - the intersection point. Atleast, that's what I think he did.
I don't know if what I posted was right or not.
My intention was that it would tell you the direction to shoot. p_d_x can be solved with that huge ugly formula, and p_d_y can be solved using that much shorter formula once you get p_d_x.
In either case the magnitude of the vectors represents their speed.
My intention was that it would tell you the direction to shoot. p_d_x can be solved with that huge ugly formula, and p_d_y can be solved using that much shorter formula once you get p_d_x.
In either case the magnitude of the vectors represents their speed.
This can be solved by calculating the intersection of a line and a cone. A cone? Yes. Although you are working in only 2 spatial dimensions, time (t) should be considered the 3rd dimension in this case. When object B fires its projectile (at t=0), the projectile moves away from B at a fixed speed (s). But since we don't yet know the direction it must fire in, at any given time after firing, the projectile will be somewhere on the circumference of a circle with radius t*s. Since that circle will be expanding at a constant speed, it can be considered a cone, which is oriented along the t axis and has object B at its very tip. If you can find the intersection between the target's trajectory (which will now be a line plotted in 3 dimensions) and the cone, you will know what direction to fire in.
I hope that made sense.
I hope that made sense.
You could do it this way, though it might be a little slow:
You know the velocity of object T, and its current position. Knowing this, you could check all the points along the line T will follow. At each checked point, calculate the time it takes T to reach the point and the time it takes B's bullet (or whatever) to reach the same point. When the two times are the same, fire away!
You could probably optimize the search function. Perhaps make it like a binary search or something. Anyway, that's the method I thought of. You could use it "as is" until it works right, then optimize from there.
Hope I helped.
[EDIT]spelling fixes
You know the velocity of object T, and its current position. Knowing this, you could check all the points along the line T will follow. At each checked point, calculate the time it takes T to reach the point and the time it takes B's bullet (or whatever) to reach the same point. When the two times are the same, fire away!
You could probably optimize the search function. Perhaps make it like a binary search or something. Anyway, that's the method I thought of. You could use it "as is" until it works right, then optimize from there.
Hope I helped.
[EDIT]spelling fixes
The cone method may be a little math-intensive, but it will run in constant time. Any iteratve search is going to scale badly, particularly if the required resolution is significantly smaller than the distance to the target (in other words, if you need to check a lot of points along the trajectory).
Also, in the described situation, there will not always be a firing solution; the speed of B's projectile might be insufficient to reach the target. A search method will not necesarily discover this, at least not quickly. The cone method will, also in constant time.
Also, in the described situation, there will not always be a firing solution; the speed of B's projectile might be insufficient to reach the target. A search method will not necesarily discover this, at least not quickly. The cone method will, also in constant time.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
