dinsdag 28 juni 2011

Simple sphere-based collision detection and response

1. Introduction

This tutorial will serve as a guide for implemening a simple sphere-based collision detection and handling routine. There is a lot of information available on these subjects on the internet, but most of this information is fragmented or poorly explained. Additionally, a lot of information is focused on collision detection with polygons, which is not what I am looking for.

The focus of this guide is on sphere-based collision detection in a tile-based 2D world. While the world is tile-based, the objects can move freely in real coordinates, allowing for more realistic movement. However, this obviously creates some new challenges, especially in pathfinding and collision detection. This guide will hopefully explain in a clear manner how to deal with this problem.

Spheres are a convenient way to efficiently do collision detection for large amounts of objects. Collision checks with spheres are extremely fast, and spheres have some very nice properties that make collision response also relatively simple. Additionally, most game objects can actually be approximated with a spherical shape. If this is not the case, they usually can with a number of spherical shapes. This does not change anything about the algorithms in the following guide; just process each sphere individually as if it is a separate object.

Using spheres to represent game objects in collision detection has a number of advantages over boxes. Boxes have very easy collision checks, but are more difficult to deal with in collision response. It is very difficult to compute how to maneuver two boxes around each other without them colliding at any point. When you only need simple collision response such as "destroy one of the two objects" or "bounce back", collision boxes might be a better and simpler choice over spheres. But in cases where you need somewhat realistic collision behaviour, such as in RTS games, spheres are much more suitable.

And yes, I know a sphere is the 3D version of the 2D circle and that this guide is actually about collision detection with circles. But bounding sphere seems to be the general term used for this kind of thing, so I'll stick with it.

2. Collision detection

The best way to approach collision detection and response is by splitting the movement process up into three separate loops over the game objects. In the first loop (the update loop), each game object determines the location it wants to go to. After this, each object \(i\) has a current location \(L_i\) and a movement vector \(M_i\). In the second loop (the collision detection loop), all objects are tested against each other for collisions. If a collision is detected, it is dealt with gracefully by updating the movement vectors \(M_i\). In the final iteration, the location of all the objects is updated: \(L_i = L_i + M_i\).

We will now discuss the structure of the second loop. For each object \(i\), find all the other objects \(j\) that need a collision check. You can limit the number of collision checks by working with a quad tree or another space division structure. This is highly recommended if there are a lot of objects in your world. For more information on quad trees, see http://en.wikipedia.org/wiki/Quadtree.

We assume that each object \(i\) has a sphere associated with it, positioned at the location of the object \(L_i\) with radius \(R_i\). In order to check for a collision between two objects, we substract radii of the spheres from the distance of the two objects:

$$\left\| (L_i+M_i) - (L_j+M_j) \right\| - R_i - R_j$$

If this is negative, there is a collision, and it must be processed. In games, time is usually divided into so-called ticks, or discrete time steps at which the game is updated. This means that each object does not move continually but in large steps as well. That the objects collide at the end of the time step does not mean that they do halfway there. To have clean movement, we need to detect at which point in time the collision occurs.

The following piece of code does exactly that in a very efficient way:
bool hit = checkCollision(O1, M1, O2, M2);
if (!hit) return;
int n = 1;
double t = 1.0;
double tBestSoFar = 0.0;
while (n < 5) {

   // reduce the movement range by a factor 2^n
   double piece = 1.0 / pow(2.0, n);

   // if we had a hit, we move back one piece
   if (hit) t -= piece;

   // if we don't have a hit, we add one piece
   else t += piece;

   // we check for collision at the new location
   hit = checkCollision(O1, M1*t, O2, M2*t);

   // if we don't have a hit, we have found a better match for our t
   if (!hit) tBestSoFar = t;

   // next iteration

 // change the movement vector for both objects
 SM1 = M1*tBestSoFar;
 SM2 = M2*tBestSoFar;  

This algorithm will look for the point in time (where as location for t=0 is \(L_i\) and location for t=1 is \(L_i + M_i\)) where the collision occurs. It starts by testing for a collision at t=1, and if there is one, the algorithm proceeds. It will first look at 0.5 for a collision, and if there is one, it will then look at 0.25, otherwise it will look at 0.75. This process is repeated with double the accuracy each time. This results in a pretty accurate estimation of when the collision occurs.

After this computation, \(SM_i\) contains the part of the original move vector \(M_i\) that is safe to carry out for both objects without having a collision. This code will cause no objects to ever collide, but does not handle collisions really well. If an object encounters another object that is not moving, it will just stop forever, because it cannot find a way around the other object. This is dealt with by collision response, and will be discussed in the next section.

3. Collision response

There are a lot of algorithms for dealing with collision response, and they can be roughly divided into three categories:
  • projection-based methods, which adjust the location of the object directly to avoid collision;
  • impulse-based methods, which change the velocity (first derivative of the location) of the object in order to avoid collision;
  • penalty-based methods, which change the acceleration (second derivative of the location) of the object in order to avoid collision.
 We will propose a projection-based method, inspired by the sliding principle proposed in http://www.peroxide.dk/papers/collision/collision.pdf. Assume we have 2 objects \(M_1, M_2\) again, for which, using the algorithm above, the part of the movement is calculated that does not cause a collision, and the part is calculated that does. This part is represented by respectively \(M_1 * tBestSoFar\) and \(M_1 * (1.0 - tBestSoFar)\). It is only the second part we're concerned with here; the first part can be executed without worries.

So for both objects, we now define the illegal (impossible) part of the move vector as follows:

$$v_i = M_i * (1.0 - tBestSoFar)$$

This vector is illustrated in the figure below:

The idea is to have the objects "slide" besodes each other without colliding, so that they can pass each other. This can be compared to when you are walking, and someone is heading your way in the opposite direction. To avoid collision, one of you moves a bit to the left, while the other moves a bit to the right. In order to calculate the improved and safe move vectors \(v_1',v_2'\) from \(v_1, v_2\), we need the tangent of the spheres at the point where they collide. The tangent is always the same when two spheres collide at one point, and is perpendicular to the vector from one center to the other:

$$d = p2 - p1$$

$$tangent = [d.y, -d.x]$$

The tangent should be normalized:

$$tangent = \frac{tangent}{ \left\| tangent \right\|}$$

We now need to compute which direction we want to slide to. If the move vector leans more to the right of \(d\), the new movement should slide to the right around the other object. This is achieved by calculating the projection of \(v_i\) onto the tangent:

\[u_1 = v_1.x * tangent.x + v_1.y * tangent.y\]
\[u_2 = v_2.x * tangent.x + v_2.y * tangent.y\]

If \(u_i\) is positive, this means we are trying to move in the direction of the tangent vector. If it is negative, we are trying to move in the opposite direction. The sign of \(u_1\) can thus be used to determine in which direction to "slide".

Putting this together results in the following code:

// get the remaining part of the move vector that is illegal
// this is V1 and V2 in the figure
BM1 = (M1 * (1.0 - tBestSoFar));
BM2 = (M2 * (1.0 - tBestSoFar));

// get the tangent in normalized form
d = (L1+SM1) - (L2+SM2);
tangent.x = d.y;
tangent.y = -d.x;

// length of the remaining unsafe move vector
double d1 = BM1.length();
double d2 = BM2.length();

// use the projected version to determine the direction in which to slide
double u1 = BM1.x*tangent.x + BM1.y*tangent.y;
double u2 = BM2.x*tangent.x + BM2.y*tangent.y;

// depending on the sign, we move in a given direction
// if our move vector is perpendicular with d, we move in opposite directions for each object
if (u1 < -EPS) SM1 += -tangent * d1;
else SM1 += tangent * d1;
if (u2 < EPS) SM2 += -tangent * d2;
else SM2 += tangent * d2;

Note the EPS in the last lines. This is used to avoid the case where two objects are headed straight at each other, and both turn into the same direction. This is the case when u1=u2=0. To avoid this issue, one object will prefer moving to the left, while the other will prefer moving to the right. To take into account precision roundoff errors, EPS is used. EPS should be a very small number, close to double precision. Something like 1e-8 should do.

4. Wall collision

In a tile-based world, objects often also encounter straight walls defined as lines, for example when a tile is blocked. The code above can easily be adapted to work with lines as well, allowing spheres that collide with walls to gracefully slide along them. In the case of walls, the tangent should be parallel to the wall and the rest of the code remains the same. The collision check is also straight-forward.

The following site explains the collision check between a sphere and a arbitrarily oriented line very well:

If you only need straight lines (on the border of tiles), the collision check is much simpler, and just comes down to checking the horizontal/vertical distance between the line and the sphere center, and seeing if it is larger than the radius.

4. Conclusion

The algorithm presented in this article will have spherical objects gracefully slide their way through a tile-based world. When they collide against each other, they will attempt to slide along each other, avoiding collision alltogether. I hope this guide will be useful for anyone who is developing a 2D game and needs a robust collision detection routine!

All feedback is of course welcome.

vrijdag 24 juni 2011

Dungeon Builder: third makeover & digging

As you might have noticed, the previous posts about Dungeon Builder followed quite quickly after each other. This is because I was writing a report of the first month of development over the course of a week, trying to catch up my blog with the actual development status of the game. Right now we're at this point; the screenshot at the bottom of this post shows the game in its current state.

After the second overhaul, I started working on the digging component of the game: the part where you expand your dungeon by digging more rooms, in order to improve your defense. However, I quickly noticed that the room-centric setup was much too limiting for this. The original engine was built around rooms, and you either had to dig rooms in one piece, or combine two rooms into one bigger room. This can be seen from the previous screenshots, where there are obvious rooms in a grid layout. This did not give enough freedom to the player, so I decided in another major overhaul.

I changed the engine into a more DK-style grid, in which you dig out squares of dirt to build rooms of any shape you want. It took something like 5 days to complete the overhaul, and when it was finished, I quickly realized I made the right call: this was so much better. But this made pathfinding a much more difficult task, so it took me a while to get the heroes and monsters to find their way to each other again.

I also added a brown color palette to make it look more like earth you're digging in, and I changed some of the game mechanics as well. For example, parties of heroes now enter the dungeon about every +- 30 secs, and you better be prepared by then. Previously, you could choose at which point the invaders came by clicking a button when you were ready.

Here's a screenshot of the current state of the game:

The playable area on this map is a circle. Dark brown means that you can't dig through. The light brown areas are rooms. Several imps (pink) and one skeleton (blue) are fighting a knight (cyan) at the bottom. The yellow areas indicate squares the hero hasn't explored yet. When the knight has won the battle, he will head out for one of the yellow squares to explore the dungeon further. Eventually, he will stumble upon the second line of defense at the top right, and will have to fight them too to get to the treasure. The 50's around the dungeon indicate that I am in build mode, and can dig out additional squares for the price of 50 gold.

Dungeon Builder: cistron switch

So I ended up with a lot of objects in the dungeon that needed to interact with each other on a neutral basis (ie no regulating object that takes care of communication - it's cumbersome). I again turned to Cistron, everyone's (well mainly my) favourite component-based architecture! I had to do a lot of recoding to fit the entire game into the Cistron system, but it was totally worth the wait: the final code was much simpler than the original prototype version.

But because of the switch, I have surpassed the time you usually take to prototype, so I guess I'm out of the prototype phase now :). Now that Cistron was in place, it became very easy to set up complex communications between different objects in the dungeon. For example, I experimented with heroes attacking each other once they realize one of them is carrying my treasure back to town, in order to capture it for himself. This resulted in quite amusing bloodbaths of tens of heroes bashing away at each other until only one survived, but it didn't add much to the gameplay, so I removed it (for now).

Because I didn't have any graphics at all, I was getting kind of annoyed playing the game myself. So I took it upon myself to spend a day or so building a somewhat attractive GUI to compensate for the total lack of interesting in-game graphics. Then it took another week to actually implement all the GUI interfaces (menu's, saving, loading, etc) until I finally got back to working on the actual game. Damn, GUI's are so much boring, boring work :(.

Either way, this is what the game looks like after the Cistron overhaul and the GUI added:

You have a hero (cyan) at the bottom fighting some imps (pink) stationed at different rooms. The imps are ranged creatures, so they shoot "fireballs" (red things) at the hero, resulting in some damage. The hero needs to get in close range to attack the imps so he's moving. When he dispatches of the imps, he will go for the treasure (gold) on top and head back to the exit.

Next up: digging!

dinsdag 21 juni 2011

Dungeon Builder: prototype

I chose C++ with SDL for the project. SDL seemed ideal to create a 2D, isometric/topdown game. C++ is my language of choice for pretty much everything and I have a HUGE library of classes and external libraries that I can immediately employ to get going quickly. I also chose not to bother with graphics, and go for abstract shapes, so I focus on the gameplay. Graphics can be added later.

The first focus was on getting a dungeon structure up, and being able to summon creatures. So after about a week, I had this:

A dungeon with rooms, treasure at the end, some imps (pink) that could be placed and a hero advancing through the dungeon. At this point, I was getting in trouble with my quick-and-dirty prototype implementation, because I needed complex interactions between creatures, heroes, projectiles thrown by ranged creatures, the dungeon itself and items on the ground. So I once again turned to my old workhorse: Cistron. Apparently I always end up using this framework that I developed a couple of years ago in pretty much every project I begin on. It's just such an incredibly natural way to model a world with different objects that interact with each other that I have a tough time imagining how to do it otherwise nowadays. My next post will deal with the transition to Cistron.

Dungeon Builder: gameplay idea

About a month ago, I came up with a new game idea that I thought was worth checking out. One of the most popular genres nowadays is Tower Defense. This genre, originating from Starcraft custom maps, became wildly popular in recent years because of games such as Desktop Tower Defense and Plants vs Zombies. The good Tower defense games are a lot of fun for casual and hardcore gamers alike, but there are some things that frustrate me about the genre.
  • There is no persistence to your carefully constructed maze. Usually, the games are split up into levels, and you start from scratch each time, starting with the crappy turrets and building up to the awesome ones.
  • Turrets are in themselves quite boring and stupid: they don't move, they don't think, they just shoot.
  • The opponents are equally stupid: they walk on a pre-defined path to their certain doom.
The idea for my game, now temporarily given the uninspired title "Dungeon Builder" until I can find something more awesome, is a mix between Dungeon Keeper and Tower Defense. The basic idea is that you are the manager of an underground dungeon, which you can improve by digging.

The goal is to survive increasingly strong waves of heroes that attempt to raid your dungeon and steal away your treasure. Heroes will come in parties, and will behave pretty much like a player would in a dungeon crawler. They explore the dungeon maze you've built, kill creatures on the way, and try to get to the treasure.

In order to defend your treasure, you will have to summon creatures and place them strategically as your line of defense. Additionally, each creature has RPG stats that determine its role in combat, and an important part of the game is to position your defenses in such a way as to be prepared for the incoming party as optimally as possible. Place a tank creature at a choke point, with several ranged damage dealers behind it, and watch as heroes attempt to break your defenses with their own tactics.

This all happens in a persistent way. All throughout a campaign (which compares to RTS campaigns), you keep your dungeon. There's no levels to walk through. This makes you feel connected to your construction, as you are stuck with it for a long time. Because hero parties get stronger continually, you will also have to improve your defenses by summoning more creatures, relocating important structures, increasing your dungeon maze, etc.

This basic idea seemed quite appealing to me, so I set out to write a quick prototype for it.