Contents |
|
Watch Your Step!
Even with a robust integrator such as RK4, there will be times when the simulation will be in danger of blowing up. To keep this from happening, you may have to reduce the step size at times. At other times, however, a large step size works fine. If my simulator only has a single fixed step size, I cannot take advantage of these facts. If I vary the size of the steps according to need, I could use large steps when possible without sacrificing stability.
This is how it works. I take full step using my current integrator, then take two steps half the current step size, and compare the results. If the error between the two results is greater than a threshold, then the step size should be reduced. Conversely, if the error is less than the threshold, the step size could actually be increased. This form of control is known as an adaptive step size method. Adaptive methods are a major area of research in numerical analysis, and can definitely improve simulation performance. I chose not to implement adaptive step size controls in my simulation. However, this is an area where you could improve the simulation.
Other Techniques
Differential equations are not easy to learn and understand. However, the programmer who pursues this knowledge has many weapons in his arsenal. As witnessed by the birthdates of Euler and Taylor, this research has been going on for centuries. If you ignore this work and strike out on your own, you’re doing yourself a great disservice. Knowledge is available to the developer as never before. While working on these algorithms, I was able to cross-check formulas and techniques in many different sources.
In fact, I’ve barely scratched the surface of the field. The integrators I’ve described (all explicit one-step methods) represent only a subset of the methods available to the programmer. Implicit integrators will also work. For example, an implicit Runge-Kutta integrator trades greater computations per step for greater stability in particularly difficult differential equations. Also, the one-step nature of these integrators reflects the fact that the method does not consider any trends in the past when calculating a new value.
In addition to these one-step methods, there are also multistep methods, extrapolation algorithms, predictor-corrector methods, and certainly many others. Clearly, there is plenty of ground for the adventurous programmer to explore. The book I used, Numerical Algorithms with C, does a good job of comparing different methods during a variety of test conditions.
For this month’s sample application (available from Game Developer’s web site), I have implemented both the midpoint method and Runge-Kutta order 4 in the dynamic simulation from last month. You can switch between integrators and adjust the step size and simulation variables to get a feel for how each performs.
For Further Info
In addition to the references cited last month, a couple of other sources proved very valuable during this article.
• Faires, J. Douglas and Richard Burden. Numerical Methods. Second edition. Pacific Grove, California: Brooks/Cole, 1998. This book provided a great discussion of measuring error in numerical solutions. It also contains a great deal of source code for all the algorithms.
• Engeln-Müllges, Gisela and Frank Uhlig. Numerical Algorithms with C. , New York, New York: Springer-Verlag, 1996. In addition to the fine sections on the methods discussed in this column, this book describes and compares a great number of other numerical methods. Additionally, the book has a great number of references to articles on the topic.
• Press, William H. et al., Numerical Recipes in C. Cambridge, England: Cambridge University Press, 1998.
While not as strong a reference on these topics, this book may be interesting to many, as it is available in electronic form. See http://www.nr.com but also check out a critical discussion of it on http://math.jpl.nasa.gov/nr/nr.html
Jeff Lander is the technical director of Darwin 3D where he spends time calculating his rate of procrastination with respect to his articles. E-mail optimization suggestions to mailito:"jeffl@darwin3d.com".
________________________________________________________