Collision Detection

Collision detection is a common problem both for computer games and my particular field of interest, artificial life. Although there is an obvious algorithm, simply checking each bot (object, creature, whatever) against every other bot will work this is slow when dealing with large numbers of bots. Other techniques are available but rather than picking one blindly there are some questions to be asked.

How many bots are there?
How often will this change and by how much?
How large is the playing area?
How does the area covered by bots compare to the unoccupied area?
Do the bots cluster in any particular patterns?

A number of techniques, including the obvious algorithm, are explained here. Also available are some speed comparisons and sample code for most of the algorithms. First a few words of warning -

Only collision detection is covered, collision resolution (what to do afterwards) is left to you.
The algorithm use radial collision checking in a non-wrap spaces but this can be modified in all cases.
The speed tests are reasonably fair but this does not mean they will perform in the same way of your computer or in your situation.
This is unlikely to be a comprehensive list of techniques - indeed if you know of any others then please let me know.

Obvious Algorithm

As mentioned above the most obvious way to detect collisions in a group of bots is to compare every bot against every other bot.

void collision(BotP bots, long number_bots)
{
  for (BotP p = bots + number_bots - 1; p > bots; p--)
    for (BotP q = p - 1; q >= bots; q--)
    {
      long dx = (p.x - q.x);
      long dy = (p.y - q.y);
      long dr = (p.r + q.r);
      
      if (dx * dx + dy * dy <= dr * dr)
        ; // necessary collision resolution
    }
}

Here the outer loop goes through the array of bots, the inner loop compares the current bot with those earlier in the array. Notice that the actual distance between each pair of bots is not calculated. A collision test can be performed on the square of the distance avoiding the need for a square root call.

Static Buckets

The previous algorithm has difficulties when working with large numbers of bots. Excessive numbers of unnecessary comparisons are made, two bots at opposite edges of the playing area need not be checked. To avoid this space is divided up into a number of buckets (regions) usually in a regular grid. Initially bots are placed in the appropriate starting bucket. If it moves across one of the buckets boundary lines it will be shifted into a neighbouring bucket. Collision detection is done in two stages -

Use obvious algorithm inside bucket.
If a bot's radius extends outside its bucket then check there as well.

Typically a bucket has four neighbours - north, south, east, and west - although those at the edge of the playing area may lack some of these.

void addBot(BucketP bucket, BotP bot)
{
  // attach bot to list
  bot.next = bucket.bots.next;
  bot.prev = bucket.bots;
  // attach dummy head to bot
  bucket.bots.next.prev = bot;
  bucket.bots.next = bot;
}

void subBot(BucketP, BotP bot)
{
  // detach dummy head from bot
  bot.next.prev = bot.prev;
  bot.prev.next = bot.next;
}

void collision(BotP bots, long number_bots)
{
  for (BotP p = bots + number_bots - 1; p >= bots; p--)
  {
    BucketP home = p.home;
    subBot(home, p);
    obviousCollision(home, p);
    addBot(home, p);
    
    if (home.north != null && home.top > p.y - p.r)
      obviousCollision(home.north, p);
    if (home.west != null && home.left > p.x - p.r)
      obviousCollision(home.west, p);
    if (home.south != null && home.bottom < p.y + p.r)
      obviousCollision(home.south, p);
    if (home.east != null && home.right < p.x + p.r)
      obviousCollision(home.east, p);
  }
}

Two elements are combined here to provide total collision detection, an array of bots and a list of neighbours. During initialisation a grid of buckets is laid out and neighbour relationships are stored. During each collision detection cycle a bot is first checked against its companions in the bucket. Then, only if the bot extends outside the bucket, need additional checks be made. Notice neighbouring buckets do not always exist in the non-wraparound space. To store bots within each bucket a circular dummy headed linked list is used which allows for fast insertion and removal.

Dynamic Buckets

Always having the same fixed grid is a limitation. In the beginning we may not know how many buckets to use. We do not want to use too few as this would lead to too many bots in each bucket and slow collision detection. Nor do we wish to use too many as this would be a waste. Whatever decision we make later it may turn out to be wrong.

Dynamic buckets uses a regular but modifiable grid. In the beginning there is only a single bucket. As this bucket is filled up with bots it splits into four smaller buckets. Whenever a bucket fills up it subdivides leading to a grid which is dense only where there are large numbers of bots and sparse elsewhere.

As bots move the density in an area will change and in response so will the number of buckets, either subdividing or coalescing as necessary. The collision detection cycle is identical to that of static buckets.

There is no sample code here because the difficulty in implementing this algorithm. It is a difficult algorithm to just write the algorithm because of the number of aspects which must be consider. Even with the work that has been completed it is suggested that these items will be needed -

Bucket tree structure.
Dummy headed linked list in each bucket.
Bots stored only in leaf buckets.
List of buckets to aid dynamic changes.
PushDown and PullUp methods to subdivide and coalesce buckets.
Up to date bucket neighbour links.

Closest Pair

Although buckets give good performance it has already been pointed out that picking the right number is difficult and dynamic allocation is difficult. The closest pair algorithm is my answer to this, I do not know if it is used by anyone other than myself. It was developed from an algorithm which find the closest pair of points amongst a group, hence its name.

This algorithm requires the array of bots to be sorted either by their x or y coordinates, here it is assumed the x coordinate has been chosen. Collision detection is a recursive function. Its return value is equal to the radius of the largest bot in the array. If only a single bot is specified in the call this bot's radius will be returned. For multiple bots it first divides the array of bots into two equal halves and for each half performs a recursive call. Having already checked each half for collision the only possible remaining collision will occur in a narrow strip where they join.

Here in the diagram the single large green bot on the right and only small blue bots on the left, these radii must be added together to give the width of the strip on each size. Even so this combined width is still small and only two bots need to be compared in the diagram. In the general case all relevant bots from the left must be compared with all relevant bots from the right using the obvious algorithm. Finally the larger of the two radii returned by the recursive calls is returned by the function.

long searchLeft(BotP* bots, long left, long right, long x)
{
  long i;
  
  for (i = right; bots[i].x >= x; i--)
    if (i == left)
      return left;
  return i + 1;
}

long searchRight(BotP* bots, long left, long right, long x)
{
  long i;
  
  for (i = left; bots[i].x <= x; i++)
    if (i == right)
      return right;
  return i - 1;
}

long collision(BotP* bots, long left, long right)
{
  if (left < right)
  {
    long h = (right - left) / 2 + left;
    long left_radius = collision(bots, left, h);
    long right_radius = collision(bots, h + 1, right);
    long radius = left_radius + right_radius;
    long l = searchLeft(bots, left, h, bots[h + 1].x - radius);
    long r = searchRight(bots, h + 1, right, bots[h].x + radius);
    for (long i = h + 1; i <= r; i++)
    {
      BotP p = bots[i];
      
      for (long j = l; j <= h; j++)
      {
        BotP q = bots[j];
        
        if (sqr(p.x - q.x) + sqr(p.y - q.y) < sqr(p.r + q.r))
          ; // necessary collision resolution
      }
    }        
    return max(left_radius, right_radius);
  }
  else
    return bots[left].r;
}

Performance for this algorithm is limited both by the recursive call itself and the sorting which must be done beforehand. For most sorting tasks quicksort is the best but not here. Quicksort ignores the behaviour of the bots. Given an already sorted list of bots when they are moved a small amount the resulting list is likely to still be mostly ordered. In such circumstances bubblesort often proves effective and indeed its results were better. However it seemed likely that many complete scans of the list were required to reorder just a few bots. To prevent this a recursive bubblesort was created which again gave a speed improvement. Even so time was wasted moving a bot place by place, surely it would be faster to transfer the erroneous bot directly to its correct position. This gave rise to a trial of both insertionsort and a recursive insertionsort, each performed well in certain circumstances.

Collision detection in this ordered environment can make assumptions about the positioning of the bots, i.e. one on the far left of the list cannot collide with one on the far right (ignoring wraparound). Because of this collision detection can be done in two subsections apart from that narrow joining strip. Finding which bots are within this strip is done with a linear search, probably faster than a binary search for small number of bots. Then for this small number of bots the obvious algorithm is used.

Speed Test

Each algorithm was tested three times with the same situation and varying the number of bots, the size of bots, and the size of playing area. A random distribution of bots was used (identical in each test) with random speeds. The test measured how many movement-collision detection cycles could be performed in 1 second using all of the computers resources (PowerPC 604 132MHz). Given the number and size of the bots the size of the playing area was manipulated to preserve a bot density of 0.6%, that is the percentage of the screen covered by bots. The chosen percentage gave a pretty cluttered appearance and collisions are frequent. Here is a graph which summarises the results of the test. On the y-axis the number of cycles achieved using a logarithmic scale and on the x-axis the number of bots, all bots have a radius of 16.

From left to right the algorithms are - obvious (yellow), 4 static buckets (dark blue), 9 static buckets (blue), 16 static buckets (light blue), quick-sorted closest pair (red), recursive bubble-sorted closest pair (dark purple), bubble-sorted closest pair (purple), recursive insertion-sorted closest pair (green), insertion-sorted closest pair (yellow-green).

What can be seen at a glance is that working with more bots takes longer, whatever algorithm is used. The second important point is that which algorithm is best is heavily dependent on the number of bots. Now some specific recommendations for each algorithm.

Obvious algorithm - because of its simplicity this algorithm performs very well for small numbers of bots, perhaps up to a few dozen, and is also easy to code. For larger simulations better performance can be found elsewhere. Its only remaining advantage in these situations is that there are no special cases, no matter how densely space or what patterns the bots take up, this algorithm has a predictable performance.

Static buckets - for small number of bots the additional overheads of managing buckets is not worthwhile. However when more than a few dozen bots are present its pays off and continues to do well even with very large numbers of bots. More buckets usually means faster performance although it also takes more memory. More buckets also means smaller buckets and increases the likelihood a bot will overlap the edges of the bucket. If bots are evenly distributed in the space then this is probably the best method but if bots tend to cluster then it may be that individual buckets become overloaded and collision detection costs escalate.

Dynamic buckets - was not implemented so here is a personal guess. Coding is difficult which stands against it. Because of the extra code it is likely to be slower than its cousin static buckets. Where this algorithm will work is when bots tend to cluster together or in certain areas of the playing area.

Closest pair - becomes worthwhile at about the same time as static buckets and becomes better for very large numbers of bots. The sorting algorithm is very important and as can be seen quicksort is almost always bad, even worse than the obvious algorithm. Different algorithms have different performance with different simulations, do some experiments before choosing. As a rough indication for large number of bots a recursive insertion sort is best. This algorithms weakness is bots clustering in the x-axis, an example is a bot firing shells (smaller bots) directly upwards. To limit this problem simply prevent the bot from shooting directly upwards, perturbing it by a few degrees is enough.

So in summary -

For small simulations use obvious algorithm.
For medium simulations use static buckets.
For very large simulations use closest pair.

For those who are interested in more detail here is the source code, visual tests in Java and speed tests in C++. Sorry but neither are well commented and code is not robust.

Further Thoughts

Static buckets is not optimal, for each pair of bots two collision checks are made. If this is changed a speed increase of 50% might be achieved. Dynamic buckets was not finished but it is certainly possible and could give great benefits in certain situations. Subdivision helped the obvious algorithm and similarly banding would help the closest pair algorithm. Splitting the playing area into a number of horizontal bands and each bot would be placed both in its local band and any others where collisions might theoretically occur.

All these algorithms assume a 2 dimensional playing are but use of the 3rd dimension is common now. The obvious algorithm works without change and bucketed systems can be easily extended to cope. Closest pair will continue to function but probably at a reduced speed. Introducing banding would help but hopefully a modification can be found to give better performance, perhaps involving additional sorting on the y and z axes.

Nearest neighbour calculations are closely associated with collision detection and all of these algorithms can be converted in some way for this purpose. Bucketing systems have a disadvantage here because a "nearest neighbour" might in fact be several buckets away.

Credits

Thanks to Professor A. C. Allision for giving that lecture on geometric algorithms which was the inspiration for the closest pair collision detection algorithm.