Motor Physics released

100 stacking boxes at 60Hz with 30 iterations

More examples:

200 stacked boxes
polygon soup
compound shapes

So here it is – due to lack of free time I have not managed to include all planned features, but I’m working hard to include those in the next update. For now I have removed many things and tried to clean up the source a little bit. Still some parts are very messy but will be fixed in the next days, so this is more a preview than a fully functional version. I also need to setup a SVN repository, write a TODO list etc. Currently you can get the source for the preview here. The engine’s name was changed to Motor2.

The new core was written according to Erin Catto’s brilliant Box2D source. Besides many things, it features a contact graph, compound objects, a working sleeping system, restitution.., all things which I have tried to implement but the Box2D version is better and it actually works :) I recommend everyone interested in learning how to write a physics engine to look at the source.

Performance

The biggest performance gains come from efficient high-level algorithms. Most algorithms in Motor run in O(n log(n)) to O(n) in the average case, and O(n^2) in the worst case only. It’s also very important that these algorithms have an efficient low-level implementation. For Flash, this means in most situations: the fewer instructions used, the faster the code executes. This is different for the Box2D C++ version. Here memory optimizations and cache-wise design are much more important. Following are my developing guidelines:

  • precompute as much as possible
  • avoid frequent object creation/deconstruction, instead create objects once and reuse them
  • constrain function calls, inline critical parts
  • inline vector and matrix math
  • use linked lists for data structures that are constantly under modification
  • limit array access (especially nested arrays)
  • accept code duplication instead of trying to encapsulate everything
  • avoid using flash’s build in methods, e.g. the Math class
  • prefer ‘extend and override’ instead of defining interfaces (template pattern)
  • don’t cast objects often

A special word about how to deal with vector and matrix math. I haven’t defined methods for vector operations at all. I have seen many vector classes, packed with dozens of methods for performing additions, multiplications etc. This makes your code incredible slow and ugly to read, resulting in spaghetti code when concatenating many operations. Without the possibility to inline functions and overload operators I recommend to just stick with writing the expressions component-wise. (an alternative would be to use a preprocessor, which I left out to make the code more accessible)

Collisions

Because the most time in a physics simulation is spend on detecting and resolving collisions, I tried to make them as efficient as possible. I have not ported Box2D’s collision code, instead I further enhanced my existing SAT collisions. Computing the support vertex of a polygon along a given direction (aka the separation axis) is now accelerated by a BSP tree-based structure for performing extremal queries on a convex polygon [1], a O(n log(n)) search. Compared to my previous brute-force method this is about 4-6x faster. Another very important change was to include separation axis hints in a contact object – if a separation axis was found, I start the search in the next time step with the previously found axis. So when for example the AABBs of two shapes are touching, but the shapes themselves do not, you get an almost instant collision resolving.
The overall result is that it’s now 40-70% faster than my latest ‘polygon soup‘ demo. This makes it possible to simulate more than 100 stacked boxes at +60fps on a decent machine.

Broad-Phase

Motor uses a quad tree as the default broad phase, based on articles in [2] and [3]. It copes very well with varying object sizes and scene dimensions so it should be fine for a wide range of applications. Erin’s Box2D uses Sweep&Prune, which is a very attractive solution making best use of spatial and temporal coherence. The implementation looks very impressive and complex – but since I don’t want to include something I don’t fully understand I started to write a pure linked Sweep&Prune detector on my own.

Creating Shapes

motor structure shape creation

I’ve adopted Box2D’s structure for creating bodies and shapes:
A ShapeData instance defines the geometry of the shape and is responsible for computing mass, moment of inertia and the centroid. A RigidBodyData objects contains a list of ShapeData objects and in addition defines the initial state (position, velocity) of the rigid body. The RigidBodyData object is then passed to a RigidBody object, which finally creates all collision shapes from this data.

Vector representation

Polygons are stored in a data structure I call a vector chain, which is nothing more than a doubly linked circular list of 2d vectors. In addition, each vector also stores its position index and a flag indicating if it’s the last vertex in the list. So it’s something between an array and a linked list. I created this format to handle wraparounds in both directions easily and fast. You could also create an arrayed doubly linked list lookup table of vertex indices like this:

var prev:Array = [];
var next:Array = [];
for (var i:int = 0; i < k; i++)
{
	prev[i] = i - 1;
	next[i] = i + 1;
}
prev[0] = k - 1;
next[n - 1] = 0;

Retrieving the next/prev vector in the circular list can be then done this way:

//next vertex in list
v = vertexList[next[i]];
v = vertexList[prev[i]];

But nothing is simpler and faster than:

v = v.next;
v = v.prev;

Also, since everyone tends to use either plain arrays, their own custom vector classes, or the build in point class I tried to stick with plain x and y properties.

Rendering

There are two different ways to show your objects on the screen. The first and most straight-forward way is to draw all objects in world-space coordinates into one DisplayObject (you have to invoke the toWorldSpace() method on each ShapeSkeleton instance to force a WCS transform before doing so). The alternative is to draw the shape’s modeling-space outline into individual DisplayObject instances and then just update their position and rotation to get in sync with the rigid bodies. This is faster and usually the best way to draw anything else besides plain vector graphics.

The package includes a simple renderer to demonstrate how it’s done, but since rendering is not handled by the physics engine you have to write something of your own.

Coordinate spaces

Collisions are all processed in the WCS (World Coordinate System). Normally you do this by transforming object B into the local space of object A, but in the 2D case it’s easier and faster to just transform every polygon into world space and process collisions there. To avoid unnecessary transformations, they are only computed if a client requests them for rendering or the collisions need them. For example, Box-Box collisions don’t need vertices, but the Polygon-Box detector does generate vertices for both shapes.

Works cited

[1] Eberly, David in Game Physics, Morgan Kaufmann Publishers, 2004
[2] Game Programming Gems, Multi-Resolution Maps for Interaction Detection
[3] Game Programming Gems II, Direct Access Quadtree Lookup

86 Comments

  1. Ryan Miller

    So what would be the advantage of Motor Physics over the AS3 port of Box2D?

  2. Ryan Miller

    i forgot to add..

    Great job! the performance looks fantastic ;-)

  3. This is great news! Thanks heaps for all your work on this project.

    All it needs is some documentation, and you’ve got yourself the best Flash physics engine to date.

    All the best for the new year. :)

  4. Great news! Excellently fast demo and in the end it will come down to performance. Porting box2d and writing specifically for AS3 gives two nice iterations to observe. I think the AS3 style smaller compact kit would be a better fit for the flash world. Looking forward to getting into this. Thanks!

  5. Great! This is the best present for the new year!

  6. Great, can’t wait to try it!

  7. You are awesome, my friend. I was crossing my fingers, hoping you would meet your release date. Opened it up this morning on a whim and here it is! Congratulations on the release.

  8. Besides the Papervision3d releases, this is probably the most anticipated release for the Flash community. Once documentation is made available, it’s definitely going to improve the quality of future Flash games!

    Oh, and I like how you released it at the latest possible moment :D Great work!

  9. thx dude :)

  10. Congratulations! Nice timing on the post too :)
    Eagerly downloading now.

  11. thx!+happy new year! ;D

  12. When I try to compile the example, I can’t find the source for ArrayedQueue object, do I miss something?

  13. Sorry, I just saw it was in the data structure package, but now, I can’t find the de.polygonal.math2.utils.MinimumAreaRectangle :)

  14. Good job mate! Huge respects!

  15. @Ryan Miller the biggest difference should be performance. I haven’t compared it to AS3 port of Box2D, because i would need to include the incremental Sweep&Prune from Box2D. But it should be faster.

    @JP you don’t need the MinimumAreaRectangle class, just comment it out. as said in the post, it’s messy. I’m currently preparing the code to be put into SVN this evening.

  16. Ryan Miller

    better performance? that’s great!

    How about features from the upcoming 2.0 release of Box2D like CCD, sensors and raycasting?

  17. motor2 is now hosted at google code, see http://lab.polygonal.de/motor_physics/. You can check out the latest revision from the SVN repository. It should now compile fine without complains about missing classes. But you need to download my data structures package and add the source to your classpath.

    I was also wondering why the polygon soup demo is so slow and discovered that I forgot to remove some debugging code from the class that handles polygon collisions. fixed in SVN and now runs fine.

  18. Thanks Michael, I was about to ask about collisions between circles and polygons and I’ve just seen in the SVN it’s not yet handled :)

    One question about the algorythm. Let’s say that for an experiment, I have a group of 50 boxes quite far from another group of 50 boxes. And let’s say that for another experiment, I have a group of 100 boxes in the same area (closed from each others). Does the collision algorytm makes a difference between the 2 experiments (normally the first experiment could be computed faster)?

  19. Mickael, I’m afraid there are still problems with the example and the svn sources.

    For example in PolyRenderer.as in your example, the line “var v:V2C = _shape.worldVertexChain;”
    I hav an error :

    1118: Implicit coercion of a value with static type de.polygonal.motor2.math:V2 to a possibly unrelated type de.polygonal.motor2.math:V2C.

  20. Sorry to spam the blog. I’ve resolved the pb by changing all V2C objects (in the example we can download on this post) by V2 objects and by changing .eol by .last .

    But now I come into a harder problems, the example compiles and runs, the objects are drawn, but no collision is detected.

  21. Are there realy no joints in you engine?
    I hope you plan to implement them.

  22. @JP

    about the experiments: this is handled in two steps. first the shape proxies are checked by the broad-phase (in my case the quad-tree). this is used to quickly determine ‘false-positives’ (objects that seem to intersect but don’t have to). if the proxies intersect a contact pair is created and send to the narrow-phase for further analysis. so experiment 1 + 2 should make no difference. although the quad-tree works best when objects are distributed over the game world and not clumped.

    about the svn-problems: the source is currently heavily modified – I’ll fix this ASAP.

    @Leszek
    I’ll port the Box2D joints.

  23. That’s great, because motor2 classes look much much better than those in box2dflash.
    great Job till now!!! thanks:)

  24. Thanks Mickael, I’ve read an article where yuo explain how to create dynamic groups. I thought you were using this to cluster objects in different areas. Then until the groups collide, you dond’t have to test the collision between an object from 2 separate groups.

    For the SVN, I think it would be a good idea to upload the examples too, because the .zip in your post seems to be old now.

  25. Very interesting work. I you want to get additional performances, you might want to try haXe. The compiler produces very optimized Flash9 bytecode and the next 1.17 version will add “inline” keyword for methods and static variables, so code can be automatically inlined at compilation time.

  26. Nicolas, sounds great. Just downloaded haXe to give it a try :)

  27. I spent 2 hours trying to make the example work with the current SVN, and I failed :) Collisions are still not detected, please help, don’t swap to haXe for now :)

  28. JP, sorry for the trouble, I forgot to make a working snapshot before messing around with the svn. at least the collisions should work now.

  29. Thx Mickael! There is a compilation pb. I think you’ve forgot to add math.AABB2 in the SVN. It’s needed in the World.as class.

  30. Hey Michael,

    Congrats on the release!
    The demos are very impressive, excellent work.

    All the best,
    -Matt

  31. Hristo Dachev

    Thanks for the release and the efforts behind it!
    It would be great if you could build a demo in which the user is able to apply force on individual bodies via the mouse. I think it would be very informative.
    Happy new year mate!

  32. Nice. The collision code & contact point code is very impressive. I’ve been working on a port of Chipmunk, also uses the Box2D persistent contacts (see link).

    Have you done any side by side comparisons of broad phase? I’m currently working on the Spatial Hash used by Chipmunk – it would be interesting to compare it to pune&sweep and quad trees in the same engine.

  33. Hi,
    how can i fix, and move manualy, just one point of a polygone?

    thx for this engine, i think it’s very great.

  34. not yet possible, need to finish implementing joints/forces, see http://code.google.com/p/motor2/issues/list

  35. Hi mickaels, still me, and still not manage to compile with version 11 of svn :) .

    1046: Type was not found or was not a compile-time constant: BufferedPair.

    Good luck mickael, I see many classes in forces and joints, seems it’s not far fro being implemented. I would love to see examples in your svn and I saw there is a directory “examples” now, which is very hopefull :)

    Good luck!

  36. All your examples look neat until you realize they are all broken. The objects penetrate eachother on collision. This should not be allowed…!

  37. I think broken is a bit of an overstatement. a bit of Intra penetration always seems to be a problem with SI.

  38. interpenetration is actually *required* for computing contact ids and enhancing the solver with warm-starting. (applying impulses from previous timestep)

  39. Do you plan to make a new release soon ?

  40. I’m working on it..

  41. Hey, i was just wondering if it’s possible to have ball line collisions in this engine yet, or if it’s something that WILL be possible in the future.

    We just finished developing line golfer and we went with APE (at the time motor physics wasn’t even an option anyway) so i’m just curious.

  42. this is the feature request list, see http://code.google.com/p/motor2/issues/

  43. I’m very impressed with the tech demos, and I can’t wait to start playing with this engine!

    I was able to run SVN checkout to get the source, but I can’t find any documentation or example source. There is an examples directory, but it’s empty. How am I supposed to know how to use it?

  44. hi, the svn is currently out of sync and i’m working hard to provide the next big update soon. for now you can only look inside the preview zip how the demos are done (http://lab.polygonal.de/files/motor2/motor2_preview.zip)

  45. There are some errors on the svn.. V2C can’t extend V2.
    With the motor2_preview.zip, where can i find “MinimumAreaRectangle.as” on the package “utils” in “math2″ file ?

    THX guys !

  46. I’m having problems getting polygon-type objects to work.

    If I create rectangles using BoxData, they seem to work just fine:
    var sd:BoxData = new BoxData(density, w, h);

    But, if I substitute PolyData for BoxData:
    var sd:PolyData = new PolyData(density, [-w/2, -h/2, w/2, -h/2, w/2, h/2, -w/2, h/2]);

    …then the objects don’t seem to collide at all. They’re displayed, and gravity affects them, but they just fall right through the ground and each other.

    I’ve seen poly objects working in your demos.. what am I missing?

  47. this is a bug, i’m fixing this right now and will provide an update this week.

  48. Hi,

    We are currently developing a little flash game at the university and we have decided to use Motor2 as physic engine. It works great for our intention but there is a little problem. It would be great if you could answer this question to us.

    We need different friction on surfaces, but if i set the friction property of f.e. BoxData it seems that it has no effect on surface friction. I have also seen two properties called angDamping and linDamping of the RigidBody clas which exactly do what it implemented for i think, but if i adjust one of this properties, the whole movement of an object is “damped”.

    Our intention now, is to combine the hitTest with the linDamping property for simulating some kind of surface friction. If it’s possible, could you give us answer if this is the right direction?

    thanks in advance,

    Hannes & the Team

  49. hi hannes, this is definitely a bug. I’ll fix this asap.

  50. Ok, i thought this is maybe a not implemented feature, but if it’s a bug that will be fixed, it will made life much easier ;)

    We produce a game that heavily use physic. There are some tests with Motor2 now and i realized their could be problems, f.e. if you want to play sound-fx on hit (faked fx-sound for sure), you have to write your own routines, or?

    I believe that dispatching or so is too slow. I do not know if you have any time for discussing this kind of features via mail, but i will go on posting infos/bugs/feature requests here, if there is a demand. I think that Motor2 could be a very great engine for games, because it is more advanced than APE by design and much better written than the Box2D port.

    thank you for your work

  51. hi hannes, friction is fixed. this was also the reason for many other bugs, now the stability is much better :). you can subscribe to the motor2 mailing list:
    http://groups.google.com/group/motor2

  52. That looks great. But I can’t figure out how to use it in Flash CS3. I tried putting the swc file in ConfigurationActionScript 3.0Classes and ConfigurationComponents but no effect. How do I import it?

  53. The swc file was compiled with the FlexSDK and doesn’t work with CS3 because it’s a pure class library. in CS3 you have to compile against the source classes, so you need to add them to the classpath.

  54. Thanks, that works. But how do I enable code completion for motor2? I haven’t worked with motor2 before and I can’t find any documentation for it.

    Thank you

  55. there isn’t much documentation yet, but the api is very similar to Box2D. It’s not possible to get code completion for custom classes in CS3, so you should rather use another editor like FlashDevelop (www.flashdevelop.org).

  56. Hi, I’m looking again to use motors2 for a game.

    i saw that you reently added line collisions, I have a question about it. does it work for elastic lines ? I mean, is it possible to manage collisions between an elastic string and other objects (circles, polys etc…) ?

  57. no, elastic shapes are not supported yet.

  58. Hi Michael.
    Great engine and amazing blog posts. Love the data structure ones.
    I’m just wandering. You said “prefer ‘extend and override’ instead of defining interfaces (template pattern)”. Are interfaces slower?
    Thanks in advance.

  59. what I meant to say: interfaces force you make function calls, which is the slow part. The alternative is to define a basic class with public fields and extend them with inheritance.

  60. What’s mean 30 iteration? Is it number of SI Solver iterations per step?

  61. Hello!
    First of all thanks for the great engine. Looks like it’s the fastest one.
    Hope you can help me with a simple problem.
    I need to add a mouse joint to the object under cursor on MouseEvent.MOUSE_DOWN.
    Is there any way I can test an object contains some point?

  62. there are plenty of examples in the source package. for example testbed.joints.TestMouseJoint

    please use http://groups.google.com/group/motor2 for further questions.

  63. Of course I have looked through all examples but there is no solution.
    My question is on the group list already so meet you there.

Trackbacks/Pingbacks

  1. […] bookmarks tagged fixed Motor Physics released saved by 22 others     floz87 bookmarked on 12/31/07 | […]

  2. TastyLamp says:

    Motor Physics!…

    Good news, everyone! Michael Baczynski from polygonal labs has released the first iteration of Motor Physics (now named Motor2) in time for the new year.
    It’s an ActionScript 3 physics engine, that boasts polygon vs. polygon collisions and super-…

  3. […] AS3 2D Physics Engine Motor Physics Released December 31, 2007 — drawk Great news! Polygonal Labs has released the long awaited Motor Physics engine. […]

  4. […] to the list of free Flash physics engines is Motor Physics. It’s based Box2D (an open-source 2d physics engine written in C++), and so shares some of […]

  5. polygonal labs » Motor Physics released…

    polygonal labs » Motor Physics released…

  6. […] his highly awaited physic engine for flash. It goes by name Motor2. Check out the releasepost here. It’s very straight forward and with help of example I managed to pull something to getter […]

  7. […] Labs has finally released a brilliant Physics Engine – now called Motor2. Be sure to check the examples ( 200 stacked boxes, polygon soup, compound […]

  8. […] Motor 2: Net zoals Box2DFlashAS3 is Motor2 gebaseerd op de Box2D C++ engine. Verder is er nog niet zoveel bekend over deze engine. Uit demo’s blijkt dat de performance voorlopig nog niet kan tippen aan die van Box2DFlashAS3 […]

  9. […] first motor phyics trial – called gooey slime. To my liking, it´s so easy, comfortable and fast to work with […]

  10. […] źródÅ‚a do pobrania […]

  11. […] Polygonal Labs a mis à jour son composant proposant un Moteur Physique pour ActionScript3. Il est maintenant nommé Motor2. […]

  12. […] are an evolution of my gooey slime snippet wich I released a couple of days ago. Still merged with polygonal´s great motor2 physics engine I now enhanced the physiognomy and color-management of each slime […]

  13. […] (0.1) of “Slime Saver v0.1“, a slimy kind of screensaver ( physics still based on motor2 […]

  14. […] motor: lab.polygonal.de/2007/12/31/motor-physics-released/ […]

  15. […] Bullet, PhysX, Farseer, Box2D, Motor, […]

Get Adobe Flash player