🔒 Locked

Challenge: Interception Formula

Started by nilum Jun 8, 2009 at 7:04 PM 3 replies 1.7k views

Original Post

Jun 8, 2009 at 7:04 PM

The target is heading at a 45 degree angle North-East from coordinates (5,4) at a speed of 7yd/s. Note: coordinates are generic and vary from map-to-map in this game, thus (5,4) does not mean 5 yards East, 4 yards North from the origin. The player is at (11,8) and has a speed of 8yd/s. What heading (in degrees) should the player travel to intercept the target in the least amount of time? Please provide a formula/proof. Bonus points: Compensate for 500ms lag. Bonus points: If the player's movement speed is reduced to 2yd/s then interception of the target is impossible. How does he minimize the distance gap that will inevitably be left? Bonus points: Add Z-Axis coordinates. -- This is not homework. I've been trying to make an addon for a game that improves AI and also gives the player the best heading to intercept a target. Problem? I suck at math. So any help is appreciated. This is an example I've been trying to figure out on my own. Here is some of what I've come up with: P = (Xp,Yp) = Player Coordinate T = (Xt, Yt) = Target Coordinate What we need to do is create a triangle with the line PT, Target vector (Tv), and Player vector (Pv). The Angle of TvPT (that is the angle formed by the Target Vector and line PT) = the Angle of PvPT (that is the angle formed by the Player Vector and line PT) The Inerception point is then where Tv intersects with Pv. The final part is the velocity ratio. If Ps (Player Velcoity/Speed) is twice as much as Ts (Target Velocity/Speed) then the ratio is 2:1. So the angle PvPT is half (i.e. if it was 45 degrees it would be 22.5 degrees). If Ps (Player Velocity/Speed) is half as much as Ts (Target Velocity/Speed) then the ratio is 1:2. So the angle PvPT is twice as much (i.e if it was 35 degrees it would be 70 degrees). The Interception point will still be where Tv intersects with Pv. There will be some cases where Interception is not possible. It could be because the Target moves faster than the Player or Tv is 90 degrees or greater. Knowing all this I am still having trouble coming up with a formula or a function. Again, any help is appreciated.

alvaro

1,980

alvaro

Jun 8, 2009 at 7:10 PM

This has been explained many times in this forum, for instance in this thread.

nilum

Author

nilum

Jun 8, 2009 at 7:22 PM

could you do me a favor alvaro and plug-in my information into your formula? Because I am having a hard time following it.

If I see where my info is going I will have a better time understanding it.

Numsgil

109

Numsgil

Jun 8, 2009 at 8:18 PM

As it so happens, this is the topic for this very recent thread.

First step: start thinking in terms of vectors. Instead of finding a heading in degrees, think about finding a unit length heading vector. A heading of 45 degrees would be a vector of: <cos(45), sin(45)> for instance. The advantage is that the math is exactly the same for 2D as it is for 3D if you do everything in terms of vectors.

Now refer to my posts in this thread. Basically the goal is to construct a vector quadratic = constant. Then square both sides and bring like terms together, until you have a scalar quintic polynomial. Then you can solve for the (up to) 4 real roots in constant time. I link to some code in that post showing how to solve a quintic.

If no positive roots exist, it means it's impossible to intercept your target. It is possible to modify the equation to find an approach vector which will minimize the distance, but the math gets even uglier.

A 500ms lag shouldn't matter too much here, since any changes propagate only through the acceleration term, and thus do so rather slowly. If your target has changed heading or started/stopped moving, you just recalculate your approach vector as soon as you have the latest information.

Of course, this assumes you want to close the distance to the target in as little time as possible, and don't care about relative velocity when you get there. If you want to get within some fixed distance of your target (say, firing range), and then stay within that range, but not too close (their firing range), it gets messier, too.

Last, if you're using this information to write a bot for an MMO you play, to get an unfair advantage against other players: shame on you.

RandomBystander

Jun 11, 2009 at 3:01 AM

If it isn't homework...
If I understand the problem correctly: Player and Target start at given positions P and T. The target is moving into a fixed direction at a fixed speed vt. The player desires to intercept, and can travel with a maximum speed vp.
Solution: Define the "Angle on Bow" AOB to be the angle between the target's velocity vector and the vector P-T from target to player. We want to know the lead angle L needed for interception.
Geometric construction: Draw a ray B from T through P. Draw another one, H, from T in the direction the target is travelling. Choose an arbitrary timespan t. Taking a compass, mark the point M on H that is t*vp away from P. Draw a circle C with center in M and radius t*vt. There are the following cases:
1) C does not intersect B: Intercept is not possible.
2) C and B intercept in exactly one point I, or touch each other at I: Intercept is feasible in exactly one way, or marginally so. The player must travel paralell to the vector M-I (at full speed).
3) C and B intercept at two points I1 and I2: The player has the choice between a "head-on" intercept and letting the target "hit you in the back" (for this to happen, vt must be greater than vp).

Calculation of lead angle: Follows trivially from above construction and basic trigonometry.
(Law of sines. The resulting equation cannot always be solved for L, and the ambiguity may or may not correspond to a future event)

Bonus 1: Simply pretend in your calculations that one of the tow gets a 500ms head start?
Bonus 2: I've read an answer to this one in an old submariner's manual that's on the web somewhere: If you don't have solid data, constanty move perpendicular to the line of sight. There are two cases:
1) Needing to turn towards him, you eventually wind up dead ahead of the target, and are in perfect position for a torpedo attack
2) You notice that you would have to pull away. You are as close as you can get when you are on a paralell course with him.

Bonus 3: Trivial. Since there are only two vectors of interest (his course vector and the line of sight) the problem is fundamentally two-dimensional.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.