Post a Comment On: Bram, INDIEvidual in Canada

[Image]I am a game programmer that spends the bulk of his time on writing physics simulations of virtual worlds. In these virtual worlds, there are typically people or vehicles. When such a person or vehicle is not under player control, but controlled by the computer, we often call this AI (Artificial Intelligence) or NPC (Non player character.) A common problem is to realistically move these entities around in the world. A naive way to move these virtual actors would be to write code that sets the new position during each frame of the simulation. This is typically how a ghost in pacman or a space invader is moved on the screen. However, for a proper simulation this is the wrong way to do it. Modern complex games use physics simulations that calculates forces and accelerations. This means that steering an object in the world becomes a very indirect way of steering. The algorithm sets a force (linear, or torque) which results in acceleration, or change in velocity. The velocity, lastly, will change the position and orientation of the object. This makes steering a hard problem: how do you move an object to position X? If X is far away, you would apply force towards X, but if X is near, and we are quickly approaching X, we need to apply force away from X so that we come to a halt on X without overshooting. Luckily, this problem has been solved for us by the engineers in process control. When heating a building for instance, knowing when and how much to run the heater depends not only on the current and desired temperature, but also how the difference between the two have been changing in the past. If the temperature is rising quickly (because the heater was running full blast) it is time to stop the heater, as the the lag in the system will cause the temperature to continue rising. If a lot of cold air is entering the building causing the temperature not to rise much in the near past, heating needs to be increased. For this, the engineers use so called PID Controllers. PID control splits the steering into three different components: Proportional (what is the error right now?) Integral (what is the historic error?) Differential (how is the error changing?) ...where the error is simply the difference between the current value and the desired value. Steering based on the differential of the error means that if we are fast approaching the desired value, we steer away, and if we fast retreating from the desired value, we steer towards. Steering based on integral means that the longer we have had a large error in the past, the harder we steer towards the desired value. Humans actually steer the same way naturally. For instance, when we need to open a door of unknown weight. First we push a little if it is closed. The longer the door remains closed, the harder we push (this is the integral part). And the faster it swings open (error decreases quickly), the less we push it, or even start pulling it. The PID system is nicely adaptive. If a hard wind is blowing the door shut, the integral steering will make that we compensate by pushing harder. This is what is called steady-state-error. The entities in our simulation will seem smarter for it, if they can adapt to changing conditions. The PID controller calculates the required force for us, each time step in our simulation. The error is calculated from desired and actual values. Note that the desired value does not have to remain fixed, it can be a moving target. PID will cope with this automagically, e.g. when trying to aim a rifle at a chaotically moving target. So, are there no downsides to this miracle technique? Well, not really, as long as the controller is tuned roughly correctly. We need to determine with what weights we mix the P, I and D control. We need to select three P, I, D coefficients, and the optimal values are typically different in each application. Personally, I find that selecting P roughly 10 times larger than D, and I somewhere in between always makes my steering converging nicely without much overshoot, and reasonably quickly. Note that all three coefficients need to be negative. (We need to steer against current error, against historic error and against rate of change of error. Just start with some default values (-10, -2, -1) and tweak them with the following guide: When system explodes due to excessive force, lower all coefficients. When overshoot is large, increase D, lower I. When convergence is slow, increase P and I, decrease D. When observed value jitters a lot, decrease P and increase I. It's high time for some code now. The code is really concise, if it carries a little bit of state (previous error, historic error) along with the P,I,D coefficients. //! Scalar PID controller typedef struct { float P; float I; float D; float previousError; // Last error float integralError; // Historic error bool fresh; // If set, we have no 'last error' yet. bool angular; // Angular PIDs have errors wrap around at -pi and +pi. } pid1_t; //! Reset a PID controller. Clears historial error. void pid1_reset( pid1_t &p ) { p.previousError = p.integralError = 0.0f; p.fresh = true; } //! Calculate the steering force based on current value (ist) and desired value (soll). float pid1_update( pid1_t &p, float dt, float ist, float soll ) { if ( dt <= 0.0f ) return 0.0f; float error = ist - soll; if ( p.angular ) { // normalize angular error error = ( error < -M_PI ) ? error + 2 * M_PI : error; error = ( error > M_PI ) ? error - 2 * M_PI : error; } p.integralError = ( p.fresh ) ? error : p.integralError; p.previousError = ( p.fresh ) ? error : p.previousError; p.integralError = ( 1.0f - dt ) * p.integralError + dt * error; float derivativeError = ( error - p.previousError ) / dt; p.previousError = error; p.fresh = false; return p.P * error + p.I * p.integralError + p.D * derivativeError; } And to use this PID controller to aim a turret in a tower-defence game: pid1_t pid; pid.reset(); pid.angular = true; pid.P = -10.0f; pid.I = -2.0f; pid.D = -1.0f; while ( simulating ) { ... float desired = angleTowardsTarget( turret, enemy ); float actual = angleOfGun( turret ); float steer = pid1_update( &pid, dt, actual, desired ); applyTorque( turret, steer ); ... } And that is pretty much it. The only thing to watch out for, is that if the turret suddenly selects a different target, the PID controller needs to be reset, so that the historic error based on previous target does not influence the steering for the new target. This causes a quicker convergence. To do this, just clear the historic error. And there you have it, a smoothly targeting turret that does not need kludges for smooth-in/smooth-out parts of a synthetic animation. Animation is bad, simulation is good. I use this PID code to: Smoothly move my camera. Smoothly reorient my camera. Smoothly have a tank aim at a moving enemy. Smoothly balance a helicopter at a desired attitude. Smoothly push, pull and twist oars of a rowing boat. Smoothly hover a bike over undulating terrain. Smoothly steer a missile towards a fast moving target. and much much more. To see many of them in action, download one of my games, they are free. Search for 'Abraham Stolk' on Google Play or iOS App Store.