Chipmunk Game Dynamics

Introduction

First of all, Chipmunk is a 2D rigid body physics library distributed under the MIT license. Though not yet complete, it is intended to be fast, numerically stable, and easy to use.

It’s been a long time in coming, but I’ve finally made a stable and usable physics implementation. While not feature complete yet, it’s well on it’s way. I would like to give a Erin Catto a big thank you, as the most of the ideas for the constraint solver come from his Box2D example code. (gPhysics Website). His contact persistence idea allows for stable stacks of objects with very few iterations of the contact solution. Couldn’t have gotten that working without his help.

Overview

Rigid bodies, collision shapes and sprites:

There is often confusion between rigid bodies and their collision shapes in Chipmunk and how they relate to sprites. A sprite would be a visual representation of an object, the sprite is drawn at the position of the rigid body. The collision shape would be the material representation of the object, and how it should collide with other objects. A sprite and collision shape have little to do with one another other than you probably want the collision shape to match the sprite’s shape.

C API Documentation

Initializing Chipmunk

Initializing Chipmunk is an extremely complicated process. The following code snippet steps you through the process:


cpInitChipmunk(); /* Actually, that's pretty much it */

Chipmunk memory management

For many of the structures you will use, Chipmunk uses a more or less standard set of memory management functions. For instance:

While you will probably use the new/free versions exclusively, the others can be helpful when writing language extensions.

In general, you are responsible for freeing any structs that you allocate. The only exception is that cpShapeDestroy() also destroys the specific shape struct that was passed to the constructor.

Chipmunk floats: cpFloat


typedef float cpFloat;

All Chipmunk code should be double safe, so feel free to redefine this.

Chipmunk vectors: cpVect

User accessible fields:


typedef struct cpVect{
    cpFloat x,y;
} cpVect

Simply a 2D vector packed into a struct. May change in the future to take advantage of SIMD.


#define cpvzero ((cpVect){0.0f, 0.0f})

Constant for the zero vector.


cpVect cpv(const cpFloat x, const cpFloat y)

Convenience constructor for creating new cpVect structs.


cpVect cpvadd(const cpVect v1, const cpVect v2)
cpVect cpvsub(const cpVect v1, const cpVect v2)

Add or subtract two vectors.


cpVect cpvneg(const cpVect v)

Negate a vector.


cpVect cpvmult(const cpVect v, const cpFloat s)

Scalar multiplication.


cpFloat cpvdot(const cpVect v1, const cpVect v2)

Vector dot product.


cpFloat cpvcross(const cpVect v1, const cpVect v2)

2D vector cross product analog. The cross product of 2D vectors exists only in the z component, so only that value is returned.


cpVect cpvperp(const cpVect v)

Returns the perpendicular vector. (90 degree rotation)


cpVect cpvproject(const cpVect v1, const cpVect v2)

Returns the vector projection of v1 onto v2.


cpVect cpvrotate(const cpVect v1, const cpVect v2)

Uses complex multiplication to rotate (and scale) v1 by v2.


cpVect cpvunrotate(const cpVect v1, const cpVect v2)

Inverse of cpvrotate().


cpFloat cpvlength(const cpVect v)

Returns the length of v.


cpFloat cpvlengthsq(const cpVect v)

Returns the squared length of v. Faster than cpvlength() when you only need to compare lengths.


cpVect cpvnormalize(const cpVect v)

Returns a normalized copy of v.


cpVect cpvforangle(const cpFloat a)

Returns the unit length vector for the given angle (in radians).


cpFloat cpvtoangle(const cpVect v)

Returns the angular direction v is pointing in (in radians).


*cpvstr(const cpVect v)

Returns a string representation of v. NOTE: The string points to a static local and is reset every time the function is called.

Chipmunk bounding boxes: cpBB

User accessible fields:


typedef struct cpBB{
    cpFloat l, b, r ,t;
} cpBB

Simple bounding box struct. Stored as left, bottom, right, top values.


cpBB cpBBNew(const cpFloat l, const cpFloat b, const cpFloat r, const cpFloat t)

Convenience constructor for cpBB structs.


int cpBBintersects(const cpBB a, const cpBB b)

Returns true if the bounding boxes intersect.


int cpBBcontainsBB(const cpBB bb, const cpBB other)

Returns true if bb completely contains other.


int cpBBcontainsVect(const cpBB bb, const cpVect v)

Returns true if bb contains v.


cpVect cpBBClampVect(const cpBB bb, const cpVect v)

Returns a copy of v clamped to the bounding box.


cpVect cpBBWrapVect(const cpBB bb, const cpVect v)

Returns a copy of v wrapped to the bounding box.

Chipmunk spatial hashes: cpSpaceHash

The spatial hash isn’t yet ready for user use. However, it has been made in a generic manner that would allow it to be used for more than just Chipmunk’s collision detection needs.

Chipmunk rigid bodies: cpBody

User accessible fields:


typedef struct cpBody{
    cpFloat m, m_inv;
    cpFloat i, i_inv;

    cpVect p, v, f;
    cpFloat a, w, t;
    cpVect rot;
} cpBody

cpBody *cpBodyAlloc(void)
cpBody *cpBodyInit(cpBody *body, cpFloat m, cpFloat i)
cpBody *cpBodyNew(cpFloat m, cpFloat i)

void cpBodyDestroy(cpBody *body)
void cpBodyFree(cpBody *body)

Uses the standard suite of Chipmunk memory functions. m and i are the mass and moment of inertia for the body.


void cpBodySetMass(cpBody *body, cpFloat m);
void cpBodySetMoment(cpBody *body, cpFloat i);
void cpBodySetAngle(cpBody *body, cpFloat a);

Because several of the values are linked, (m/m_inv, i/i_inv, a/rot) don’t set them explicitly, use these setter functions instead.


cpVect cpBodyLocal2World(cpBody *body, cpVect v)

Convert from body local coordinates to world space coordinates.


cpVect cpBodyWorld2Local(cpBody *body, cpVect v)

Convert from world space coordinates to body local coordinates.


void cpBodyApplyImpulse(cpBody *body, cpVect j, cpVect r)

Apply the impulse j to body with offset r. Both j and r should be in world coordinates.


void cpBodyResetForces(cpBody *body)

Zero both the forces and torques accumulated on body.


void cpBodyApplyForce(cpBody *body, cpVect f, cpVect r)

Apply (accumulate) the force f on body with offset r. Both f and r should be in world coordinates.


void cpBodyUpdateVelocity(cpBody *body, cpVect gravity, cpFloat damping, cpFloat dt)

Updates the velocity of the body using Euler integration. You don’t need to call this unless you are managing the object manually instead of adding it to a cpSpace.


void cpBodyUpdatePosition(cpBody *body, cpFloat dt)

Updates the position of the body using Euler integration. Like cpBodyUpdateVelocity() you shouldn’t normally need to call this yourself.


void cpDampedSpring(cpBody *a, cpBody *b, cpVect anchr1, cpVect anchr2, cpFloat rlen, cpFloat k, cpFloat dmp, cpFloat dt)

Apply a spring force between bodies a and b at anchors anchr1 and anchr2 respectively. k is the spring constant (force/distance), rlen is the rest length of the spring, dmp is the damping constant (force/velocity), and dt is the time step to apply the force over. Note: not solving the damping forces in the impulse solver causes problems with large damping values. This function will eventually be replaced by a new constraint (joint) type.

Notes:

Chipmunk collision shapes: cpShape

There are currently 3 possible collision shapes:

User accessible fields:


typedef struct cpShape{
    cpBB bb;

    unsigned long collision_type;
    unsigned long group;
    unsigned long layers;

    void *data;

    cpBody *body;
    cpFloat e, u;
    cpVect surface_v;
} cpShape;

void cpShapeDestroy(cpShape *shape)
void cpShapeFree(cpShape *shape)

Destroy and Free functions are shared by all shape types.


cpBB cpShapeCacheBB(cpShape *shape)

Updates and returns the bounding box of shape.


void cpResetShapeIdCounter(void)

Chipmunk keeps a counter so that every new shape is given a unique hash value to be used in the spatial hash. Because this affects the order in which the collisions are found and handled, you should reset the shape counter every time you populate a space with new shapes. If you don’t, there might be (very) slight differences in the simulation.


cpCircleShape *cpCircleShapeAlloc(void)
cpCircleShape *cpCircleShapeInit(cpCircleShape *circle, cpBody *body, cpVect offset, cpFloat radius)
cpShape *cpCircleShapeNew(cpBody *body, cpVect offset, cpFloat radius)

body is the body to attach the circle to, offset is the offset from the body’s center of gravity in body local coordinates.


cpSegmentShape* cpSegmentShapeAlloc(void)
cpSegmentShape* cpSegmentShapeInit(cpSegmentShape *seg, cpBody *body, cpVect a, cpVect b, cpFloat radius)
cpShape* cpSegmentShapeNew(cpBody *body, cpVect a, cpVect b, cpFloat radius)

body is the body to attach the segment to, a and b are the endpoints, and radius is the thickness of the segment.


cpPolyShape *cpPolyShapeAlloc(void)
cpPolyShape *cpPolyShapeInit(cpPolyShape *poly, cpBody *body, int numVerts, cpVect *verts, cpVect offset)
cpShape *cpPolyShapeNew(cpBody *body, int numVerts, cpVect *verts, cpVect offset)

body is the body to attach the poly to, verts is an array of cpVect’s defining a convex hull with a counterclockwise winding, offset is the offset from the body’s center of gravity in body local coordinates.

Notes:

Chipmunk joints: cpJoint

There are currently 4 kinds of joints:


void cpJointDestroy(cpJoint *joint)
void cpJointFree(cpJoint *joint)

Destroy and Free functions are shared by all joint types.


cpPinJoint *cpPinJointAlloc(void)
cpPinJoint *cpPinJointInit(cpPinJoint *joint, cpBody *a, cpBody *b, cpVect anchr1, cpVect anchr2)
cpJoint *cpPinJointNew(cpBody *a, cpBody *b, cpVect anchr1, cpVect anchr2)

a and b are the two bodies to connect, and anchr1 and anchr2 are the anchor points on those bodies.


cpSlideJoint *cpSlideJointAlloc(void)
cpSlideJoint *cpSlideJointInit(cpSlideJoint *joint, cpBody *a, cpBody *b, cpVect anchr1, cpVect anchr2, cpFloat min, cpFloat max)
cpJoint *cpSlideJointNew(cpBody *a, cpBody *b, cpVect anchr1, cpVect anchr2, cpFloat min, cpFloat max)

a and b are the two bodies to connect, anchr1 and anchr2 are the anchor points on those bodies, and min and max define the allowed distances of the anchor points.


cpPivotJoint *cpPivotJointAlloc(void)
cpPivotJoint *cpPivotJointInit(cpPivotJoint *joint, cpBody *a, cpBody *b, cpVect pivot)
cpJoint *cpPivotJointNew(cpBody *a, cpBody *b, cpVect pivot)

a and b are the two bodies to connect, and pivot is the point in world coordinates of the pivot. Because the pivot location is given in world coordinates, you must have the bodies moved into the correct positions already.


cpGrooveJoint *cpGrooveJointAlloc(void)
cpGrooveJoint *cpGrooveJointInit(cpGrooveJoint *joint, cpBody *a, cpBody *b, cpVect groove_a, cpVect groove_b, cpVect anchr2)
cpJoint *cpGrooveJointNew(cpBody *a, cpBody *b, cpVect groove_a, cpVect groove_b, cpVect anchr2)

The groove goes from groov_a to groove_b on body a_, and the pivot is attached to _anchr2 on body b. All coordinates are body local.

Notes:

Chipmunk spaces: cpSpace

User accessible fields:


typedef struct cpSpace{
    int iterations;

    cpVect gravity;
    cpFloat damping;

    int stamp;
} cpSpace;

void cpSpaceFreeChildren(cpSpace *space)

Frees all bodies, shapes and joints added to the system.


cpSpace* cpSpaceAlloc(void)
cpSpace* cpSpaceInit(cpSpace *space, int iterations)
cpSpace* cpSpaceNew(int iterations)

void cpSpaceDestroy(cpSpace *space)
void cpSpaceFree(cpSpace *space)

More standard Chipmunk memory functions.


void cpSpaceFreeChildren(cpSpace *space)

This function will free all of the shapes, bodies and joints that have been added to space.


void cpSpaceAddShape(cpSpace *space, cpShape *shape)
void cpSpaceAddStaticShape(cpSpace *space, cpShape *shape)
void cpSpaceAddBody(cpSpace *space, cpBody *body)
void cpSpaceAddJoint(cpSpace *space, cpJoint *joint)

void cpSpaceRemoveShape(cpSpace *space, cpShape *shape)
void cpSpaceRemoveStaticShape(cpSpace *space, cpShape *shape)
void cpSpaceRemoveBody(cpSpace *space, cpBody *body)
void cpSpaceRemoveJoint(cpSpace *space, cpJoint *joint)

These functions add and remove shapes, bodies and joints from space. Shapes added as static are assumed not to move. Static shapes should be be attached to a rigid body with an infinite mass and moment of inertia. Also, don’t add the rigid body used to the space, as that will cause it to fall under the effects of gravity.


void cpSpaceResizeStaticHash(cpSpace *space, cpFloat dim, int count)
void cpSpaceResizeActiveHash(cpSpace *space, cpFloat dim, int count)

The spatial hashes used by Chipmunk’s collision detection are fairly size sensitive. dim is the size of the hash cells. Setting dim to the average objects size is likely to give the best performance.

count is the suggested minimum number of cells in the hash table. Bigger is better, but only to a point. Setting count to ~10x the number of objects in the hash is probably a good starting point.

By default, dim is 100.0, and count is 1000.


void cpSpaceRehashStatic(cpSpace *space)

Rehashes the shapes in the static spatial hash. You only need to call this if you move one of the static shapes.


void cpSpaceStep(cpSpace *space, cpFloat dt)

Update the space for the given time step. Using a fixed time step is highly recommended. Doing so will increase the efficiency of the contact persistence, requiring an order of magnitude fewer iterations to resolve the collisions in the usual case.

Notes:

Miscellaneous.


cpFloat cpMomentForCircle(cpFloat m, cpFloat r1, cpFloat r2, cpVect offset)

Calculate the moment of inertia for a circle. Arguments are similar to cpCircleShapeInit(). m_ is the mass, _r1 and r2 define an inner and outer radius, and offset is the offset of the center from the center of gravity of the rigid body.


cpFloat cpMomentForPoly(cpFloat m, int numVerts, cpVect *verts, cpVect offset)

Calculate the moment of inertia for a poly. Arguments are similar to cpPolyShapeInit() m_ is the mass, _numVerts is the number of vertexes in verts, and offset is the offset of the poly coordinates from the center of gravity of the rigid body.

Collision pair functions

Collision pair functions allow you to add callbacks for certain collision events. Each cpShape structure has a user definable collision_type field that is used to identify its type. For instance, you could define an enumeration of collision types such as bullets and players, and then register a collision pair function to reduce the players health when a collision is found between the two.

Additionally, the return value of a collision pair function determines whether or not a collision will be processed. If the function returns false, the collision will be ignored. One use for this functionality is to allow a rock object to break a vase object. If the approximated energy of the collision is above a certain level, flag the vase to be removed from the space, apply an impulse to the rock to slow it down, and return false. After the cpSpaceStep() returns, remove the vase from the space.

WARNING: It is not safe for collision pair functions to remove or free shapes or bodies from a space. Doing so will likely end in a segfault as an earlier collision may already be referencing the shape or body. You must wait until after the cpSpaceStep() function returns.


typedef struct cpContact{
    cpVect p, n;
    cpFloat dist;

    cpFloat jnAcc, jtAcc;
} cpContact;

An array of cpContact structs are passed to collision pair functions. Some user accessible fields include:


typedef int (*cpCollFunc)(cpShape *a, cpShape *b, cpContact *contacts, int numContacts, cpFloat normal_coef, void *data)

Prototype for a collision callback function. The two colliding shapes are passed as a and b, along with the contact points, and a user definable pointer are passed as arguments. The shapes are passed in the same order as their types were registered using cpSpaceAddCollisionPairFunc(). Because Chipmunk may swap the shapes to accommodate your collision pair function the normals may be backwards. Always multiply the normals by normal_coef before using the values. The contacts array may be freed on the next call to cpSpaceStep().


void cpSpaceAddCollisionPairFunc(cpSpace *space, unsigned long a, unsigned long b, cpCollFunc func, void *data)

Register func to be called when a collision is found between a shapes with collision_type fields that match a and b. data is passed to func as a parameter. The ordering of the collision types will match the ordering passed to the callback function.

Passing NULL for func will reject any collision with the given collision type pair.


void cpSpaceRemoveCollisionPairFunc(cpSpace *space, unsigned long a, unsigned long b)

Remove the function for the given collision type pair. The order of a and b must match the original order used with cpSpaceAddCollisionPairFunc().


void cpSpaceSetDefaultCollisionPairFunc(cpSpace *space, cpCollFunc func, void *data)

The default function is called when no collision pair function is specified. By default, the default function simply accepts all collisions. Passing NULL for func will reset the default function back to the default. (You know what I mean.)

Passing NULL for func will reject collisions by default.

Advanced topics

Advanced collision processing

Using collision pair functions, it’s possible to get information about a collision such as the locations of the contact points and the normals, but you can’t get the impulse applied to each contact point at the time the callback is called. Because Chipmunk caches the impulses, it is possible to access them after the call to cpSpaceStep() returns.

The impulse information is stored in the jnAcc and jtAcc fields of the cpContact structures passed to the collision pair function. So you must store a reference to the contacts array in the collision pair function so that you can access it later once the impulses have been calculated.


cpVect cpContactsSumImpulses(cpContact *contacts, int numContacts);
cpVect cpContactsSumImpulsesWithFriction(cpContact *contacts, int numContacts);

Sums the impulses applied to the the given contact points. cpContactsSumImpulses() sums only the normal components, while cpContactsSumImpulsesWithFriction() sums the normal and tangential componets.

Notes:

Collision pair functions, groups, and layers

There are three ways that you can specify which shapes are allowed to collide in Chipmunk: collision pair functions, groups, and layers. What are their intended purposes?

Collision pair functions: More than just a callback, collision pair functions can conditionally allow a collision between two shapes. This is the only choice if you need to perform some logic based on the shapes or contact information before deciding to allow the collision.

Groups: Groups filter out collisions between objects in the same non-zero groups. A good example of when groups would be useful is to create a multi-body, multi-shape object such as a ragdoll. You don’t want the parts of the ragdoll to collide with itself, but you do want it to collide with other ragdolls.

Layers: Layers are another way of grouping shapes. Collision between shapes that don’t occupy one or more of the same layers are filtered out. Layers are implemented using a bitmask on an unsigned long, so there are up to 32 layers available.

To be clear, for a collision to occur, all of the tests have to pass. Additionally, collisions between static shapes are not considered nor are collisions between shapes connected to the same rigid body.

Mysteries of cpSpaceStep() explained.

The cpSpaceStep() function is really the workhorse of Chipmunk. So what exactly does it do?

Chipmunk does a lot of processing on the shapes in the system in order to provide robust and fast collision detection, but the same is not true of the rigid bodies. Really all cpSpaceStep() does to the bodies in the system is to integrate them and apply impulses to them.

The integration step is really just for convenience. If you integrate the velocity of your rigid bodies before calling cpSpaceStep() and integrate their positions afterward, you don’t have to add them to the space at all. In fact, there are good reasons for not doing so. All bodies in the space are integrated using the same gravity and damping, and this prevents you from providing interesting objects such as moving platforms.

If you are going to do the integration for your rigid bodies manually, I would highly recommend that you use cpBodyUpdatePosition() to integrate the position of the objects and only integrate the velocity. cpBodyUpdatePosition() is a required step for penetration resolution, and weird things could happen if it’s not called. Chipmunk uses Euler integration, so calculating the velocity required to move a body to a specific position is trivial if that is what you wish to do.

Chipmunk globals.

Chipmunk was designed with multithreading in mind, so very few globals are used. This shouldn’t be a problem in most cases as it’s likely you’ll only need to set them on a per application basis (if at all).

int cp_contact_persistence: This determines how long contacts should persist. This number should be fairly small as the cached contacts will only be close for a short time. cp_contact_persistence defaults to 3 as it is large enough to help prevent oscillating contacts, but doesn’t allow stale contact information to be used.

cpFloat cp_collision_slop: The amount that shapes are allowed to penetrate. Setting this to zero will work just fine, but using a small positive amount will help prevent oscillating contacts. cp_collision_slop defaults to 0.1.

cpFloat cp_bias_coef: The amount of penetration to reduce in each step. Values should range from 0 to 1. Using large values will eliminate penetration in fewer steps, but can cause vibration. cp_bias_coef defaults to 0.1.

cpFloat cp_joint_bias_coef: Similar to cp_bias_coef, but for joints. Defaults to 0.1. In the future, joints might have their own bias coefficient instead.

Known Problems

Performance/Quality tuning

There are a number of things you can do to increase the performance of Chipmunk:

If you have problems with jittery or vibrating objects, you need to do mostly the opposite:

To do

There are a number of things left on my todo list:

Contact information

Drop me a line. Tell me how great you think Chipmunk is or how terribly buggy it is. I’d love to hear about any project that people are using Chipmunk for.

AIM: slembcke@mac.com

Email: lemb0029(at)morris(dot)umn(dot)edu or slembcke(at)gmail(dot)com

I can also be found lurking about the iDevGames forums.

License

Copyright© 2007 Scott Lembcke

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.