Aiming and hitting a moving target

[birdwing]

Yeah. I know this has probably been asked before, but I couldn't find it using the forum's search function so I am gonna ask.

I am working on building a Tower Defense game. Right now I have enemies that move along a path. The ability to add towers that shoot at the targets, a monetary system, lives, and levels. I am programming this in AS3 and before anyone points it out thinking its a mistake. I define _root as a variable in each of my classes (old habits die hard, so I find a way to use them :D) you just wont see this because there is no point in posting the entire class for my question.

The problem I have come across is that my code for how the tower shoots at the target is inaccurate. The tower shoots at the targets current location, which means that the target is gone by the time the bullet gets there.

The algorithm I am using is this: I am using the PHP block because the code block is lame. But this IS action script.. rest in piece [as] tag


//this is the code that calculates how far the turret should rotate, and it creates the bullet
//enTarget is the target the turret is shooting at
this.rotation = Math.atan2((enTarget.y-y), enTarget.x-x)/Math.PI*180 - 90;;
if(loaded){ //if the turret is able to shoot
loaded = false; //then make it unable to do it for a bit
var newBullet:Bullet = new Bullet(); //create a bullet
//set the bullet's coordinates
newBullet.x = this.x;
newBullet.y = this.y;
newBullet.maxSpeed = bulletSpeed;
//set the bullet's target and damage
newBullet.target = enTarget;
newBullet.damage = damage;
_root.addChild(newBullet); //add it to the stage
}

//the following code calculates the angle the bullet needs to travel
//it sets the xSpeed and ySpeed separately
//target is the target its being shot at
var yDist:Number = (target.y - this.y); //how far the bullet is from the enemy (x)
var xDist:Number = (target.x - this.x); //how far it is from the enemy (y)
var angle:Number = Math.atan2(yDist,xDist); //the angle that it must move
ySpeed = Math.sin(angle) * maxSpeed; //movent is multiplied by maxSpeed
xSpeed = Math.cos(angle) * maxSpeed;


the problem as already stated.. is that this causes the turret to shoot where the target currently is. I can't figure out how to get it to anticipate the targets movements. There is a variable defined for the speed of the bullet because I know I will need that.

I have been scouring the internet for an answer, but the only thing i have found so far was this:
Note: he is talking with point A as the turret and point B as the target
posted on stackoverflow in answer to a similar question


First rotate the axes so that AB is vertical (by doing a rotation)

Now, split the velocity vector of B into the x and y components (say Bx and By). You can use this to calculate the x and y components of the vector you need to shoot at.


B --> Bx
|
|
V

By


Vy
^
|
|
A ---> Vx

You need Vx = Bx and Sqrt(Vx*Vx + Vy*Vy) = Velocity of Ammo.

This should give you the vector you need in the new system. Transform back to old system and you are done (by doing a rotation in the other direction).



I'm new to physics and trigonometry. In fact I am teaching myself... so I understand almost nothing of what he said.


So my question is:

Can someone help me understand what this guy meant? Or help me figure out the proper equation to use to shoot a target by anticipating its movement?


Thanks :beer: :trout:

[icio]

I think I have a solution to this. Let me think on it a little more and try it out. PM me sometime if I forget, lol.

[randomagain]

I can vaguely remember a tutorial about this somewhere but I'll taking a stab at this...the target usually moves at a set speed horizontally or vertically and stops at corners or objects in the way. Likewise turrets tend to have set ranges. Hit rate tends to be 100%, with "miss" calculated by random score between max and min damage. So basically all you need to do is fool the 60fps eye that you are shooting at the target.

Currently you are just calculating the path and firing, the target moves and you miss.

You should be able to calculate the bullet time, t = distance using trig / bullet speed

now you know the approx bullet time,

so you need the lead distance, d = speed of target * bullet time

you then recalculate the path with the lead distance added to the target coordinates

this should then give an approximate lead target to shoot at, run the math again with new bullet time and it should hit

changing direction is tricker, they tend to move, stop, then move, *shrugs* got half way there:P

[icio]

Yep, I got it to work. I'll go and write up the explanation for you (with all the juicy mathematics for you to enjoy!)

[lnsiu]

Why don't you do a discrete calculation rather than an analytic? Don't get me wrong, I think you should work through the analytical first. but in the end, both of them will probably be equally calculation intense, and if you try to shot at a human player, I personally would not try to shot at a linear assumption (if you ever played first person shooter over the internet, some play like they had a disease of some kind, or at least parkinson, still it works, and they successfully avoid being shot)

If you pre-calculate the steps of the bullet and make the turret bullet behave like a 'heat seaking' missile, you can average the max min angle and shot somewhere in the middle of the positions of the 'heat seaking' missiles positions over time.

If you get that to work, you can then pre-record the opponents movement as an assumption of future movement and use that motion for the pre-calculation with your missile, this means the turret has to 'observe' the opponent before it shots. (since you have a known path of the opponent, its not much to assume I guess?)

[TOdorus]

Is this question going to pop up every half year? There is a search function guys.

[birdwing]

Yep, I got it to work. I'll go and write up the explanation for you (with all the juicy mathematics for you to enjoy!)

I would be most appreciative. Thank you :D:D:D:D:D:D:D:D:D:D:D





--------
TOdorus.. i did search, but I couldn't find what I was looking for, or understand what I did find.

[icio]

Okay guys, here's what I've got:


/**
* Shoot at a target
*
* @param t The target to be shot
* @return The bullet to be fired (or null if cannot hit)
*/
public function shoot(targ:Target, bulletSpeed:Number = BULLET_SPEED):Bullet
{
var dx:Number = targ.x - this.x;
var dy:Number = targ.y - this.y;

var a:Number = targ.vx * targ.vx + targ.vy * targ.vy - bulletSpeed * bulletSpeed;
var b:Number = 2 * (targ.vx * dx + targ.vy * dy);
var c:Number = dx * dx + dy * dy;

// Check we're not breaking into complex numbers
var q:Number = b * b - 4 * a * c;
if (q < 0) return null;

// The time that we will hit the target
var t:Number = ((a < 0 ? -1 : 1)*Math.sqrt(q) - b) / (2 * a);

// Aim for where the target will be after time t
dx += t * targ.vx;
dy += t * targ.vy;
var theta:Number = Math.atan2(dy, dx);

// Fire the bullet
var bullet:Bullet = new Bullet();
bullet.target = targ;
bullet.hitPoint = new Point(targ.x + targ.vx * t, targ.y + targ.vy * t);

bullet.x = this.x;
bullet.y = this.y;
bullet.vx = bulletSpeed * Math.cos(theta);
bullet.vy = bulletSpeed * Math.sin(theta);

return bullet;
}

which you can see in action on my website:

http://paul.sc/shooting-moving-target/
(backup (http://www.swfcabin.com/open/1271284059))

I've detailed the derivation of my solution in the article (http://paul.sc/shooting-moving-target/Shooting_Moving_Target.pdf) and you can download the source code (http://paul.sc/shooting-moving-target/Demo.zip) from the link on the page or from the attachment posted here.

Hope you enjoy it :thumb:

[icio]

I was just going to post that on the Stackoverflow question when I noticed the second answer posted there. Did you fail to spot it? It's exactly the same derivation and solution that I came up with.

Edit: or perhaps you really were wanting to understand the given solution rather than understand how to do it. Sorry if that's the case.

[birdwing]

Yeah, I was just trying to understand the solution :lol: sorry if that wasn't clear.
Thanks for all the help! I understand what I was doing wrong now :beer:

I realize teaching myself this sttuff is going to be harder that I originally thought :trout:

[lnsiu]

we should have a 'turret' battle altogether :-)

I enjoy reading icios solution, and I'm totally blown away by the amount of information he produced in short time. thank you!

...but if there ever will be a AI battle, ahem...
I will beat him :toad:

[icio]

...but if there ever will be a AI battle, ahem...
I will beat him :toad:
ORLY?

[Jovia]

It's a great solution.

Just thought that sometimes in game, we don't really aim for such perfect calculations. This accuracy can actually make it look weird. Imagine:

Monster ==>== Turret
...................||
...................||
...................||
................... X

Assuming that X is where the monster and the missile will land with perfect calculation, you will actually see the turret firing towards X when the monster is actually on his direct west direction.

One suggestion is to increase the speed of the missile, increase the size of the impact effects, and that should create a believable image that the bullet hit the monster. If you look at WC3 tower defense, fast monsters always outrun the point of impact.

Not discrediting the solution, don't get me wrong. :)

[icio]

I'm pretty sure it doesn't do that. None of the solutions above take into the consideration the Monster changing direction. Any diagrams that make it look like that is the case are in fact illustrating the x- and y-components of their movement vector.

[lnsiu]

ORLY?

HAHA, sure why not? I think it's a great idea to do AI battle :)
PM me when its time... :pirate3:

anyhow...

One alternative caclulation that doesnt involve trigonometry could be achived if we imagen the targets movement and the turrets bullet as expanding circles (and their radius are their respective trajectories).
So what we want to know is when these radius meet each other. Their radius are proprotional, since their speed is constant.

This radius relation can be expressed with the formula:
R.1 = c x R.2
(c=constant,R=radius)

The targets path is fixed and be written on the form:
f(x) = y = (x + c)

the targets 'radius' can be written with phytagoras theorem:
(R.2)^2 = (f(x.1)-f(x.2))^2 + (x.1 -x.2)^2
(x.1 = current position, x.2=unknown position)

The turrets bullet radius can be written somewhat equally:
(R.1)^2 = (x-j)^2+(y-k)^2
(j=turrets x, k = turrets y)

so to get a complete formula for when the bullet and the target intersect, we replace
R.1 with c x R.2
and
y with x + c
thus
(c x f(x.1)-f(x.2))^2 + (x.1 -x.2)^2 = (x-j)^2+((x + c)-k)^2

giving a second degree equation to solve...