Jump to content

  • Log In with Google      Sign In   
  • Create Account

2D Physics Engine


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
31 replies to this topic

#1 extralongpants   GDNet+   -  Reputation: 704

Like
0Likes
Like

Posted 21 June 2007 - 01:26 PM

I'm looking for a free (preferably open-source) C/C++ library for simulation of rigid body physics in 2D. I've done a lot of google-ing, and it seems that there aren't any mature, reliable, maintained C/C++ 2d physics libraries (though I'd love to be proven wrong). I came across this thread, but a lot of the recommendations in it are now non-existent or don't meet all of my needs. The two choices that stand out are ODE, with object positions constrained to a single plane, or the Chipmunk Game Dynamics library. My main concern regarding ODE is, naturally, the fact that it was designed for 3D physics simulation. My game is going to have lots of physically enabled objects, and I'm concerned that the extra, useless dimension is going to result in lots of overhead, in both memory and computation. Another concern I have for ODE is 2D polygons - how should I represent them, if at all? Constructing 3D polygonal volumes for this purpose seems like it would very wasteful, not to mention overly difficult. Chipmunk seems to be a pretty nice library, but I have some concerns:
  • It's not quite finished, and I don't know if it's still maintained
  • The documentation available is not nearly as complete or as easy to follow as it is in other libraries (notably ODE).
  • I'm not sure if it will assist me in managing objects that shouldn't always act like rigid bodies (such as the player), for which I should just need basic intersection prevention. ODE seems to be well equipped for this (with its separation of collision detection and collision response), but it's not clear to me from Chipmunk's documentation whether or not this is well handled. Right now I'm leaning toward ODE. Do any of you know of any good 2d physics libraries? Do you have any recommendations given the choices available? I really want to avoid rolling my own physics/collision detection library, so any advice would be greatly appreciated.

  • Sponsor:

    #2 Aressera   Members   -  Reputation: 1485

    Like
    0Likes
    Like

    Posted 21 June 2007 - 04:26 PM

    Chipmunk is nice from what i've seen, but as you pointed out, it's not quite finished. But, it is however still under active development I believe. I think its main limitation is that it doesn't support user controlled "kinematic" objects, though static objects can be acheived by setting mass to be infinite.

    Other than that, i'm not sure, thought I can say that Chipmunk will be at least twice as fast as ODE because its collision detection is much simpler and tailored for 2D objects.

    If you want the missing features, i'm sure you could implement them without much effort. All it takes is adding a couple of functions to the cpBody source file to set the position, as well as a flag denoting a body as kinematic, and then modifying collision detection slightly to filter out pairs of kinematically controlled objects (your player for instance). Basically if two objects are both controlled kinematically, no collision detection should be performed. Otherwise, if one object is dynamically controlled and the other kinematically, then during restitution only the dynamic object will be altered. One can do this by setting the mass of all kinematic objects to be infinite, or setting their inverse masses to be zero.

    hope this helps.

    #3 extralongpants   GDNet+   -  Reputation: 704

    Like
    0Likes
    Like

    Posted 21 June 2007 - 04:46 PM

    Good idea. One thing I forgot to mention, however, is that Chipmunk's source code has very few comments in it, so it may be difficult for me to find out where to put my alterations. I'm also not very knowledgeable in the areas of mathematics and physics. Nevertheless, that's probably my best option so far.

    On another note, I realized earlier today that I'll probably need support for line segments as collision barriers to simulate terrain-like surfaces, which makes using ODE less desirable (and Chipmunk more desirable).



    #4 raigan   Members   -  Reputation: 744

    Like
    0Likes
    Like

    Posted 21 June 2007 - 05:00 PM

    There are several 2D-physics projects based on Erin Catto's Box2D simulator: http://gphysics.com/

    The Box2D source is so clean and simple that you might want to just roll your own engine from that -- all you need is broadphase collision and support for arbitrary polygons.

    There are several ports of Box2D to other languages, that should be a good place to start -- this one has a lot of extra functionality, you could simply port the stuff that was added back to c++: http://www.cokeandcode.com/phys2d/

    raigan

    #5 extralongpants   GDNet+   -  Reputation: 704

    Like
    0Likes
    Like

    Posted 21 June 2007 - 05:17 PM

    I took a look at the box2D stuff earlier, but it just isn't feature complete enough for me. It would consume too much of my time to try and add the features I need. It is a great resource though. Thanks for the suggestion.

    #6 skorche   Members   -  Reputation: 136

    Like
    0Likes
    Like

    Posted 21 June 2007 - 06:13 PM

    Wow, I'm surprised you guys have heard of Chipmunk. Has anyone actually used/dabbled with it? I've been somewhat cautious about getting too well known yet. (largely because of the poor documentation at the source level) I actually registered for an account a couple of months ago to evangelize, but then never did.

    To answer some of your questions:
    1) Yes it's maintained. Development has slowed now (too much competition for my free time at the moment), but I'll be happy to fix bugs. I should start scheduling time for all my personal projects. ;)
    2) I know the documentation is somewhat lacking (again, particularly at the source level). Considering that you're the second person that's emailed me this week about Chipmunk, I should probably make the docs a priority. If you do end up using Chipmunk, and would like to help... it would be... helpful...

    You're last question is a bit more complicated. It depends on what you want to do, but you can probably have both good rigid body behavior and a large degree of control.
    1) Do surface velocities help? They were added with sidescrollers in mind.
    2) Setting the positions explicitly will work, but will result in rather poor looking physics. A better solution would be to modify the velocity of the object to slew it to the desired position in the next timestep.
    3) For things like moving platforms or elevators, give them an infinite mass and slew them into position using their velocity. (Just make sure they don't trigger collisions with other infinite mass objects!)
    4) If you still really don't want the objects to act like rigid bodies, it wouldn't be hard to query for collisions using a cpShape and cpBody that aren't added to the cpSpace. You would have to do all the collision response on your own, which wouldn't be easy without the impulse solver to help you.

    There was mention of Erin Catto's Box2D. Chipmunk is actually using his impulse solving technique. On top of that I've implemented several collision primitives for the narrow phase, and a spatial hash for the broad phase. I'm actually listed on his page.

    Oh, and one last thing. Someone did manage to get it to build under MSVC. I could probably get a binary of the library if anyone wants. It sounds like a cleaner solution would be to use MinGW, as that has better support for C99. Help on this front would be appreciated as I have no Windows machines.

    #7 skorche   Members   -  Reputation: 136

    Like
    0Likes
    Like

    Posted 21 June 2007 - 06:34 PM

    Quote:
    Original post by Aressera
    Other than that, i'm not sure, thought I can say that Chipmunk will be at least twice as fast as ODE because its collision detection is much simpler and tailored for 2D objects.


    Don't quote me on it, but I would guess that Chipmunk's impulse solver (the most expensive part of the simulation) is faster that ODE's by a large amount, thanks largely to Erin Catto's contact persistence idea. I don't have sleeping for inactive bodies implemented however. I have no hard performance facts, so this is all purely speculation.

    The real benefit (and the reason I wrote Chipmunk) is that using ODE or Newton for 2D physics is obnoxious. I started down that road and thought there had to be a better way. When I saw that there really wasn't, I started Chipmunk's (terribly crappy) predecessor.

    [Edited by - skorche on June 22, 2007 1:34:15 AM]

    #8 extralongpants   GDNet+   -  Reputation: 704

    Like
    0Likes
    Like

    Posted 21 June 2007 - 06:54 PM

    Awesome, thanks for the reply. It looks like your library may be the best solution for me. Since you've done a proof-of-concept platformer successfully, I imagine using your library for the same purpose can't be too hard [smile].

    I'll be using Visual Studio for development of the game, so if I can get it compiling, I'll send you the info and or project files.

    I may be able to help a little with documentation (no guarantee); I'll be gathering information as I attempt to integrate the library with the rest of my code base, and I can use that information for writing up some documentation.

    Thanks for taking the time to reply here. I appreciate your help.

    #9 pTymN   Members   -  Reputation: 464

    Like
    0Likes
    Like

    Posted 22 June 2007 - 09:20 AM

    Hello, I posted this a few weeks ago on the bullet forums on the thread about Chipmunk's release:

    I have a 2D collision detection engine that performs fully swept collisions, modelling the swept movements as 4th order polynomials to find the root of. However, it absolutely cannot handle interpenetration. Does your physical solver resolve collisions in such a way that interpenetration is guaranteed not to ever occur?

    [edit]
    The collision detection makes the assumption that objects move from non-penetrating positions to new non-penetrating positions. If I were to adapt your physical solver code to my collision engine, does it already or could it easily be instrumented to not stop converging until the relative velocities of any contact point is zero or positive and not negative.

    [Edited by - pTymN on June 22, 2007 3:20:42 PM]

    #10 skorche   Members   -  Reputation: 136

    Like
    0Likes
    Like

    Posted 22 June 2007 - 12:01 PM

    Oh, I haven't looked on that forum for quite a while now. Sorry about that.

    To answer your question, interpenetration is fixed iteratively after the collision occurs. However, given that you can do swept collisions, you could just look a frame ahead right? Catch the collision on the frame before instead of after. This won't necessarily guarantee non-interpenetration though unless you use a *lot* of solver iterations.

    What kind of primitives do you support? Is your code open-sourced? Supporting swept collisions would be awfully nice.

    #11 pTymN   Members   -  Reputation: 464

    Like
    0Likes
    Like

    Posted 25 June 2007 - 04:22 AM

    Quote:

    To answer your question, interpenetration is fixed iteratively after the collision occurs. However, given that you can do swept collisions, you could just look a frame ahead right? Catch the collision on the frame before instead of after. This won't necessarily guarantee non-interpenetration though unless you use a *lot* of solver iterations.


    The algorithm is:

    1) Calculate desired new manifold positions (translation/rotation/animation).
    2) Search for collisions between new manifolds.
    3) When a collision is found between two objects, scale back their motions by the amount prescribed by the collision test. This algorithm assumes that all object motion is first order. This assumption works surprisingly well.
    4) When all objects' new manifolds have valid motions that don't cause penetrations to occur at any time during the frame interval, then perform a quick static pass to find where objects are "touching", and record world space contact points and normals.
    5) Ask objects to perform non-linear updates, including change of velocity and angular velocity.

    The dynamic collision tests are no longer analytical geometry based tests, but instead 4th order or 2nd order polynomial equations that describe the motions of two object's boundary pieces over the span of a frame. This means that if two boundary pieces start a frame already penetrating, the collision test will fail to recognize a collision. In a sense, the question that the collision tests answer is,

    If it happens at all, when is the distance between these two pieces equal to HALF_EPSILON? (For 0<= x <= EPSILON, x is the distance apart that two objects are in order to be considered touching. This turns out to be wonderful for cases where you want to handle sliding and rolling objects.)

    Quote:

    What kind of primitives do you support?


    Here's an old screenshot that will pretty much give you the gist of what primitives my engine supports



    There is no concavity limitation, and the manifolds can perform any arbitrary transformation over the span of a frame. The circles can be of radius 0, and part of one the the bugs that I'm fixing, the circles will instead be treated as arcs, including inside facing arcs. I can keep a steady 100fps with ~200 simple objects.

    Quote:

    Is your code open-sourced? Supporting swept collisions would be awfully nice.


    Not yet, but supporting realistic looking physical response would be awfully nice. Please contact me via one of the methods listed in my profile, IM preferred, since we can carry on rapid dialog and quickly reach a useful agreement. Collision detection without physics is not particularly exciting... I'm willing to open source the collision detection engine, if you can do two things for me:

    1) We come up with a plan to quickly integrate the two useful parts of the software, my collision detection and your physics (which is awesome btw).
    2) You help me get the old and new Chipmunk versions working on Microsoft Visual Studio 2003/2005, because it is choking on some of the straight C. This isn't really a fault of yours, but it sure limits Chipmunk's usability.

    #12 D_Linden   Members   -  Reputation: 122

    Like
    0Likes
    Like

    Posted 20 July 2007 - 02:11 AM

    I hope you don't mind if I add some more questions to this thread.

    I'm writing a server for a online-game, and now I have to do some collision detection between some simple 2D shapes (circles, rectangles, cones and maybe some line intersection). I found chipmunk some days ago and it seems really nice, but now I wonder:

    1. Should I use chipmunk just for the collision detection or should I roll something on my own?
    2. (Assuming I should use chipmunk) How do I get it to compile under visual studio 2005? I have set it to compile as C-code but still it gives me 857 errors when I compile.

    Thanks in advance
    Daniel

    #13 pTymN   Members   -  Reputation: 464

    Like
    0Likes
    Like

    Posted 20 July 2007 - 05:06 AM

    VC71 compatible source and project

    #14 D_Linden   Members   -  Reputation: 122

    Like
    0Likes
    Like

    Posted 20 July 2007 - 08:17 AM

    Quote:
    Original post by pTymN
    VC71 compatible source and project


    Thanks a lot!
    After spending some hours trying it out, I must say its very very cool. But I think it will be better if I use my own collision detection, this seems a bit to complicated for the purposes I'm looking for.

    #15 Emil_Halim   Members   -  Reputation: 122

    Like
    0Likes
    Like

    Posted 21 July 2007 - 05:21 AM


    Wow , It is very cool stuff. thank you skorche for that wonderful work.

    Does it have a Line intersect with poly function ? , this intersct function is realy very uesful , for example you can allow the enamy to see you and take some action.

    also i want to ask is it currently under havy devolping or not?

    #16 pTymN   Members   -  Reputation: 464

    Like
    0Likes
    Like

    Posted 24 July 2007 - 03:36 AM

    It is under active development and has intersection methods between any two types of cpShapes.

    #17 Emil_Halim   Members   -  Reputation: 122

    Like
    0Likes
    Like

    Posted 24 July 2007 - 07:32 PM


    Thanks pTymN , 2 days ago i emailed Scott Lembcke the ownner of the library ,and he said It is under active development but according to his needs of new features to create his game.

    I have tried to replace the allocation c functions with the new keyword and using dynamic array instead of reallocating c function , but it did not wrorked.

    so is there any one triead that and did it ?

    #18 Lightstrike   Members   -  Reputation: 172

    Like
    0Likes
    Like

    Posted 25 July 2007 - 04:21 AM

    I've been looking for a decent aimed-at-2d physics library for years now. Chipmunk seems to have come the furthest. I'm very impressed by the stability and behaviour of the demos. It was too bad there are no swept collisions yet but it would be awesome if you two could help each other out. The library would feel very complete for a wide range of applications then.

    Great work and keep it coming! I'll try the visual studio project too and play around with it. I got a pretty playable game with a pretty bad physics engine I can try it on. Would be cool to change it to chipmunk and see how it works. I am a bit worried about not having swept collision handling though since its a fast ball game.

    #19 Lightstrike   Members   -  Reputation: 172

    Like
    0Likes
    Like

    Posted 25 July 2007 - 05:14 AM

    I compiled the vc71 project with vs2005 but the constant M_PI was missing causing the only error. Is something missing?

    #20 pTymN   Members   -  Reputation: 464

    Like
    0Likes
    Like

    Posted 25 July 2007 - 07:02 AM

    Oh snap. Go to your project properties and add _USE_MATH_DEFINES in your preprocessor definitions.




    Old topic!
    Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



    PARTNERS