Monday, May 19, 2008

Pixelated Martini Roller - Collision - Triangle Game Jam 2008

More Pixelated Martini Roller game stuff (other posts)... I just pulled everything off my camera and noticed this video showing the collision system in progress:

Collision system in progress
(a final video can be found here)

I figured I'd briefly write up what we decided to do for the collision / physics. Nolan had already put together some simple gameplay motion. We used Aristotelian physics: objects are at rest unless something actively disturbs them. AKA apply velocity only, not acceleration. Well, some velocity is recycled frame to frame... but, that not what I really was going to talk about. That would be collision:

We wanted:
  • easy to make art
  • simple to code collision
  • fairly decent performance, even with lots of objects, but lets just get the thing working quickly
  • robustness even when many objects are overlapping
We really only considered
  • making piece wise linear shapes, aka polygons, to represent shapes
  • making images to represent where shapes were solid
We ended up with colliding against images because it greatly simplified art workflow (just paint a version of the sprite with what you wanted to be solid), would allow for pretty complicated shapes, and I figured the code may be easier.

Nolan and I pair programmed it at the end of the day Saturday, good thing too, we were both getting tired. Here's what we did:
  • The olive is a circle in gameplay.
  • Initialize a 1D buffer representing the closest any surface is to the center of the circle for a given arc. We ended up cranking this up to an arc being 1 degree. Init value is float_max. Call this buffer buckets.
  • For all sprites:
  • transform the circle to sprite local space
  • check if you're overlapping the sprite at all
  • for the overlapping area, scan through all texels:
  • if the texel is solid, transform it to polar coordinates, and set the bucket value if this new point is closer to circle center.
  • ...
  • Then, check through all the buckets, did we find some collision and some not collision?
  • If not, quit, can't do anything useful.
  • If so, scan through the buckets looking for the largest open area. This will be the widest open space around our circle, and the way out.
  • (btw, need to loop around the circle, regardless of the buffer's boundary, so everything uses modulo math)
  • Find the center of the largest open space, and consider that the normal to the surface.
  • ...
  • Now, get out of whatever objects we may have gotten into:
  • for every bucket, transform out of polar coordinates, and then compute the distance from that point to the penetrating side of the circle, in the direction of the normal. The max value tells us how far to move out along the normal to no longer be in collision.
  • ...
  • If we have any velocity along the normal, remove it (we we don't move into the object).
  • Take a portion of that velocity and apply it tangentially, to keep up some momentum.
  • ....
  • And, if we hit the surface hard enough, make some noise.
Overall I think the system worked out pretty well. It was very easy to make art. The gameplay felt pretty good. It was fairly quick to code. It was pretty robust, even when nasty shapes.

Downsides: The olive was overly sticky to some surfaces, you can crawl around objects sometimes a bit before falling off. That was related to us basically turning gravity way down if you're already sitting on a surface. Without doing that you couldn't roll around as freely as we liked.

Note: Noland replied to this post --- check out the comments

Code from the above, if you're into that:
static bool debugGeom = false;
static int numBuckets = 360 / 1;
static float[] buckets = new float[numBuckets];

public static void DetectCollision(DynamicObject dObj)
for (int i = 0; i < airborne =" true;" sobj =" bObj" collisiondata ="=" localcenter =" dObj.position" localradius =" dObj.radius" y =" (int)(localCenter.Y">= sObj.TexCollision.Height)
for (int x = (int)(localCenter.X - localRadius); x <>= sObj.TexCollision.Width)

Vector2 sampleVec = new Vector2(x, y) - localCenter;
if (sampleVec.LengthSquared() > localRadius * localRadius)

float angle = (float)Math.Atan2(sampleVec.Y, sampleVec.X);
int bucket = ((int)(angle * numBuckets / (2 * Math.PI)) + numBuckets) % numBuckets;

Color c = sObj.collisionData[x + y * sObj.TexCollision.Width];
if (c.A == 0)

buckets[bucket] = Math.Min(buckets[bucket], sampleVec.Length()) / localRadius;


// Find the longest bucket chain
int first;
bool found = false;
for (first = 0; first < found =" true;" chainmiddle =" 0;" maxlength =" 0;" thislen =" 0;" i =" 0;" b =" (first"> maxLength)
maxLength = thisLen;
chainMiddle = (b - thisLen / 2 + numBuckets) % numBuckets;
thisLen = 0;

// find the distance we need to move to get the circle not penetrating

float rot = (float)(chainMiddle * 2 * Math.PI / numBuckets);
Vector2 collisionNormal = new Vector2((float)Math.Cos(rot), (float)Math.Sin(rot));

// Fix up penetration position
// walk through all buckets, project point back into local dObj space
// Find longest distance along normal to sphere edge
// translate the sphere that distance along the normal
// NOTE: given that we only store one value in bucket[], it's possible there
// is a slightly more distance value that has a higher penetration depth.
// Oh well.
// Also, this isn't quite right for the martini glass. It works *well enough*.
float penetrationDistance = 0;
for (int i = 0; i < bucketrot =" (float)(i" point =" new" pointdotnormal =" Vector2.Dot(point," basedotnormal =" Vector2.Dot(-collisionNormal," distpointtospherebase =" pointDotNormal" collisiontangent =" new" pointdottangent =" Vector2.Dot(point," angletopenetrationpoint =" (float)Math.Acos((float)Math.Abs(pointDotTangent));" distspherebasetosphere =" (float)Math.Sin((float)angleToPenetrationPoint);" distpointtosphere =" distPointToSphereBase" penetrationdistance =" Math.Max(distPointToSphere," positionadjust =" collisionNormal" adjustlen =" positionAdjust.Length();"> 0) ? 1 : -1) * adjustLen / dObj.radius;

if (debugGeom)
Level.DebugRecord s; = dObj.position;
s.v = collisionNormal * 30;
s.c = Color.Blue;
s.scale = 2;

float objVelocityOriginalMagnitude = dObj.velocity.Length();

float ColisionNormalDotVelocity = Vector2.Dot(collisionNormal, dObj.velocity);
float dotNormalized = ColisionNormalDotVelocity / objVelocityOriginalMagnitude;
if (ColisionNormalDotVelocity > 0)

dObj.airborne = false;
dObj.lastGround = 0;

Vector2 penetratingVelocity = collisionNormal * ColisionNormalDotVelocity;

// Remove penetratingVelocity velocity from object
dObj.velocity -= penetratingVelocity;

// Transfer velocity that was penetratingVelocity into tangential
float objVelocityTruncated = dObj.velocity.Length();
if (objVelocityTruncated > 0.01)
float amountToTransfer = (1 - (-dotNormalized)); // transfer only if not directly into collision
float objVelocityResulting = MathHelper.Lerp(objVelocityTruncated, objVelocityOriginalMagnitude, amountToTransfer);
dObj.velocity *= objVelocityResulting / objVelocityTruncated;

// Should we make a noise?
const float minHitVelocityForSound = 1f; //TODO make this better? tune it in XACT or something?
if (Math.Abs(ColisionNormalDotVelocity) > minHitVelocityForSound)

1 comment:

  1. I was quite happy with the collision detection. Even against multiple surfaces and in tight corners, it consistently picks out a good collision normal. I'm still just not very happy with our collision response. I tried to fix it, but I couldn't rationalize spending too much time on something that worked "well enough." Apparently it did, if you didn't think anything was wrong with it. ;)

    I still think there might be something wrong with my math on the penetration fix up. Although, it may be that the optimization to not reconsider all points again to find the maximum distance and to instead just use the bucket distances was giving incorrect results (as the comment points out.)

    If there was anything I would want to fix about our collision response system though, it would be to be able to have a rest state in a tight corner. Before the penetration position correction, the olive would roll into a corner and stop (but possibly penetrate the resting surface.) Once we moved the olive after a collision, it prevented this rest state from ever occurring.