Planning movement over pre-determined distance and time

You can talk about almost anything that you want to on this board.

Moderator: Moderators

Post Reply
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Planning movement over pre-determined distance and time

Post by tokumaru »

Hey there, guys. Since a lot of you are much better at math than I am, I figured I'd ask a little question here - Say that I want some object in a game to cover a specific distance in a specific number of frames while accelerating or decelerating. How would I go about calculating the velocity and acceleration values to achieve what I want?

This is using typical 8/16-bit game physics, where an object moves from having its velocity added to its position every frame, and its velocity changes from having some constant added to it every frame.

A simple scenario would be an object at an specific position with a specific velocity, and I need it to stop completely over the course of x pixels and y frames. How would I go about calculating the velocity and the acceleration?

Since the velocity changes by a constant amount each frame, and I know the number of frames I want the whole process to last, this is looking an awful lot like an arithmetic progression, where the length of the sequence is the number of frames, the sum of all the terms is the distance covered, the first term is the initial velocity, the last term is the final velocity, and the difference between consecutive terms is the acceleration/deceleration value. I just can't seem to figure out how to piece all of this together, and calculate some of these variables based on the others.
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Planning movement over pre-determined distance and time

Post by Dwedit »

What exact kind of movement do we want here?

One kind of movement is the Worms problem, where you want to shoot at a target with the basic Bazooka or Grenade. Displacement is known, Initial Velocity is unknown, Acceleration is constant

Let's declare our variables:
X, V, and A are vectors, T is time
X1 = final position
X0 = initial position
X1 - X0 = total displacement (Known)
V0 = initial velocity (Unknown, solving for this)
V1 = final velocity (don't care about this)
AValue = Acceleration (Known, Constant for this problem) (in Worms, acceleration happens due to gravity and wind)
T = total time for it to move (We pick this) (In Worms, it's the fuse length for a grenade, or the time you want a Bazooka shot to fly)

From Physics:
A(t) = acceleration
V(t) = velocity
X(t) = position

V(t) = Integral(A(t), t)
X(t) = Integral(V(t), t)

If A is a constant (calling it AValue here), we get these:

A(t) = AValue
V(t) = AValue * t + V0
X(t) = AValue * t ^ 2 / 2 + V0 * t + X0

Evaluate these at t=0:
A(0) = AValue
V(0) = V0
X(0) = X0

Evaluate at t=T
X(t=T) = X1 = AValue * T ^ 2 / 2 + V0 * T + X0

Then we want to solve for V0, we get this:

V0 = ((X1 - X0) - AValue * T ^ 2 / 2) / T

So that tells you what your initial velocity of the projectile is, given the displacement, the time, and constant acceleration.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Planning movement over pre-determined distance and time

Post by rainwarrior »

A note on precision:

For a linear movement, 8.8 fixed point position+velocity is generally enough to get from one pixel to another on the screen. If you add another order for acceleration, you'll probably need 8.16 position+velocity+acceleration.

This is just a ballpark. If the length of the curve in time or position is extended enough, you could need more precision, but in my experience 8.16 has been sufficient.

A suggested curve:

There are different ways to define a curve. One which I find pretty useful is the Quadratic Bézier where you pick a start (A) and end point (C), then a third point (B) in between which dictates the direction of the starting and ending velocities. (So the curve "approaches" the 3rd point but only touches the two end points.)

Across the curve, it's a recursive linear interpolation, so if you want the point 20% along the curve, you take a 20% interpolation of A to B, and a 20% interpolation of B to C... then you take a 20% interpolation of the two points you just made AB to BC, and that's your midpoint. (See the animations on the linked article.)

That way of calculating probably isn't practical on NES, since there's no multiply, but you can convert the same curve to a starting point, starting velocity, and constant acceleration:
  • Starting point is just A.
  • Starting velocity is 2 * (B-A) / time.
  • Ending velocity is 2 * (C-B) / time. (temporary, not stored)
  • Constant acceleration is (ending velocity - starting velocity) / time.
(Maybe you can kinda see how with the accleration being the result of two divisions by time, it should need twice the precision?)

Finally, I recommend doing these precalculations with more precision and then rounding, rather than just truncating, to 8.16 fixed point. I also think it's worth writing a little discrete simulation of the fixed point math, just to make sure you do end up on the desired pixel. That's important for verifying/discovering the precision needs.

There are a lot of other types of curve which can be similarly broken down into something that's NES-practical, but the Quadratic Bézier specifically is one I've found quite useful in several applications.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Planning movement over pre-determined distance and time

Post by Drag »

And now for perspective #3! :P

I was trying to figure it out with calculus, but was struggling because I'm either rusty or have covid-brain, so I made a chart instead and looked for patterns. Here's my scratch pad:
planned-velocity.png
C = (2x) / (t^2 + t), where t is the desired number of frames, x is the desired number of pixels, and C is the amount you will need to subtract from the object's velocity each frame, given t and x.
V = Ct, where V is velocity the object will need to start with.

To figure this out, I started with X=10, a list of t's, and kept guessing at c until c + 2c + 3c + etc would equal 10. When I found a c that'd work, I plotted the object's movement starting at XPosition=10 and going backwards towards 0 (to create deceleration from 0 to 10), with the plotted number being the step number.

C ended up being X/triangle(t), and then V comes from that.

If this ends up being correct, I'd really like to know how you'd arrive to this with calculus, since it's going to bother me. :P
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Planning movement over pre-determined distance and time

Post by calima »

And for #4, if this is for a cutscene or otherwise the distance is constant, just try different values until it looks cool. Binary searching the space.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Planning movement over pre-determined distance and time

Post by Drag »

EDIT: Disregard this post, the thing I described was just a coincidence and doesn't actually work.

I did some more digging after refreshing up on calculus, and what I did before ended up being the exact same thing Dwedit did, except mine wants to solve for AValue instead of V0. Further, my method needs V0 set to 0.5 in order to get an AValue that matches the "C" values in my table.

I thought to just set t = 1 to get the AValue for 1 step (i.e., what you need to add to V each frame, assuming T is measured in whole frames, t = 1 should be "one frame"), but it doesn't quite work right, where setting V0 = 0.5 works, and I don't understand why. Maybe it's because fixed-step physics is different from continuous physics? That'd be the difference between using an integral vs a reimann sum if I'm not mistaken.

Well, specifically, I know that V0 = 0.5 gives you V = At + 1/2 which integrates to X = (At2 + t) / 2 which is that triangle number my method needed, but I don't understand why setting the starting velocity specifically to that is what works, and I haven't tested to see if you can choose any V0 and just add 0.5, or if 0.5 only works when you actually want V0 = 0.

Specifically, not understanding why something's the correct answer is what bothers me. :P
Last edited by Drag on Fri May 27, 2022 7:34 pm, edited 1 time in total.
Maurício
Posts: 3
Joined: Wed May 25, 2022 5:21 am

Re: Planning movement over pre-determined distance and time

Post by Maurício »

tokumaru wrote: Sat May 21, 2022 10:02 am A simple scenario would be an object at an specific position with a specific velocity, and I need it to stop completely over the course of x pixels and y frames. How would I go about calculating the velocity and the acceleration?
That particular situation is generally unsolvable. You can stop over a specific number of frames or of pixels, not both.

For the situations where its possible:
1) A specific change of speed over a specific distance (no control over time)
There are 3 possible variations:
A) [(final velocity)² - (initial velocity)²] / (2·distance)
B) [(final velocity)² - (initial velocity)²] / [(2·distance) - (final velocity - initial velocity)]
C) [(final velocity)² - (initial velocity)²] / [(2·distance) + (final velocity - initial velocity)]

2) A specific distance over a specific time (no control over change of speed)
Also 3 variations:
A) 2·[distance - (initial velocity · time)] / (time)²
B) 2·[distance - (initial velocity · time)] / [(time)²+time)
C) 2·[distance - (initial velocity · time)] / [(time)²-time)

3) A specific change of speed over a specific time (no control over distance)
Only one possibility, obviously (change of speed)/(time)

* Time in frames, distance in whatever
* For options labeled B, acceleration should be applied each the movement
* For options labeled C, acceleration should be applied each the movement
* For the options labeled A, half of the acceleration should be applied before the movement, and half after
* For case 1 (change of speed over distance), the number of frames will probably be fractional, so you´ll have to adjust everything at the end
* Case 2 can also be used with a fixed final velocity instead, just switch the sign of acceleration at the end, and switch equation B for eq. C
* I presume you can handle quantization errors

Explanation:
Options labeled A are derived from the physical equation of motion Δx = v(0)t + at²/2
Half of the acceleration has to be applied before moving so the speed on that frame is what the average speed would be on continuous time

Options labeled B are derived from the sum of v(0)+a, v(0)+2a, v(0)+3a ... v(0)+ta,
which gives Δx = v(0)t + at(t+1)/2

Options labeled B are derived from the sum of v(0)+a, v(0)+2a, v(0)+3a ... v(0)+ta,
which gives Δx = v(0)t + at(t-1)/2
Last edited by Maurício on Wed May 25, 2022 7:07 am, edited 1 time in total.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Planning movement over pre-determined distance and time

Post by Drag »

Wow! Thanks for the explanation, that cleared up my questions at least.

If I understood right, the equation is different depending on how you update your object's position, and I originally figured out equation B and it was correct. But, to use equation A (the one you'd get if you simply use physics equations), your object's movement needs to represent what the mean speed for that frame was? Otherwise, you'd need to calculate the new position based on the physics equation instead of just adding V to X.

So, the "hack" I found in my second post was just a coincidence. :P
Maurício
Posts: 3
Joined: Wed May 25, 2022 5:21 am

Re: Planning movement over pre-determined distance and time

Post by Maurício »

Drag wrote: Wed May 25, 2022 1:56 pm If I understood right, the equation is different depending on how you update your object's position,
Yes, because if you update the speed, then update the position, you get a different result than if you update the position then the speed.
But, to use equation A (the one you'd get if you simply use physics equations), your object's movement needs to represent what the mean speed for that frame was? Otherwise, you'd need to calculate the new position based on the physics equation instead of just adding V to X.
By the definition of mean speed, yes.
and I originally figured out equation B and it was correct.
(...)
So, the "hack" I found in my second post was just a coincidence. :P
I didn´t respond because I did´t understand what you did (and still don´t)
It seemed you were trying to calculate something to do with ballistic movement (because you mentioned doing the same as Dwedit), which is something else.
I will say that the triangle numbers you got are the result of summing the arithmetic progression of speeds.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Planning movement over pre-determined distance and time

Post by Drag »

Yeah, the thing I did in my second post was incorrect and just happened to work with my test inputs (time=4, distance=10) by coincidence. If I tested with other test inputs, I would've noticed that there was a problem. The fact that I even said "I don't understand why this works" should've clued me off but I'd decided to be lazy instead. :P

As a sidenote, I did Advent of Code 2021 this past winter, and the puzzle for Day 17 is very similar to Tokumaru's original question for this thread; you have a fixed position, a fixed target area, and you need to figure out all of the velocities you can fire a projectile with in order to get the projectile to reach the target area.
Post Reply