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:
- 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
- making piece wise linear shapes, aka polygons, to represent shapes
- making images to represent where shapes were solid
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.
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
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;
s.center = 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)