Shadow Covenant

Lately, on the gamedev side of life, I’ve been working on a platform game structure, so I could create a more or less complete platform game from an editor…

I was considering three engines on which to build the “Game Player” itself: Flash (Flex-based), Torque (Torque Game Builder, more exactly) and Spellbook (my own engine).

One of the most important aspects for me was the ability to use my pipeline to build the game… so that would imply creating the assets in 3d Studio, use a tool we call IBGen to build the sprite images and then use that for the game.

So, I started with a Actionscript exporter for my Flash tries… Although I got a platformer structure working pretty fast, Flash is just too slow for my purposes, which is too bad, since it was going very well:

Flash would have the advantage of running on lots of platforms (Mac, PC, Linux, and so on), with a huge ammount of compatibility, from a HW standpoint (the old PC-dev nemesis!).

I tried Torque Game Builder (TGB) next, with the Platformer Starter Kit (PSK). And while it had some nice ideas, the ammount of work on the code itself that would have to be done to adjust itself to the needs of my project would have been too big, considering that I would have to learn the inner workings of Torque and PSK… But the state machine that the PSK uses was very nice, so I kind of designed a similar system for my own platform system.

So I decided to go Spellbook, and all was good… until I had to do collision detection…

Normally, I do collision detection in 2d either using tilemaps and circles, or by cheating, testing horizontal and vertical displacements separatly and reacting accordingly, but at the end of all projects, I end up with an extremely ugly piece of code that’s too finicky to work with again… and each time I swear I’m going to do a better job at that…

Well, this time I decided to try to do it correctly from the start, using 2d polygons as collision primitives and reacting appropriately (more or less physically correct) to the collisions.

On my initial formulation of the problem, I’d like to find out if a polygon A that will want to move a certain delta will collide with polygon B, and if so, find out when and where.

Some quick searches later, I didn’t seem to find a general swept-polygon test, so I had to implement my own.

My own test is not as efficient as it could be, I think… For example, I can probably take advantage of the fact that the polygons are convex to speed up the process, but the algorithm outlined below is fast enough for my needs…

My algorithm is all designed around of checking if the line segment formed from points Pn and P’n intersect any side of the other polygon:

Pn is the nth point of the first polygon, P’n is that point offset by the delta, so P’n=Pn+delta.

So, check if that segment collides with any of the segments that define the second polygon, taking the one that will take less “time” to hit.

To discover the intersection of two line segments, La and Lb, you just have to solve the equation:

La=Lb

Since La=P1+ua(P2-P1) and Lb=P3+ub(P4-P3), and we’re working in 2d, we get the following two equations:

x1+ua(x2-x1)=x3+ub(x4-x3)

y1+ua(y2-y1)=y3+ub(y4-y3)

Solving for ua and ub, we get something like:

den=(y4-y3)(x2-x1)-(x4-x3)(y2-y1)

ua=((x4-x3)(y1-y3)-(y4-y3)(x1-x3))/den

ub=((x2-x1)(y1-y3)-(y2-y1)(x1-x3))/den

If den=0, the lines are parallel and will never intersect, unless the numerator of both equations are also 0, in that case the lines are coincident.

Finally, if 0<ua<1, the lines intersect, and point of intersection is PC=P1+ua(P2-P1).

One thing I’ve noticed is that since the polygons are convex, you only have test half the segments in the polygon, the segments that are facing the opposite direction from the delta (green ones, in the example below):

The whole function would look similar to:

t_min=FLT_MAX
For all vertexes(V) in poly A
   For all edges(E) in poly B
      P1=V
      P2=V+delta
      t=point_of_intersection(P1,P2,E)
      if (in_range(t,0,1) and in_range(t,0,t_min)) then
         best_vertex=V
         best_edge=E
         t_min=t
      end
   end
end
For all vertexes(V) in poly B
   For all edges(E) in poly A
      P1=V
      P2=V+delta
      t=point_of_intersection(P1,P2,E)
      if (in_range(t,0,1) and in_range(t,0,t_min)) then
         best_vertex=V
         best_edge=E
         t_min=t
      end
   end
end
if (t_min==FLT_MAX) return NO_INTERSECTION
TimeOfContact=t_min
PointOfContact=V+delta*t_min
NormalOfContact=E.normal()

One important thing about this routine: it just handles collisions through movement (if the object is already colliding when the test is done, it will acknowledge no collision).

Now, collision response is as important as collision detection, since that’s where lots of things can go bad…

When we don’t detect a collision on object A moving a certain delta, end position of said object is just:

posA=posA+delta

But what happens if we have a collision?

Well, we have to contemplate some movement and modify the delta, according to the normal:

   if (test_collision(A,delta,TimeOfContact,PointOfContact,Normal)) then
      posA=posA+delta*TimeOfContact
   else
      posA=posA+delta
   end

But imagine you have gravity and are moving to the right, so that delta=(10,10) and you detect the collision time is 0.2 (from a possible 0..1).

So, you would move down 2 units, and to the right 2 units, and then stop, instead of moving 10 units to the right, since nothing is stopping the player from doing that!

So, we need to account for multiple collisions during the whole time interval, and we get to something like:

   float total_time=1
   while (test_collision(A,delta,TimeOfContact,PointOfContact,Normal)) then
      posA=posA+delta*min(TimeOfContact,total_time)
      total_time=total_time-TimeOfContact
      delta=delta-normal*dot_product(normal,delta)
      if (delta.is_null) break
   end

The “delta=delta-normal*dot_product(Normal,delta)” removes the offending movement component from the displacement vector. In the above example, the new delta would be (10,0), and we would only have 0.8 time to move on that vector. This would create the correct final position of (10,2), instead of the incorrect (2,2) of the first version.

Now, there’s a final problem with this solution… Since our poly/poly intersection function can’t handle cases where a collision is already existing, this would fail, since the first intersection would make the first polygon be lying just on top of the the second polygon, intersecting the edge (correctly), but future movement would pass right through it…

You could handle this case by checking for colinearity and a series of other processes, but I found out that the simpler way to work this through is now to allow the movement that would bring us to that limit case, by just changing the order of a couple of operations:

   float total_time=1
   while (test_collision(A,delta,TimeOfContact,PointOfContact,Normal)) then
      delta=delta-normal*dot_product(normal,delta)
      if (delta.is_null) break
      posA=posA+delta*min(TimeOfContact,total_time)
      total_time=total_time-TimeOfContact
   end

While this isn’t as correct from a formal standpoint, it works great in practice, stopping those small edge cases that can be quite tricky to get working correctly…

Any questions, or suggestions of improvements, let me know… I’m sure I can make this a better algorithm by taking in account the fact that the polygons are convex.

Note that this algorithm works with concave polygons aswell, but you’d have to remove the dot_product test on the poly/poly intersection test, and make sure the scale of the objects are very different, so that you don’t have simultaneous collisions to handle, which happens quite easily in concave polygons.