Foundations

Successful prediction of movement requires a minimal understanding of Newtonian physics. No need to worry; we'll keep it down to accessible concepts. This approach is at the foundation of physics engines—although it is very simplified here.

Physical State

All objects have a set of properties that define them as physical things: shape, size, or weight. These properties combine to determine the movement of objects. To understand the behavior of objects, their properties are modeled—including velocity, acceleration, and center of mass.

Physicists have been able to express relationships between these variables, so they can be used to solve problems. For example, the velocity is the derivative of the position x (that is, the position changes based on the velocity) and the acceleration a is the derivative of the velocity v. (That is, the velocity changes based on the acceleration.) In physics, dots are the preferred notation for derivatives with respect to time (they both are):

The laws of Newtonian physics enable us to determine some of these values (for instance, the acceleration based on force and mass). However, we need calculus to compute the other values indirectly. This allows problems to be solved or simulations to be performed—both involving the movement of objects.

Numeric Integration

The biggest problem in physics implementations is generally to keep track of the position over time. We know the velocity is the derivative (that is, rate of change) of the position, so the position is the integral (that is, the accumulation) of the velocity. Essentially, it's often difficult to exactly determine the position.

The algorithms used to compute values that change over time are known as numeric integrators. Integrators compute the values of the position x(t) and velocity v(t) as a function of time t, generally in terms of previous values.

One of the first and simplest solutions to do this is Euler integration [Bourg01] (referred to as kinematics). The idea is to estimates the next values (with time step Dt), based on the derivative and the current value:

This means that we compute the next value of the velocity by adding the acceleration, and add the velocity to the position to get the next position. This is known as explicit integration, which involves barely more than vector algebra.

Sadly, Euler integration has many problems in practice. Indeed, the acceleration often changes between the time steps Dt, and there are collisions to deal with. Many better solutions for numeric integration have been developed, which work very well on both solid objects and elastic ones. Although these are of great benefit to applications in physics, AI rarely requires more sophisticated solutions.