{"id":59886,"date":"2018-11-05T08:57:00","date_gmt":"2018-11-05T08:57:00","guid":{"rendered":"http:\/\/www.gamasutra.com\/view\/news\/329944"},"modified":"2018-11-05T08:57:00","modified_gmt":"2018-11-05T08:57:00","slug":"game-programming-deep-dive-3-scenarios-for-movement-prediction","status":"publish","type":"post","link":"https:\/\/sickgaming.net\/blog\/2018\/11\/05\/game-programming-deep-dive-3-scenarios-for-movement-prediction\/","title":{"rendered":"Game Programming Deep Dive: 3 scenarios for movement prediction"},"content":{"rendered":"

The following blog post, unless otherwise noted, was written by a member of Gamasutra\u0092s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company. <\/small><\/i><\/strong> <\/p>\n

\n

We need to use movement prediction in our games more often than we might expect. We, as humans, predict the future position of objects all the time, and we act accordingly to that prediction. For example, when we want to catch a moving ball, we do not run to the place where it is currently in the air or on the ground. Instead, we naturally predict where the ball will be in a few seconds and move toward that predicted position. Based on our prediction skills we can catch the ball easily, or not so easily if our prediction was wrong.<\/p>\n

Here are the examples of calculating predicted movement in a game:<\/p>\n

    \n
  • A trajectory of a grenade, to prevent a character from running towards it.<\/li>\n

    <\/p>\n

  • Firing a projectile in the direction of the predicted place of a moving enemy.<\/li>\n

    <\/p>\n

  • Movement of a vehicle in the close future to allow characters to avoid it.<\/li>\n

    <\/p>\n

  • Predicted position of a replicated object over the network to compensate for the lag.<\/li>\n

    \n<\/ul>\n

    In general, if we want to predict the movement of an object, we need to execute some form of physical simulation. The ideal situation would be if we could simulate the whole physical world for the needed time in the future. In most cases, because of the limited computing power, this is not (yet!) reasonable. However, depending on our needs, we can perform a simplified simulation to get the predicted state of the single object in the future.<\/p>\n

    In this article, I would like to describe three different scenarios of how we typically use prediction in games:<\/p>\n

      \n
    1. Character<\/strong>. In this case, we are interested in a predicted position for a short amount of time in the future.<\/li>\n

      <\/p>\n

    2. Projectile<\/strong>. For projectiles, we want a much longer time of predicted movement including collisions.<\/li>\n

      <\/p>\n

    3. Vehicle<\/strong>. For vehicles, to properly handle the predicted movement, we also need to take into account the orientation with angular velocity.<\/li>\n

      \n<\/ol>\n

      Nevertheless, we still need to remember that this is a prediction. We are not running the full physical simulation. Rather, we want to compute the most probable state of the object in the future.<\/p>\n

      To perform our predictions as a form of physical simulation, we need the basic physical quantity for the kinematic object: a velocity [1]. In general, the velocity is a rate of change of position in respect to time and is expressed using a derivative:<\/p>\n

      <\/p>\n

      However, for our prediction needs, we can use the formula for the velocity during the constant movement, without referring directly to the derivative:<\/p>\n

      <\/p>\n

      where \u00a0is the position displacement (from point \u00a0to ) and \u00a0is the elapsed time (from \u00a0to ).<\/p>\n

      Velocity is a vector quantity, which has a direction and a length. The length of a velocity vector is a scalar value and can be called speed.<\/p>\n

      Our main concern for the character is the prediction for the short amount of time in the future – usually less than 1 s. This is the basic case for the prediction, where we make a few assumptions:<\/p>\n

        \n
      1. We simulate the character\u2019s movement as a point moving along the straight line without any collisions.<\/li>\n

        <\/p>\n

      2. We know the character\u2019s current velocity.<\/li>\n

        <\/p>\n

      3. We assume that the character will continue its movement along the straight line with its current velocity.<\/li>\n

        \n<\/ol>\n

        We start with the formula for the constant velocity from the previous section:<\/p>\n

        <\/p>\n

        But this time we assume that , , and \u00a0are known variables and \u00a0is unknown.<\/p>\n

        We multiply both sides by :<\/p>\n

        <\/p>\n

        Then, we move \u00a0to the left side:<\/p>\n

        <\/p>\n

        Finally, we swap both sides of the equation:<\/p>\n

        <\/p>\n

        and we get the final formula, where \u00a0is the current position of the character, \u00a0is the character\u2019s velocity, \u00a0is the time of the prediction, and \u00a0is our predicted position in the future.<\/p>\n

        This formula has a natural geometrical explanation. The object moves with a constant linear movement, so we are moving the point along the velocity vector \u00a0from the point \u00a0to the point .<\/p>\n

        Below you can find the code in Unity Engine\u2122 with a straightforward implementation of the final formula:<\/p>\n

        Vector3 LinearMovementPrediction(Vector3 CurrentPosition, Vector3 CurrentVelocity, float PredictionTime)
\n{
 Vector3 PredictedPosition = CurrentPosition + CurrentVelocity * PredictionTime;
 return PredictedPosition;
\n}<\/code><\/pre>\n
        In navigation, the process to predict the position in the future is called \u201cdead reckoning\u201d [2] and it uses this formula as the basic computation technique.<\/p>\n
        This is also a simple formula to predict the movement of a character in multiplayer games while waiting for a new network data to arrive [3, section \u2018Display of Targets\u2019].<\/p>\n
        On the image below, we have an example with a geometrical description for this prediction scenario:<\/p>\n
        \u00a0<\/p>\n
        The blue curve marks the movement of the object (dashed blue line is the future movement). Velocity is the derivative of position function, so it lies on a tangent at the point \u00a0[4, section ‘Kinematic quantities’]. Since we are predicting position along the velocity vector, we can observe how a longer prediction time \u00a0will cause the predicted position to diverge from the real position in the future. A shorter prediction time \u00a0gives a better approximation.<\/p>\n
        Acceleration<\/strong><\/h3>\n
        There are situations when we want to consider acceleration in our prediction. In such cases, instead of assuming the constant velocity, we will assume the constant acceleration during the prediction period:<\/p>\n
        <\/p>\n
        where \u00a0is the initial velocity, \u00a0is the final velocity, and \u00a0is the prediction time.<\/p>\n
        The formula for the predicted position \u00a0with the constant acceleration \u00a0is given by<\/p>\n
        <\/p>\n
        As we can see, when there is no acceleration (), this formula still gives the same prediction result as the equation from the previous section.<\/p>\n
        The formula can be easily explained using the graph below for one-dimensional movement:<\/p>\n
        <\/p>\n
        The graphs show a relation between velocity and time. In other words, it shows how velocity (a blue line) changes over time. When the graph is given in such a way, the area under the velocity line (marked with a blue color) is the distance traveled by the moving object [1, section \u2018Instantaneous velocity\u2019]. We can calculate that area as a sum of two figures: a rectangle A and a right triangle B.<\/p>\n
        Using notation for the areas with the initial distance \u00a0and the final distance \u00a0traveled by the moving object, we get the formula:<\/p>\n
        <\/p>\n
        The area of the rectangle A is:<\/p>\n
        <\/p>\n
        The area of the right triangle B can be computed as the half of the upper rectangle:<\/p>\n
        <\/p>\n
        Because the acceleration is given by \u00a0, so . Using that, we can change the equation above to:<\/p>\n
        <\/p>\n
        Finally, substituting for A and B in the first formula for \u00a0we get:<\/p>\n
        <\/p>\n
        By renaming variables \u00a0to \u00a0and \u00a0to , we obtain the formula for the predicted position \u00a0given at the beginning of this section:<\/p>\n
        <\/p>\n
        In the case of projectiles, we are interested in the much longer time of our prediction. Additionally, we want to track the projectile when it bounces off other objects.<\/p>\n
        To perform this prediction, we need to execute a simulation loop and check for collisions in every step. We will assume simple ballistics physics for the projectile moving as a point [4, section \u2018Uniform acceleration\u2019]. Below is the code with the implementation in the Unity Engine:<\/p>\n
        Vector3 PredictProjectileMovement(Vector3 InitialPosition, Vector3 InitialVelocity, float TimeToExplode)
\n{
 float Restitution = 0.5f;
\n\u00a0\u00a0\u00a0\u00a0Vector3 Position = InitialPosition;
\n\u00a0\u00a0\u00a0\u00a0Vector3 Velocity = InitialVelocity;
\n\u00a0\u00a0\u00a0 Vector3 GravitationalAcceleration = new Vector3(0.0f, -9.81f, 0.0f);
\n\u00a0\u00a0\u00a0 float t = 0.0f;
\n\u00a0\u00a0\u00a0 float DeltaTime = 0.02f;
\n
\n\u00a0\u00a0\u00a0\u00a0while (t < TimeToExplode)
\n\u00a0\u00a0\u00a0 {
\n\u00a0\u00a0\u00a0 Vector3 PreviousPosition = Position;
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Vector3 PreviousVelocity = Velocity;
\n
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Position += Velocity * DeltaTime + 0.5f * GravitationalAcceleration * DeltaTime * DeltaTime;
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Velocity += GravitationalAcceleration * DeltaTime;
\n
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ Collision detection.
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 RaycastHit HitInfo;
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if (Physics.Linecast(PreviousPosition, Position, out HitInfo))
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ Recompute velocity at the collision point.
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 float FullDistance = (Position - PreviousPosition).magnitude;
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 float HitCoef = (FullDistance > 0.000001f) ? (HitInfo.distance \/ FullDistance) : 0.0f;
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Velocity = PreviousVelocity + GravitationalAcceleration * DeltaTime * HitCoef;
\n
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ Set the hit point as the new position.
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Position = HitInfo.point;
\n
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ Collision response. Bounce velocity after the impact using coefficient of restitution.
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 float ProjectedVelocity = Vector3.Dot(HitInfo.normal, Velocity);
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Velocity += -(1+Restitution) * ProjectedVelocity * HitInfo.normal;
 }
\n
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0t += DeltaTime;
 }
\n
 \/\/ Return the final predicted position.
\n\u00a0\u00a0\u00a0 return Position;
\n}<\/code><\/pre>\n
        We will explain the code given above in the following three subsections: Simulation loop, Collision detection, and Collision response.<\/p>\n
        Simulation loop<\/strong><\/h3>\n
        The choice of the time step (DeltaTime<\/em>) for every iteration depends on our requirements for accuracy. Typically, this will be the same value as the time step for our physics engine (in Unity Engine the default value is 0.02 s).<\/p>\n
        At the beginning of the loop, before evaluating our movement equations, we store position and velocity in PreviousPosition<\/em> and PreviousVelocity<\/em> variables. This is required to perform collision detection.<\/p>\n
        We are considering only gravitational acceleration, which is constant during the whole movement. Because of that, we can use the formula from the previous section to compute the new position after a given time step:<\/p>\n
        Position += Velocity * DeltaTime + 0.5f * GravitationalAcceleration * DeltaTime * DeltaTime;<\/code><\/pre>\n
        Similarly, the new velocity is calculated using acceleration:<\/p>\n
        Velocity += GravitationalAcceleration * DeltaTime;<\/code><\/pre>\n
        Collision detection<\/strong><\/h3>\n
        The essential part of the loop is the test for collisions, which is described in the image below:<\/p>\n
        <\/p>\n
        We use position from the previous step (variable PreviousPosition<\/em>) and the newly calculated position (variable Position<\/em>) to test if the line segment between them hits any objects. The collision test is performed by the Unity Engine method Physics<\/em>.LineCast<\/em>:<\/p>\n
        Physics.Linecast(PreviousPosition, Position, out HitInfo)<\/code><\/pre>\n
        If there is a collision, the method returns true and stores the result in HitInfo<\/em>:<\/p>\n