Collision detection systems for RTS games

From observing the unit movement behavior of several real time strategy games it becomes apparent that there are two major collision detection systems, each with their own pros and cons.

Tile based collision detection system
With this system each unit sits in a discrete tile on the tilemap. Only one unit can occupy a tile at any one time. As a unit moves around the map, it moves from one tile to another. Before moving into the next tile, it checks to see if any other units already occupy this tile. If the tile is occupied, the unit recalculates its path, if not then it moves into the tile.

There are some great advantages to this implementation:
1) It is extremely simple to implement
2) It is a very stable system (no units will ever get stuck in one another etc)
3) It has little CPU and memory cost which scale well

The main disadvantage of this method is the rigid nature of the movement of units. It is very clear of the fact that units sit in discrete tiles and there is a lack of fluidity in their movement.

As an example, here is a youtube clip of Warcraft: Orcs & Humans which uses the tile based collision detection system:


Note the fixed movement at 45 degree angles (i.e. North, North-East, East etc) is particularly rigid-looking and not really suitable for modern RTS games.

Object based collision detection system
Each unit is modeled as a sphere, and each building as a box. Standard collision detection techniques which may been seen in other genres of computer games are used. At each frame of movement for each unit, collisions are checked for, and upon collision are moved appropriately.

The clear advantage of this system is that the units move very fluidly and with a natural motion. It also makes it easier to make troops walk and fight in formation, as they are not constrained to discrete tiles.

However, it is particularly difficult to implement effectively and with low CPU cost. The main problem is that each unit must check the positions of surrounding units and buildings to test for collisions. For large groups of units, the checks become greater in number, having a heavy impact on the CPU.

Path finding/following also becomes an issue as it becomes more difficult to avoid dynamically moving obstacles. This is discussed in this article on Gamasutra.

An example of a game using object-based collision would be Empires: Dawn of the modern world. A youtube clip below shows this in action:


You can note at the beginning of the clip that as the soldiers line up to shoot at the building, the units kind of 'bounce' off each other.

The solution for Warring States
At first I implemented an object-based collision detection system purely for aesthetic reasons. However I soon noticed the problems that are discussed above, particularly with object avoidance. Units tended to get stuck when they tried to navigate around large groups and it would take a lot of work to make the system work well enough to my satisfaction.

As I want to start focusing on the AI system, I've decided to revert to a tile based collision detection system. However I'm not restricting the movements of units to grid-based movement as seen in Warcraft.