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)

Sunday, May 11, 2008

Triangle Game Jam, It's Over!

Nicer videos and reports will come later I'm sure [EDIT: Here is high quality video], but for now here's a handheld video of the Pixelated Martini Roller when we ran out of time:

You're an olive. You like martinis. You roll around and get to umbrellas for checkpoints. Sitting in a martini glass gets you a bit tipsy. You've got more energy and can jump higher. But watch out, stay too long and you get sloppy. You'll stagger around, and your jumps won't land you where you want to go.
As you get tipsy the screen gets pixelated (hard to see in this video), and the music sounds like it's had too much to drink too (hard to hear in this video).
Thanks for everyone at the Jam for a good time. Thanks for Michael Noland and Adrienne Walker for working together on this game with me, and Brad for the title screen.
(music by STU,, MyMelody, Creative Commons attribution license)

Saturday, May 10, 2008

Triangle Game Jam part way results

The theme is game madlibs. We've picked several ridiculous game titles to implement, and several teams are well under way. I'm working on Pixelated Martini Roller:

But, you've also got to check out the progress on Musical Dragon Twirler:

Getting sleepy now....

Friday, May 9, 2008

Pre Triangle Game Jam, May 2008

The Triangle Game Jam 2008 starts tomorrow! It'll be quite exciting. This is the second Triangle Game Jam, we did one last summer as well. There, Mike Daly and I made Shape Slasher:

Mike had the idea to cut up shapes and try to score the result based on how nice of a triangle it was. We decided that the size of the triangle shouldn't matter, just how close it was to an equilateral triangle. Mike wrote some scoring code for triangle shapes, and I wrote a definition of n-gons and code to cut them. We decided to always have convex shapes.

Things turned out well, Mike made some procedural level generation code with different shape size, irregularity complexity, and speeds. I dressed up the graphics a bit, worked on the code for cutting and movement, etc.

We added special bonus rounds as well, so gamplay alternates between levels with moving random pieces, and bonus rounds with shapes that start off still. Your job is to quickly decide how to cut and collect as many triangles as possible in a limited amount of time.

The game turned out to be pretty fun, and we had a good difficulty curve over the duration of several levels. The final stage is quite challenging, and the last bonus stage is a rare treat. ;)

Since the first game jam, spending a lot of energy getting used to XNA and C#, we've gotten faster and continued to use XNA.