4

I have a huge array of 30x100 representing a football field. I make players move in it. However, when the ball is throwed, I need to determine if other players are within a +/-1 reach of the trajectory to possibly intercept the pass.

Since some (and most) passes are thrown diagonally, I have a hard time figuring out how to determine an algorythm to evaluate such thing.

My field looks like

1 2 3 4 5 6 7 ...
2
3
4
5
6
7
...

Characters can only move from integrers (so each has a set of coordinates at every moment, such as (3,2) or (20,90).

What would be the simplest way of finding out if a player is within a certain range of my pass trajectory (say the pass goes from (2,4) to (30,15))?

Adam Strudwick
  • 12,671
  • 13
  • 31
  • 41
  • Same question except not specific to PHP: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment. The answers there cover the slightly easier case where what you want is the distance to the *line*, and the more complicated one -- which I think is what you want here -- of the distance to the *line segment*. If the difference isn't clear: is the distance between (-1000,1) and the line from (0,0) to (1,0) 1, or is it about 1000? – Gareth McCaughan May 10 '12 at 21:47

3 Answers3

3

So you have a passer at ($x0, $y0), a place where the pass will come down if nobody catches it ($x1, $y1), and a potential receiver at ($x, $y). You want to find out the distance between the receiver at ($x, $y) and the line from ($x0, $y0) to ($x1, $y1).

That's given by this equation:

$d = abs( ( $x1 - $x0 ) *  ( $y0 - $y ) - ( $x0 - $x ) * ($y1 - $y0 ) ) / 
    sqrt( pow( $x1 - $x0, 2 ) + pow ($y1 - $y0, 2 ) );

You can find a derivation here.

That only gets you the distance to the (infinitely long) line, however, which may be outside the line segment containing the pass. To get the right answer, see Grumdrig's answer here: Shortest distance between a point and a line segment

Community
  • 1
  • 1
Mark Reed
  • 91,912
  • 16
  • 138
  • 175
  • Although true for two points, this is slightly less useful for a point and a line. – Ignacio Vazquez-Abrams May 10 '12 at 21:46
  • @IgnacioVazquez-Abrams I think we are almost at it with your equation. As you said, this gives us the distance to the infinite line. However, with a simple if/else statement, I could make sure that the "3rd player" is within the min-1 and the max+1 "y" coordinate of the passer and the receiver, or else he cannot intercept. – Adam Strudwick May 10 '12 at 22:03
  • I think you want Grumdrig's answer: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment – Mark Reed May 10 '12 at 22:19
  • @MarkReed I do not understand why he's using a float there. Also, what is the dot function of C++? I prefer your 100% PHP solution, even though I need to add an if/else condition to check whether I'm off the segment. – Adam Strudwick May 10 '12 at 22:28
  • http://coding.pressbin.com/65/PHP-Find-shortest-distance-from-point-to-line-segment This is exactly what I need here! – Adam Strudwick May 10 '12 at 22:32
2

Translate the passer to the origin, rotate the trajectory of the ball to the X axis, then check if any of the players near the path (i.e. same x coordinate sign) have a y coordinate between -1 and 1.

Ignacio Vazquez-Abrams
  • 776,304
  • 153
  • 1,341
  • 1,358
  • Seems a good idea. However, how would I rotate the trajectory of the ball to the X axis? I'd need a function to rotate everything, which sounds quite complex. – Adam Strudwick May 10 '12 at 21:49
  • `atan2()` would give you the angle you need to rotate. You then multiply the translation matrix and the rotation matrix, and apply the resultant matrix to the points. – Ignacio Vazquez-Abrams May 10 '12 at 22:06
0

Polar coordinate system is the way to go.

Shomz
  • 37,421
  • 4
  • 57
  • 85