Sunday, December 04, 2011

Rapid Physics Beta Release

Rapid Physics is a custom Physics Engine that I decided to build in Flash.

Why would I torture myself like that?

There are plenty of industrial-strength physics engines out there, such as Havok and Box2D. They offer complete and robust physics simulations, but they also hide a lot of information from the programmers that use them. This leads to two problems:
  1. Hard limits on authorship control over the physics simulation (lots of code you didn't write)
  2. A sense of helplessness when debugging engine-level problems (lots of code you didn't test)
Effectively, game programmers lose the granularity to control subtle features of the physics simulation, and the ability to do custom collision resolution for gameplay purposes. For games whose physics are integral to gameplay, there is still a place for custom physics implementations.

I designed Rapid Physics to tackle one specific problem that most general-purpose physics engines never attempt to address: Tunneling

In a physics simulation, physics objects actually teleport small distances each frame. The faster they move, the farther they teleport. Eventually, there comes a point where objects end up teleporting through other objects they should actually collide with. We call this problem Tunneling.

What Rapid Physics Does
Rapid Physics solves the tunneling problem for a fast-moving points that collide with Lines and Circles.

That's all?

For now, yes. The mathematical and algorithmic needs behind advanced collision detection are damned complicated. It turned out that perfecting such a simple task still takes hundreds of lines of code. Throw in some useful engine features, test code, and demos, and the codebase explodes to several thousand lines of code. That's a lot to do in a single semester!

Check out the Beta Release here:

How Rapid Physics Works
Rapid Physics is heavily inspired by the Flixel 2.5 framework. If you know how to use Flixel, you will know how to write in RapidPhysics. Here is a handy guide of some Flixel equivilents:
  • FlxGame - RapidSim
  • FlxG - RapidG
  • FlxU - RapidU
  • FlxState - RapidWorld
  • FlxBasic - RapidBasic
  • FlxObject - RapidObject
  • FlxGroup - RapidGroup
  • FlxText - RapidText
  • Input - (literally the same code, use RapidG.keys)
Flixel's Design overview applies equally well to RapidPhysics. The class where your game starts will extend RapidSim. The class where you write most of your physics code will be a class that extends RapidWorld. Exactly one RapidWorld exists at a time, and it's easy to switch between worlds with a call to host.switchWorld() (every RapidWorld has a host property).

Next, let's discuss some of the core components of Rapid Physics:

In Rapid Physics, Islands do all of the heavy lifting of the physics simulation. The idea is as follows:
  1. Add all of your RapidObjects to an Island
  2. Add your Island to the RapidWorld's IslandManager
  3. Enjoy sexy physics
The base class Island contains that core algorithm that solves collisions in Rapid Physics. Subclasses of island simply define what kinds of objects are collected together for collision solving. Currently, there are exactly 2 Islands in Rapid Physics:
  • PointLineIsland
  • PointCircleIsland
Let's take a look at PointLineIsland, for example:

package org.rapidphysics.islands
 import flash.geom.Point;
 import flash.utils.Dictionary;
 import org.rapidphysics.Collision;
 import org.rapidphysics.RapidU;
 import org.rapidphysics.Rlap;
 import org.rapidphysics.shapes.RapidLine;
 import org.rapidphysics.shapes.RapidPoint;

  * An Island that solves collisions between moving points and fixed lines. 
  * @author greglieberman
 public class PointLineIsland extends Island
  public var points:Vector.;
  public var lines:Vector.;
  public function PointLineIsland()
   points = new Vector.();
   lines = new Vector.();

   * This is an implementation of collectCollisions for points and lines
   * NOTE WELL: This implementation collides every point with every line, but it does NOT collide points with each other, or lines with each other 
   * @param frameTime
  protected override function collectCollisions(frameTime:Number):void
   var temp:Point = new Point();

   // test for collision between every point and every line
   for each(var rPoint:RapidPoint in points)
    for each(var line:RapidLine in lines)
     var result:Point = (Rlap.lineSegments(rPoint.position, rPoint.nextPosition, line.position, line.end, temp));
      // grab a collision object, and fill it with data from the intersection
      var c:Collision = recycleCollision();
      c.init(rPoint, line, Rlap.resolveMovingPointAndFixedLine); // obj1, obj2, how to resolve the collision
      c.pointOfCollision.x = result.x;
      c.pointOfCollision.y = result.y;
      c.time = frameTime + RapidU.timeOfCollision(rPoint.position, rPoint.nextPosition, result); // define time for priority in solving collisions


At it's core, it's just two Vectors, and 2 nested for loops. Not too bad right?

It should be extremely easy to write new Island subclasses with the existing intersection tests, should you have more custom collision needs. The tough part is writing brand new intersection tests. I could spend another semester just working on those...

The Core Collision Algorithm
The core collision-solving algorithm is perfect, but extremely expensive. Here's what it does:

Every Island, every frame:
  1. Test for collisions
  2. Sort collisions by time
  3. Resolve collisions in time order
    1. Every time Step 3 occurs, throw out all collision information, and return to Step 1.
This is insane, but necessary. When a collision is solved, it changes the state of the system, so every object that is being tested for collision needs to be evaluated again. In the worst case (which never happens), you are looking at a runtime of O(n!). The only way to avoid this is to cheat the physics in some way. Thankfully, in general, you are looking at an average runtime of O(n^3). This can be even faster if the collision test code runs better than O(n^2).

Intersection Tests
I designed Rapid Physics in parallel with a game that I am building. I wanted to utilize parts of Rapid Physics immediately during development, so there are 2 components to the engine that are extremely easy to integrate into to other games: Rlap and RapidU.
  • Rlap contains the hardcore Intersection Tests, and also Collision Resolution functions
  • RapidU contains low-level utility functions, like clamp, vector reflection, dot product, etc.
Intersection tests are some of the hardest parts of physics programming. I hope they serve you well.

For project setup, I strongly recommend importing RapidPhysics into a Flash Builder project. For this, Flixel has a nice setup guide.

Download the source files on GitHub:

Unlike Flixel, RapidPhysics is not a complete game engine. You will probably be better off exploring and modifying the five project demos instead of building something from scratch.

You can find the code documentation in the GitHub repository, but for convenience, you can also find it here:

That's a wrap for this Beta Release. Maybe I'll add more to this project in the future.


No comments: