If I have a group of soccor players, the speed at which each player can move, and a moving soccor ball. How do I calculate the time it takes to intercept the moving ball for each player?

In this book you find good explanation of AI and even a soccer sport simulation as one of many examples:

http://www.amazon.com/exec/obidos/ASIN/1556220782/greggman

Disclaimer. I'm an idiot, and I have no clue of anything. My math is horrible, I cannot prove anything, I barely know what "vectors" are, my approach is probably idiotic, and I'm probably not even handsome.

So here's my approach, that you may laugh at until someone else posts a better one

I'm going to pretend that neither player nor ball are anything but a small point in space.



Suppose the speed of the player is v_p (vector), and his starting position s_p. The area he may be in after the time "t" has passed is the circle/sphere (depending on 2d/3d) with the center point "s_p" and the radius "|v_p|*t" (with |v| being the length of vector v). RIGHT?!

The position of the ball at any time may be expressed as s_b+v_b*t.

For simplicity, let's ignore the third dimension and simply pretend it would only exist in 2D (that could be a problem when you shoot the ball high into the air, but who does that anyway?! ;))

As the "player-area" is a circle, we can simply calculate when the distance from ball to player is <= |v_p|*t.

Problems: There are likely going to be several "t" for which this is true. We need the smallest t.

The difference vector between startingpos of player and ball is:

s_b+v_b*t-s_p
so in our two dimensions

s_b.x+v_b.x*t-s_p.x | s_b.y+v_b.y*t-s_p.y

for the length of said vector, we get:

sqrt( (s_b.x+v_b.x*t-s_p.x)² + (s_b.y+v_b.y*t-s_p.y)² )

and our condition would be

sqrt( (s_b.x+v_b.x*t-s_p.x)² + (s_b.y+v_b.y*t-s_p.y)² ) <= |v_p|*t.

Of course, there may be several (or zero!) "t" for which this is true.

We may assume that the smallest "t" is the t for which said condition is "barely" true, i.e. for which the length of our vector is "exactly" |v_p|*t. Let's call this "t" "t0", then we get

sqrt( (s_b.x+v_b.x*t0-s_p.x)² + (s_b.y+v_b.y*t0-s_p.y)² ) = |v_p|*t0.

I'll probably make mistakes in the following.

(s_b.x+v_b.x*t0-s_p.x)² + (s_b.y+v_b.y*t0-s_p.y)² = (|v_p|*t0)²

then we get

t = (sqrt( - s_b.x² * (v_b.y²-|v_p|²) + 2*s_b.x*(s_b.y*v_b.x*v_b.y + s_p.x*(v_b.y² - v_p²) - s_p.y * v_b.x*v_b.y) - s_b.y²*(v_b.x²-|v_p|²) - 2*s_b.y*(s_p.x*v_b.x*v_b.y-s_p.y*(v_b.x²-|v_p|²)) - s_p.x²*(v_b.y²-|v_p|²) + 2*s_p.x*s_p.y*v_b.x*v_b.y - s_p.y²*(v_b.x²-|v_p|²) ) - s_b.x*v_b.x - s_b.y*v_b.y + s_p.x * v_b.x + s_p.y*v_b.y )/(v_b.x²+v_b.y²-|v_p|²)

(We also get another solution for t, but that one would be negative and thus, wouldn't make sense).

Thats it. Because this is very complicated, here is the formula as a graphic:

LINK. Be warned: The graphic is almost 2400 pixels wide.


Is that correct? NO IDEA. Sorry. I actually just asked my almighty calculator to solve that for me. So there is a good chance for me accidently entering wrong things or having typos when I got this. So you may want to check the math here.
Well, you probably don't really want that, but you know...


-----

Because that is such a complicated formula, it might be worth to think of easier, not as accurate approaches, for instance, by using the dot-product between difference vector of startingpositions with the velocity-vector of the ball, and dividing that by the length of the velocity-vector of the player..... Well... okya, that wouldn't work, but something along these lines might be wiser.

Now: Let us wait until someone gives us a better approach and/or shows us how wrong my approach is.

find the distance(vec_sub) between ball and players

then using resulting vector's components:

distance =

distance/speed = time.

Quadraxas: That would work if the ball didn't move. Adding both velocities may also be a possibility, but you have to take care of their directions somehow (the behaviour is different when the ball is moving towards the player as when its moving away from the player). Still, maybe its accurate enough for the situation David is in (or: "Mr. Lancester is in." I don't want to come across as rude!)??

But maybe something like that could be used as said easier approach...

semi-pseudo-code

vec_set(tempb,s_p);
vec_sub(tempb,s_b);
vec_set(temp,v_s);
t = vec_length(tempb)/(vec_length(temp)+vec_dot(tempb,v_b));


This time, I didn't think that hard about it, so maybe, it has to be minus vec_dot, or something completely different altogether. Maybe I shouldn't have posted this before thinking more thoroughly about it?!

EDIT: It should also be mentioned that my approach further up can be adjusted for different movements (i.e. the player needs to accerlate first, or the ball may fly in a different curve.)

If you calculate it "every frame", you can get ball as it's like "still".

Thank you for all your help guys

I have checked out the source code for that book but I'm really unfamiliar with C++, maybe buying the book would help alot but I'm putting that idea on hold for now. Thank you Frank.

I need to attempt to get my head around all this and try and implement it.

Error what is the v_s variable in this code:

I believe error is almost right with his diagram - I was thinking a straight trig answer, given interception is going to be a right angle intercept using a ratio of player_speed:ball_speed for the lengths. Sadly, it doesn't actually become a right angle, so that doesn't work..

Having played around on a piece of paper, I believe the following should work:

vars: ballSpd, guySpd, (new)timefactor
vectors: ballPos, guyPos, (unit-vector)ballDir, (new)guyDir, (new)interceptPos
angle: (new)delta

delta = vec_sub(ballDir,vec_sub(guyPos,ballPos));
//delta should be the angle of divergence of ball direction from ball to guy direct.
timefactor = vec_dist(guyPos,ballPos)/(guySpd+ballSpd)/cos(delta);
guyDir = 360-vec_sub(guyPos,ballPos)-90-delta;
interceptPos = ballPos+(vec_scale(ballDir, ballSpd*timefactor);

I may have problems in there, and could provide my scribble page if neccessary, but that may help.

Also happy to take a look at code and try and get it working myself if its screwy

Don
have a great day

PS. David - did you get my PM?

Argh, sorry. That one is supposed to be "v_p" - as in "velocity of (soccer) player". Why is it "v_s"? Probably because in the process of thinking about this, I actually thought in german, a language that uses the word "spieler" for "player". Sorry.

--

Gumby22:
The diagrams would definately be helpful, but I do have a few questions

delta is supposed to be the angle, right? Then shouldn't you use vec_dot and either normalize this vector vec_sub(guyPos,ballPos) or divide by its length? (ballDir has the length 1 according to your definition, so thats fine).
To get the angle then, we'd have to do "acos", but since we're only going to use "cos" anyway, we can simply keep it like that, but then, we shouldn't have "cos(delta)" and instead "just" delta.

I suppose you also need to put smoe brackets between the "timefactor"-line.
The next line, however, is where I have most problems - guyDir is, as I understand it, a vector, right? But in the "guyDir"-line, you use both constant numbers (270, to be exact), as well as vector"pointers" (vec_sub). Maybe you want guyDir to be an angle, but then, you'd have to make the resulting "vec_sub-vector" into a "number".

ARGH. Okay, I... am confused.
I don't know about the other users, but I would certainly have an easier time if you could provide diagrams or your scribble page

I've been tweaking it for ages, test all your code. As I can calculate the position of the ball if I know the time variable, I transition the time from a variable 1-500 frames, calculate the soccor ball's position, once I have that position I calculate where the player will be if they run to that position, I then use vec_dist to compare the distance and once I find the spot which has the smallest distance from the player to ball then I store the time variable and compare it to the other players on the field.

It gives me bugs at times, and has certain issues I've had to work around, but it's working to some extent...hopefully I'll either find a solution or get this tweaked better.

Thanks heaps for your help. If anyone has a working formula for this code please let me know. It's the same as getting an ai enemy missile launcher to fire at the position the player is moving to.