Mathmatical AI vectory question?

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.

yep - i was wondering about the interpolation side you went with, but clean code would definately be simpler.

I'll write up my pseudo-spaghetti tomorrow at work and post with diagrams.

Don
have a great day

You're welcome. But can you tell us where the different approaches failed? Did you try them all? I know my first code was horrifying (not to mention that it actually was no code at all), but the math looks right to me. So why did it fail?

The same goes for all other approaches mentioned here. (I don't know about the content of your PMs, but if there was a solution given, it would surely help others with similar problems if you gave at least basic details as to its content, because I, for one, am totally lost now.)



Sounds like a clever approach. I guess the problem is that for every "t", a different player will be closest to the ball, but you cannot tell this way for which "t" the player will get it (and there may be unlucky cases in which the "smallest distance t" will give you the "longest really-getting-there t". Plus, are you just calculating it once for "t=500frames from now", or are you actually calculating it five hundred times? If so, then my formula may not be so bad after all

EDIT: Ah, so there was a second page already! I didn't really understand your approach, Gumbydon22 (Thats an awesome name right there), so it will be interesting to see diagrams that may help to get it in my head


.....
Is it even real soccer? or is it futuristic soccer with weapons, or maybe MAGICAL soccer? Oh, yes. Magical games. I used to play those.

Your first attempt Error014 really confused me, I don't think it needs to be complex but you gave me the basic idea of calculating where the ball and player will be.

If I know t I can calculate using formulas how far each character will be to the ball. So yes I calculate 500 times, t = 1, t = 2, find the distance from the player to the ball from the player's and ball's position at t. When I've found the shortest distance I store the time value. I then find the player which has the smallest t value and make that player run towards where the ball will be

Nope there was no solution, even the way I have implemented fails at certain times and it's not really clean to calculate 500 times for each character each frame, I could do it less if I wanted. But one set of code which simply calculates what t is at, as you've all so graciously been doing, would be the best solution.

If I were to do the time segment calc's you're doing now David, I'd start with a calculation of half the field traveled, solve for whether its a good solution, or higher or lower, then go halfway to the higher or lower, until the calculation meets the required accuracy - this way you're cutting from 500 to maybe 20? calcs per guy per frame.

Working on my diagrams now...

Don
have a great day

Ok - I think this'll make my approach clearer, but my communication could do with some improvement still.

PDF Version

In text here:

Initial setup: we need to know the time it takes to reach a point at the same time as the ball. From time direction, position are calculatable fairly easily.


In order to solve with simple math, I propose using a 1D direct line between Ball and (each) Guy. This way we can solve with a straightforward timing calculation, and move back to full 2D with simple trig afterwards.


Math:
(Its been years since I did anything for anyone to look at, and my use of math in programming tends to be pseudocode -> compiler -> look at what errors spring up. The following may contain errors in type (int degrees/radians particularly) and code.

G1(2D) is:
G1Pos = BallPos + unityvector(direction to GuyPos) x (ballSpd*T1)

G1(1D math – dist from Ball to G1) is:
G1 = ballSpd*T1 = ballSpd*T1/(guySpd*T1+ballSpd*T1) * vec_dist(GuyPos,BallPos)

Therefore: T1 = T1/(guySpd*T1+ballSpd*T1)*vec_dist(guyPos,ballPos)
T1 = vec_dist(guyPos, ballPos)/(guySpd+ballSpd)

Timefactor = T1*cos(angle delta) //angle delta is angle between (ball-guy & ball–Goal)




I think that will clear it up, and I’ll leave it to you to test with real code. Anything further I write will screw with type errors etc. 

Don
Have a great day

Hey Don

This is the code I'm using from your math:



I'm not sure what it is but it simply fails to work properly in practice...could be my code, could be your math, I'm not sure. Thank you for the code.

I'm using my.movement_speed as the ball's speed value, that's deliberate.

Assuming the ball's speed is 0, this fails to work until I remove "*cos(result)"



David

Ahh - yeah I forgot to mention, it will need special cases for ballSpd == 0 or direction = 90, as these two simulations will be close to division by 0, which is a small no-no.

I'd suggest if the conditions of delta being non-90d, and speed of both greater than 0, then you solve with specific conditions.

I'm wondering if the code works with a delta angle of around 30degrees?

Don
have a great day

I'm sorry for confusing you, but math-wise, that approach should be pretty okay, I think! Maybe if you could put your confusion into specific questions, I could help you?

Honestly, it's actually not that hard. If you understand the graphics and the general concept, you can pretty much take the rest for granted, as thats just "putting it in math-speak" and then getting the proper conditions for "t". I know that it looks confusing, but isn't it at least worth a try? You just need to convert the last line into script (by which I mean: replace "|v_b|" with "vec_length(v_b)", and "x²" with "x*x"), but then, you should have a working piece of code!

It's not a guarantee, mind you, but I still don't see a rpoblem with the math, and I do think that its worth a try. We can try simplyfing it when we find that it works generally.

David - I wonder if you could strip back some code and give us a project prototype to play with, set up as a 2D intercept sim, and error and I could both try to implement our own (and each others) ideas in code?

Don
have a great day

Hi, i don't know if this has already been suggested as i have'nt read every single line but I do mechanics at school and this seems to be a common projectiles question.

The only thing missing is the distance from the ball to the player, but i guess that could be calculated with a vector function or something like that. Once you have the distance the ball is from the player, the time can be found easily.

u = inital velocity
Z = angle to ground
g = acceleration due to gravity (9.8)
t = time

Here are 4 equations of projectile motion...

Displacement (x) = utcosZ
Displacement (y) = utsinZ - 0.5gt^2

Velocity (x) = ucosZ
Velocity (y) = usinZ - gt

Example: distance to player is 30, angle is 15 and intial velocity is 10, trying to find time takes to reach player.

Horizontal velocity = 10cos15 = 9.66....

time = distance/speed = 30/9.66 = 3.11

I know I haven't explained it the best I could, but hopefully this could point you in the right direction.

Sorry if any of this has been mentioned before or that it is totally useless.

DJB MASTER...

Found some time to test out your code error, couldn't get it to work, thanks for all your effort.

Let me know if you see anything wrong with the code:

Uhm. Well. Err.

Okay, so I had to trick the forum by clicking on "Quote", just so I got the complete line.

I then tried to check it and got confused about a billion times. I think there was a mistake, though, but I can't be sure.

I did a quick Replace on it on Notepad .... probably the same you did .... and this is what I got. I'm not putting it in code-tags since that will cut part of the line.


(sqrt( - pow(ball_ent.x,2) * (pow(ball_velocity.y,2)-pow(vel_p,2)) + 2*ball_ent.x*(ball_ent.y*ball_velocity.x*ball_velocity.y + my.x*(pow(ball_velocity.y,2) - pow(vel_p,2)) - my.y * ball_velocity.x*ball_velocity.y) - pow(ball_ent.y,2)*(pow(ball_velocity.x,2)-pow(vel_p,2)) - 2*ball_ent.y*(my.x*ball_velocity.x*ball_velocity.y-my.y*(pow(ball_velocity.x,2)-pow(vel_p,2))) - pow(my.x,2)*(pow(ball_velocity.y,2)-pow(vel_p,2)) + 2*my.x*my.y*ball_velocity.x*ball_velocity.y - pow(my.y,2)*(pow(ball_velocity.x,2)-pow(vel_p,2)) ) - ball_ent.x*ball_velocity.x - ball_ent.y*ball_velocity.y + my.x * ball_velocity.x + my.y*ball_velocity.y )/(pow(ball_velocity.x,2)+pow(ball_velocity.y,2)-pow(vel_p,2))


Huh.

I assumed:

s_b = ball_ent.x
s_p = my.x
v_p = A positive number holding the length of the velocity-vector of the player (i.e., how fast can he run)
v_b = ball_velocity.x

If its not working, it might be because one of those values is wrong...

(or maybe we're leaving acknex variable-range)

No idea if its true, no idea if its going to work. A computer actually solved that mathematical line for me. I only thought up the approach.

Just use simple calculus:
set the players direction to a Euler angle equal to dy/dx of the ball's path.
Can't get easier than that.

That sounds easy, I'd have no idea how to code that though, any ideas? Thanks!

i have coded a solution but it wont work because i use a linear ball speed...
(EDIT: and my solution is still unfinished yet)

Linear ball speed is fine, better than nothing Can't wait to test it!

it will definitely work but i just have some math problems :-D