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.

Fog of war, building animation and gui interface

I've added a 'fog of war' effect to hide areas of the map that have not yet been explored by the player. A grey scale texture contains the data of which areas have been explored, and then this is fed into the terrain shader to darken the areas which are yet to be explored. I'm quite happy with the effect, although objects and trees tend to 'pop' in and I'd rather put a fading in effect as they become visible.

I've also modified the building animation, so a 'scaffold' model is erected first, then the building and then the scaffold descends again. This makes it easier to see where the building is being built, and the progress of its construction.

The last thing visible in this post is the GUI that I have started implementing. The selected units or building are displayed across the bottom of the screen, and their actions are available along the left side of the screen. The minimap is displayed on the bottom left side of the screen.

Below is a video to show the effects mentioned:

Two new youtube videos

I've uploaded two new youtube movies showing details of the game. The first shows a number of workers collecting gold and lumber and returning them back to the town center. The second video demonstrates the grass shader as it is too difficult to see in the first video due to the compression of the video.