Building An Analytical Physics Engine - Pt.1

Hello Gamasutra, this is my first post and I'm going to talk about a different approach I've taken to making a physics engine. I've worked in isolation so far and I'm very interested to see the reaction of programmers/developers with experience of physics engines, even if their reaction is to recoil in horror at my ill informed approach, all comments are demanded!

Analytical Physics Engine.

Recently I've been investigating an alternative approach to making a physics engine. I'm no expert on physics engines so my approach to the problem wasn't initially influenced by the more traditional approach. The project is taking shape now and i would like to throw the idea out to the community to get some feedback on it. In future blogs I want to talk about the strengths and limitations of the analytical approach to physics engines and finally compare the applications of a traditional physics engine to my analytical one.

In this first blog post I'll try to outline how the analytical approach is taken and why I took it. I wont comment on the limitations or advantages too much yet, I'll leave that up to debate till later posts.

Analytical vs Numerical methods:

When I use the term analytical methods I'm referring to the method used to resolve a mathematical or algebraic problem. The alternative approach to the analytical method is the numerical method. A good problem to look at (and a large problem in the physics engine too) that demonstrates the differences between these two approaches is root finding. Say you have an equation ax^2 + bx + c = 0, and you want to find the roots (find the possible answers for x) you can use the well known general quadratic equation which would be the analytical approach or you could make a guess as to what the answer was, put this back into the equation, adjust your guess based on the result of the previous one, repeat until you have a satisfactory answer. This simple problem highlights the difference between the two methods, the analytical approach attempts to find an exact answer in terms of the coefficients (a, b and c in this case) where as the numerical method uses an iterative approach to slowly increase the accuracy of an answer until satisfactory. In this case I doubt there would be many people would would take the numerical approach because of the relative simplicity of the general equation but if you were to look at ax^4 + bx^3 + cx^2 + dx + c = 0 you may turn to the numerical method as the general solution for quartic equations is an order of magnitude more complicated and if you start to include terms of x^5 and higher you will be forced to take a numerical approach as no general equation exists (to my knowledge anyway, please prove me wrong here as I could find a use for such an equation).

Different Approaches:

So how does all this relate to a physics engine? A large issue in physics engines is collision detection, detecting the point at which two objects collide. The way this is generally done is to use a method that tests for overlapping objects and run this test on objects every time they are moved by a small amount. This is in essence a numerical approach to finding out if the two objects will collide. An analytical approach would be to evaluate a single equation to test if the objects collide without the need to move the objects. The equation in question would be the equation of the distance between the objects over time. For a linear path with a constant velocity this equation is reasonably simple, in the case of two circular objects it takes the form of a quadratic equation which we know how to solve easily. The result of the equation should be the time that the objects will first first start to overlap and the time that they finish overlapping (or no results if they never overlap).

At this point I would like to point out a limitation of the numerical physics engine which was one of the reasons I ventured down this analytical avenue, If two objects are far apart and will never collide the numerical physics engine wastes much time checking and rechecking (I understand that a broad-phase check will speed this up but you will still be doing many broad-phase checks) to see if the will collide every time they are moved. In the analytical approach we evaluate a single equation and from that point on we know they will never collide.

This would be a good point to talk about the differences in architecture too. A numerical physics engine will generally store the state of all objects at a specific point in time and iterate forwards through time. The analytical physics engine stores the state of objects over time, i.e. it will store the path of an object (some might point out here that the state of an object in the numerical physics engine is equivalent to the path of the object over time as you store velocity acceleration etc, however the analytical physics engine also stores the start and end point of this path and any subsequent or previous paths the object has taken).

Promising Properties:

There's one particular property I was trying to exploit with the analytical approach. In a physics engine there may be times of heavy and light load, i.e. times when not much is happening and times when a lot of things are happening. What I wanted to do was to let the physics engine get ahead when there was a light load in order to have an extra buffer of time to cope with heavy load. This means the physics engine runs ahead of viewing time and is powerful optimisation which frees the engine up to handle spikes of very heavy loads without any perceived slow down.

An astute observer will point out to me at this time that to do so would be a waste of time as the very second that a users input modifies the state of an object all of the computation made about the future state of objects in the engine would be invalidated. This is "partially" correct, the crucial term here being "partially". When the user makes some dynamic input to the engine it is theoretically possible to separate out exactly what has been invalidated and what is still valid and then only re-evaluate the invalid results.

Being able to achieve this gives us the first major advantage of the analytical engine, the ability to balance load in a scalable, general way throughout the entire engine. This advantage is mitigated very slightly in the case of dynamic input, it can't work out ahead what the user is going to do so if the user does something which instantly causes a heavy load on the engine it can't balance that load, but if the user does something with causes a heavy load to occur a second or two later (like the time it takes for a gun to charge or a rocket to reach its target) we can balance out the heavy load by working it out ahead of time.

Bad Omens:

I'll also now touch on a big limitation of the analytical approach, architectural and algorithmical complexity. It was tediously difficult to make this work in an effective way, I've rebuild the entire engine from scratch about three times so far. After each rebuild there has been an agonising period of fixing horrendously fiddly bugs. At some point I found myself implementing a general solution to quartic equations and in turn cubic equations for which I've not found any scripted examples online and require some maths knowledge to understand, this is not the last of the sparsely documented maths that is required. As most people take the numerical approach there is far less in the way of online help for the types of problems and equations I needed to solve. The difficulties I've faced are significant enough to list as a limitation of the analytical physics engine, while not limiting performance this is a significant development overhead.

I'm going to stop talking about the innards of the engine here and in my next post hopefully move onto more of the limitations, advantages and applications. Some programmers may notice that there are still technical questions to be answered but I don't want this article to be too technical. If there's any indication from comments that there are specific technical questions people want clarification on I'll try to cover them.