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)
continue;
for (int x = (int)(localCenter.X - localRadius); x <>= sObj.TexCollision.Width)
continue;

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

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)
continue;

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;
}
else
{
thisLen++;
}
}

// 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;
s.center = dObj.position;
s.v = collisionNormal * 30;
s.c = Color.Blue;
s.scale = 2;
Game.level.DebugVectors.Add(s);
}

float objVelocityOriginalMagnitude = dObj.velocity.Length();

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

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)
Game.sound.soundsToPlayThisFrame.Add("hit");
}