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.