Projectile Calculation in Discrete Time

Game Mechanics
#1

My goal is to determine if/when a particle with a given position will land on a platform. The particle moves in two dimensions without friction according to:

x += vx; // Positive is right
y += vy; // Positive is up
vy += gravity; // Negative constant. There is no terminal velocity.

The particle “lands” on the platform when the segment [(x, y) (x+vx, y+vy)] intersects the segment [(left, top) (right, top)] defined by the platform’s boundaries and only while it is falling. The top boundary of the platform and initial y position of the particle are not necessarily zero. If the particle were fired vertically, crossed the platform going up and fell back on top of it, the second intersection would count as the “landing.” No collision detection is done for the purpose of this simulation.

I would like to use this to quickly determine whether projectiles fired by a player/AI will possibly collide with non-moving platforms some time in the future. What process should I use to check whether the particle will land in the right location and return the (ceiling of the) time it lands. (I can figure out the math, but have a feeling I am overlooking something either extremely obvious or very subtle. I wanted to give a detailed description of the problem.)

#2

Just simulate it. It’s incredibly cheap to simulate, and will give you an accurate result, with barely any effort (developer time is a valueable resource too - don’t try to find the ultimate solution)

#3

It’s part of an AI system. It gets called a lot. That would be the normal operation, but sometimes there are a lot more dead ends that don’t need to get explored. I currently weed out predictions if the object falls off the bottom of the screen, but want to flag cases earlier in my best-first search with objects that are on their way into falling into the abyss.

#4

Here’s a function of time that determines the y position of the particle.

f(t) = y0 + t / 2 * (2 * vy0 + (t - 1) * g)

I can calculate thse times:
L = (left - x0) / vx; L+ = ceil(L); L- = floor(L);
R = (right - x0) / vx; R+ = ceil®; R- = floor®;
P = floor(vy0 / gravity);

I can use the function to see if the particle crosses the top boundary of the platform using different values depending on the case. For example, if vx0 > 0 and x0 < left, then the particle definitely lands on the platform if f(L+) > top && f(R-) < top or if L < P < R && f§ > top && f(R-) < top. Unfortunately, if the particle lands near the edge, it requires testing f(L-) with f(L+) or f(R-) with f(R+).

I may skip the edge conditions and use conservative assumptions involving L-, R+, and P, which I think should never have false positives but no false negatives. I’m also assuming accumulated rounding errors are negligible between the iterative original version and parametric prediction version.

Another option is to find the time after peak height where y = top and checking if (left < t * vx < right), but I think there are a lot more operations involved. (Though the difference one way or the other might not be enough important if the above works.)

(Edit) Here’s a picture. The time numbers aren’t rounded, but they still look like they fall pretty close to the original line. I think the image covers every case. It looks like I only need to calculate three y values and that the logic is pretty simple. Looks good enough to me, but I still feel like I’m overlooking something, though.

#5

USE FIXED TIMERATE SIMULATIONS AND SIMPLE INTEGRATION.

#6

Why not use some physics and quadratic equation?

Simple Physics, using this equation:
s = 1/2 * a * t2

using this, the location of the projectile at time t after the calculation will have a y-coordinate of y’ :

y’ = (u * t + 1/2 * gravity * t2) + yi

where u is the y-velocity (vy) of the projectile at the current time.
and yi is the y coordinate of the projectile at the current time.

when y’ is equal to the y coordinate of the platform, there is a chance the projectile will collide with it, we can work out the time that this will occur by doing this (where yp is the y-coord of the platform:

y’ = (u * t + 1/2 * gravity * t2) + yi
but y’ = yp
therefore, yp = (u * t + 1/2 * gravity * t2) + yi
(u * t + 1/2 * gravity * t2) + yi - yp = 0

you can then use quadratic equation to find t, the times when the y-coords are equal (there will be 2!). Just note, sometimes the y-coords will never be equal and if this is the case your calculation will involve finding the square root of -1 (not sure how java proceeds with this).

Then all you have to do is find the x-coord of hte projectile at this time and see if it matches up with the platform.

x’ = xi + ( t * vx)

(assumes constant vx), where xi is current projectile x-coordinate.

then,

if (x' < right && x' > left) {
   the projectile will collide at t!
}
#7

Concrete math, ignoring difference in computation methods in floats:

xn = n vx + x0
yn = (0.5a(n-1)+vy0)n+y0

(EDIT: I had a misplace paren…opps)

#8

I don’t want to keep a bunch of time variables floating around. My last calculations were based on the formula for the sum of an arithmetic sequence. Which makes it compatible with x += vx; y += vy; vy += gravity; If I want to use a parabolic equation, it needs to pass through the same points for the prediction and the step-by-step simulations. Which means I either find an expression to use after the y += that follows a real parabola or work with a different formula for predictions. (I’m not sure what the consequences are for ordinary collision detection either way, though.)

@Roquen - Substitute the n for t and rearrange the equations and you have the same one I do. What method did you use to get it and what were you suggesting?

#9

You would used physics Projectile Motion Time of Flight equation.

#10

I forgot that I don’t normally factor in continuous acceleration for simplicity sake. Integrated speed (vy = vy0 + t * g) to get position. (y = t^2 * g / 2 + vy0 * t + y0) Then subtracted y0 and substituted t for 1 to get delta y = g / 2 + vy * t.

x += vx;
y += vy + gravity / 2; // Is this correct?
vy += gravity;

So that means it’s possible to use normal projectile equations. I think that means that calculating the exact time of a a given y value is about as simple as a single y(t). Square roots probably aren’t expensive. I think I will also try to expand this to walls, ceilings, and slopes. I thought of a way to check if a projectile collides with an AABB using left/right/peak times, which was cool. Some methods I thought of for walls, ceilings, and other things work the same way no matter what y(t) is. I plan to look for a better way involving plain parabolas though…

I do wonder how I should do step-by-step collision detection. I’ve tried exact line segment based intersections before, but I hadn’t planned to do that in this case either. Exact parabola based intersections would be a pain. I could probably use cheap collision detections methods and shorten the length of the platform seen by the prediction just so things fall closer to the center of a platform.

#11

That doesnt look right, i cant be bothered going over to my physics notes, so this is what I googled which is what i got in my notes I believe:

[quote]General:

We can use the following kinematics equation:

vf= vo+ at

Subscript it for y:

vfy= voy+ ayt

Solve it for t:

t = (vfy- voy) / ay

Plug in 0.0 m/s for vfy:

t = (0.0 m/s - voy) / ay

If the original y velocity and the y acceleration, i. e., the acceleration due to gravity, are plugged into the above equation, it will solve for the amount of time that passes from the moment of release to the moment when the projectile is at the top of its flight.
[/quote]
http://zonalandeducation.com/mstm/physics/mechanics/curvedMotion/projectileMotion/generalSolution/generalSolution.html
about halfway down the page
heading is “How much time passes until the projectile is at the top of its trajectory?”

in the equation its to how long it takes to get to the top, to get how long it takes to get to the other side, just double the answer it gets.

EDIT: Ay is the gravity btw.

I never tested if this actually works in games, but I assume it would, you just to get the correct values.

#12

For once, I agree with Roquen. This is the simple & quick answer.

#13

Indeed they are the same. I used finite difference. I’m suggesting everyone to use fixed-timesteps…well, or better use use a physics library (that fits one’s needs) which uses fixed timesteps is even better.

#14

In your very first post you asked for the time when it would occur.

[quote]My goal is to determine if/when a particle with a given position will land on a platform
[/quote]
The answer you get for the ‘t’ variable in my equations simply tells you when the collision will occur, ie. after t logic updates. My explanation was probably a bit long and tedious, pretty much all it takes is two equations to solve if it will collide, and when it will collide. If you want, I can help you out with rearranging and such.

#15

Fixed-time-step means the same thing as discrete time. Discrete means you can have values of 0, or 1, or 2, and so on, but not 0.5, 1.234, or 2.0001.

[quote=“hvince95,post:14,topic:40303”]
I want to predict the time in the future where a collision occurs. I do not want to save old x/y positions/velocities or time stamps. I have an update function that moves an object with an x-velocity, y-velocity, and position. The position and velocity of an object at time t would be a function of only its state at t-1. Not a function of t relative to the beginning of time or relative to some arbitrary time stamp from the past.

Predictions, on the other hand, need to be valid given a function of t and the present velocity/position with t = zero being the present.

[quote=“hvince95,post:14,topic:40303”]
It wasn’t tedious, though you did use frightening notation (such as y’). One of the problems with your post is that you use a parabolic equation as the basis of your equations. Given the version of the update function I had at the time (y += vx;), a real parabola doesn’t give the same results.

y’ = (u * t + 1/2 * gravity * t2) + yi
y = 1/2 * gravity * t2 + v * t + y0 = f(t)

Let g = -1, v = 2, y0 = 3.

[tr][td]f(0) = 3[/td] [td]y0 = 3[/td][/tr]
[tr][td]f(1) = 4.5[/td] [td]y1 = 5[/td][/tr]
[tr][td]f(2) = 5[/td] [td]y3 = 6[/td][/tr]
[tr][td]f(3) = 4.5[/td] [td]y3 = 6[/td][/tr]
[tr][td]f(4) = 3[/td] [td]y4 = 5[/td][/tr]

So… it looks like a parabola, but it’s not. The equivalent equation h(t) that passes through the points yn is already posted here. The step-by-step simulation needs to be the same as the prediction function. However, now I think I can replace yn+1 = yn + vyn with yn+1 = yn + vyn + gravity / 2. And then both processes will give the same results. I’ve done the math for both the parabola and arithmetic series equations (and found t is a little simpler to calculate directly using a parabola than an arithmetic series,) but I’m not done yet.

I’m left with the following considerations:

  • How expensive is a square root relative to multiplication?
  • If finding t directly is slower (it is for anything besides flat horizontal platforms), should I drop the requirement optional condition or find t in two steps (prune the relatively large amount of bad trajectories and only calculate t for the remaining ones)? *
  • How can I apply this to more complicated structures, like walls, ceilings, or slopes? **
  • b[/b] If the object is assumed to travel in an arc for the prediction, how should I ensure actual collision detection in the step by step method?
  • This is extremely specific to my application, so I don’t expect an answer for this. I’m just writing it to summarize my train of thought on this. - I may drop this requirement mainly because I discovered I can apply my prediction method, no matter what it turns out to be, to other objects, including hills, walls, ceilings, solid blocks, AABB based targets, and moving platforms (but not necessarily with precise collision times). It would have been very helpful if only the simplest case (as described in my first post) were possible, but it’s not really needed as an “optimization” anymore. Though it still could help for something else.

** This can be done by looking at the y position of the particle before an after it passes by an object (assuming it goes through it). It’s sort of like an intersect function for rectangles. For example, collision with a wall is simply f((wallX - x) / vx) > bottom && f((wallX - x) / vx) < top… So I’ve solved this on my own, too, slightly differently than my original thoughts.

The last part is currently my biggest concern. If the predicted collision time for a simple vertical platform was 10.5 for example, the positions of the object at times t = 9 and t = 10 where on opposite sides of the platform but didn’t individually intersect with it, then what method should be used to detect collision in the actual step by step process?

#16

My advice, you are going to need to use time steps and vectors. At time (t) each object is going to move from position A to position B.

Where t is time, O1 is Object 1 (x,y), and O2 is Object 2(x,y)
(t) 0 ; 1; 2
O1 10,10; 20, 20; 30, 30
O2 11,11; -10, 0; -30, 20

If you draw lines in-between each step, you can check for collisions while the objects are moving. This should give you a rough estimate even if gravity is involved. The biggest issue with this method is if a Object moves in a short parabola. In a case where gravity is involved, you will want to create a shaded region [Rectangle] deciphering the max flux the Object can move.

If a ball moves from 0,10 to 10, 10. If the previous information had the ball move from -10,0 to 0,10. You can say that the ball vector can’t move higher than (5 pixels). So to check for a collision in that case, you make a binding box for the parabola (Rectangle [5,-10] - [0, 10]) and check for collisions using the box.

Other than that, every single method described here is very good for solving the problem. If you want to do it every time step, you are going to have to use the object position to create a line that you can use for collisions every frame. It will be very slow, but it will be very thorough.

#17

[quote=“ctomni231,post:16,topic:40303”]
Am I being trolled by you guys? ???

#18

I don’t think everybody reads the topic. They jump in and post their suggestion. It happens all the time, in many threads.

[quote]+ How expensive is a square root relative to multiplication?
[/quote]
Benchmarking at this level is rather hard, because multiplications are so blinding fast, that you’re most likely waiting for memory, not for ‘blocking’ instructions.

Math.sqrt() is however noticably slow(er), and therefore its performance is easier to measure. My guestimate is that it’s between 50 and 500x slower.

#19

What’s the prediction for? AI? I have been reading the thread…but I don’t have a clear grasp of what it is that you’re really attempting to solve.