LE screen 1

It’s been a while since I updated on the old Liberty Engine so here it is with a lot more polish than the last demo. You still can’t modify the objects or forces just yet, but I sharpened up everything else. It’s running much more efficiently, with stats, an improved console and new keyboard commands. It also includes a “Help” button that will explain all of its functions on mouse-over.

Here is a swf copy as well as an exe. I haven’t seen much of a performance difference between the two:

The default “memory” setting is 60 seconds, so if you play more than 60 seconds it will begin deleting old data. This is meant to prevent the program from filling your computers memory and lagging or crashing. However, you can set the memory value to Infinity and see how much you can hold without slowdown. I found a loss of about 2 or 3 fps with 1 hour of data. I average about 6 or 7 calculated seconds per actual second (Scalc/S) so you should be able to set the rate of time passage to as high as 6 without playback time ever passing up calculation time. But play around with it and let me know how it runs on your machine. I could use the feedback!

With your time rate set to 6, you can get through an hour of simulation in 10 minutes.

Design

There is a great deal of idealism in the design of the Liberty Engine. You might say principles had more to do with it than technical goals. These were my priorities:

  1. Precision: All data and specifically collisions must be precise. At this point the only rounding off occurs due to flash’s technical limitations, but I’ve aimed for accuracy to the 10th decimal place. No collisions are missed, regardless of velocities, and all are calculated exactly.
  2. Repeatability: As a result of high level precision and uniform methods of rounding off data when necessary, experiments in this engine are entirely repeatable. No matter what machine is used to run the software, the same events will occur.
  3. Preservation: Data is treated as sacred and preserved for potential use in any number of ways. The most significant acknowledgment of this priority is the engine’s “memory” of past events. This allows you to scrub back and forth over hours of animation. Data is compressed in different ways to keep it from costing too much space.
  4. Simplicity: The soul of the Liberty Engine concept lies in its ease of use. In the early stages this was a great challenge, but since then its rewards have been great. Engine operation is entirely cut and paste, drag and drop, with minimal for scripting. This engine is built to give the little guys the power of the big guys and the big guys the freedom of the little guys.
  5. Efficiency: The framerate must be stable. Even if it drops down, it must be stable. A stable framerate is predictable and provides for a much better experience than one that varies between high and low values. Also, due to the high level of precision, calculations can suck up a lot of processing power so logic must be employed to make as many safe assumptions as possible and minimize unnecessary work. On the other hand, there are a number of high efficiency coding practices that I’ve ignored for the sake of simplicity. I hope to fix some of this in the future, but clearly it is not high on my list.
  6. Power: Power is the #1 concern of every engine out there, but very few games even take advantage of it. I decided that if you need a powerful physics engine you can take from plenty of others, but I would not set it as a high priority until later in development. Fortunately, the nature of the Liberty Engine gives it a significant advantage from the start. It can’t yet handle as many events as other flash engines, and still doesn’t have contact forces, but in the right circumstances it can blow them out of the water.

How It Works

Everything is coded for a quick pipeline. You drag and drop objects and force vectors from the flash library and they automatically submit themselves to a library of data at the initiation of the engine. This is what it looks like in flash:

LE 04.17.08 flah Image

Equations

Based on the force vectors and object data, equations are calculated to describe the trajectories of each object relative to time. Equations are arrays with lengths equal to the number of terms they contain. Each term is described by a coefficient that will be multiplied by time. The exponent of time (t) is determined by the number and order of terms in the equation.

e = [2,3,4,5]

position = e(t) = 2 + 3t + 4t^2 + 5t^3

Each term represents a derivation of position (position, velocity, acceleration, jerk, yank, etc). Since objects can move over the x and y axes as well as rotate over the z axis, 3 coefficients are needed for each term. These are described with arrays nested in the equation array. Each contains an x, y and z value.

e = [[2,2.1,2.2] , [3,3.1,3.2] , [4,4.1,4.2] , [5,5.1,5.2]]

position.x = e[x](t) = 2 + 3t + 4t^2 + 5t^3

position.y = e[y](t) = 2.1 + 3.1t + 4.1t^2 + 5.1t^3

position.z = e[z](t) = 2.2 + 3.2t + 4.2t^2 + 5.2t^3

In other words, the equation is made up of coefficient vectors multiplied by exponentially increasing values of time. An EquationAnimator function uses those equations to find the position of each object at a given time and update the stage. That allows the engine to function independently of the actual animation state.

From there, it’s only a matter of making updates due to collisions. My collision algorithms are geometrically based, so they don’t yet function for curved movements (accelerations and further derivations of position), but I’ve plans for that update so hopefully I can get on it pretty soon. The circle-circle collisions, for example, assume each circle to be moving linearly.

Circle-Circle Collision Calculation

The circle-circle collision algorithm takes advantage of relative motion by combining the movement of each circle into a single vector and applying it to one of the circles (resulting in C-static and C-moving). The nearest point to C-static along the trajectory of C-moving is then found by calculating the intersection point of the C-moving trajectory and a line penetrating C-static and perpendicular to the C-moving trajectory. Let’s call that intersection point N.

Circle-Circle Collision Illustration and Physics Math

It is assumed that at the time of collision between these circles, their centers will be separated by a distance equal to the sum of their radii. That means that at the time of collision, a right triangle will exist with 2 vertices at the centers of each circle and 1 vertex at point N. The Pythagorean theorem is then used to calculate the position of C-moving at the time of collision by finding the length of the edge of the triangle opposite the vertex located at the center of C-static (the edge which lies along the C-moving trajectory). The resulting length is the distance between point N and the center of C-moving at the time of collision. That is subtracted from the distance between the center of C-moving at start and point N to give the distance between C-moving at start and C-moving at collision. Finally, that distance is divided by the length of the entire trajectory of C-moving (from start to end) and multiplied by the total change in time (from start to end). The result is the exact time of collision, which can then be applied to position equations to find the exact positions of C-static and C-moving at the time of collision. A vector with magnitude equal to the radius of either circle, and in the direction of the opposite circle, can be added to the center’s position to find the exact point at which collision will occur.

This is not just a “detected” collision, it is a calculated result that tells the exact time and place of the collision. Therefore, objects may be moving at any speed and the logic will still apply accurately (as opposed to frame-based or time-stepped logic which only functions accurately at very low speeds or very high framerates). It also saves time because after a collision is known, it never needs to be checked again so the engine doesn’t need to be vigilantly checking objects every frame. Instead, it jumps ahead into the future and continues calculations from there. The downside is that this kind of calculation sucks on your processing power so you need to find ways to stay accurate while only committing to the fewest calculations possible.

Impulses and New Equations

For every collision, an impulse must be calculated. That impulse leads to the formulation of a new equation that takes effect at the time of collision. The new equation is added to an array of equations with “start” and “end” values indicating when they accurately describe object movement and when their usefulness expires. Each array of equations is nested in an array with elements representing each individual object. When the playback time minus the “end” value of an equation is greater than the engine’s “memory” value, that equation is deleted. This only applies if the playback time is less than the most recent calculation time.

Matters of Optimization

As you can see, arrays are nested like crazy, which is not at all the most efficient way to handle things. I’ve been wanting to use something like a linked list, but arrays are a good temporary solution.

Calculations are capable of predicting collisions indefinitely, but there isn’t much point in having the engine predict events that won’t occur for an hour, so it is built to only go 15 seconds into the future before pausing. Then it continues calculations when the playback time is within 10 seconds of the last calculated event. If you pause the animation and push the scrubber far ahead of the calculation marker, you’ll see it kick into high gear to catch up. Like any arbitrarily selected value in the engine, these numbers can be easily modified.

When predictions are ahead of schedule, the engine will relax by stopping at partial cycles to allow the frame to pass. At the start of the next frame, the engine will continue where it left off. This helps prevent crashing and constant lag due to the engine voraciously seeking results that may never see the light of day anyway.

The engine is self-regulated. It keeps track of the average run-times of each portion of itself and later uses that data to determine whether or not it is necessary to interrupt a cycle for frame passage. If it expects the next segment of calculation to take too long, it ends the sequence, otherwise it continues.

The engine is also capable of running multiple cycles within a single frame (as in the first Liberty Engine Demo), but that function has been turned off for now.

More to Come

I’ll go into more on the math and methods later, but for now I have enough work to do that I shouldn’t be blabbing on. If there are formulas you’re looking for, don’t be afraid to ask. It’s a bit of a trick to find all the physics you need for this kind of thing. I was shocked to find out how rare it was for anyone to consider time-based physics instead of frame-based and that adds hours to your research.

I was happy to find this article from gamepoetry.com last week. That’s really the reason I felt compelled to post this update. Apparently Panayoti will be doing a much needed series on this topic.

Next time I’ll definitely incorporate some more interactivity so you can drop in some forces and objects. I’d also like to allow the engine to run backwards, calculating the past in addition to the future. With that capability, it wouldn’t be necessary to save as much equation data because it can easily be recalculated when necessary.

Too much to do, not enough time to do it.

-Christopher J. Rock

P.S. At 3491.9 (58 minutes, 11.9 seconds) an error occurs! This is due to simultaneous collisions. Simultaneous collisions are only accounted for in some circumstances right now. That’s one of the fixes I still have to make, but I think this shows how rarely it actually comes up. Thousands of collisions occur in that first hour before a single error rears its ugly head. Not bad.

I allowed it to calculate 10 hours of data without significant drop-framing. Unfortunately, there seems to be a bit of erroneous energy loss at an extremely gradual rate. After 10 hours, objects are moving much more slowly they they were at the start. That should not be occurring! . . . On the other hand, it’s not often that you run an engine for 10 hours anyway. . . .

UPDATE: I did the same 10 hour test with memory set to 60 seconds and there was no loss of energy! . . . Flash calculations are becoming less accurate due to all the equation data I was storing. . . . How strange. All the more reason to implement backsolving rather than saving all the information.

About the author:
Christopher J. Rock (http://)
Film student at California State, Long Beach. I want to make the gaming world a better place.
  • Pingback: blog.sokay.net » NorthStar: Intro to Pathfinding around Irregular Polygons()

  • Chris, that’s very cool bud. I must admit I am a tad jealous you’ve got the all that deterministic calculus working so well (even if not perfectly). You’re quite right — it’s not easy to find people who know about this sort of thing in the Flash community — gamedev.net, being mostly industry professionals working on “real” games, is very different in this sense.

    I may well return with questions for you! Thanks for sharing.

  • Thanks for saying so!
    My life in flash has been something of a hurricane since this first went up, including a complete transition to AS3, obsolescing any of this old code (except for some math that can thankfully be copied and pasted)! But on the bright side, this was my first time building a physics engine so I naturally learned a great deal in the process. And since then I’ve put some study into other techniques.

    Progress is spread over too many projects, but there will be another incarnation of Liberty Engine and it will be much more powerful and much better architected. This is the reason it’s been so long since I made a post on Sokay! I decided I wanted to put my money where my mouth was, so I’m focusing much more on work than talk. Still much to do. . . .

  • Oh, I know how you feel about spreading things too thin… 🙂

    *gets back to coding*

  • Chris,

    I’ve been doing some research on the matter of determinism in game (specifically re C++ and Flash), thought you might like to have a quick read and offer some feedback if you have any thoughts:

    http://www.visualharmonics.co.uk/actionscript-3/determinism-in-games-culling-the-myths/