Flowfield pathfinding/ Continuum Crowds

In Real-Time Strategy(RTS) games, path-finding is the fundamental issue that needs to be tackled by artificial-intelligence(AI). The game would be hardly playable without it or head-scratching if the search algorithm is buggy. The issue has long been investigated many years ago and one of the present-day standard solution is the A*(A-star) search algorithm, which is used to find the least-cost path from point A to point B, out of many possible routes.

Recently, Gas Powered Games' Chris Taylor highlighted their state of the art path-finding system, Flowfield, used in their latest release, Supreme Commander 2.



The demonstration is fascinating and shows the difference between their new Flowfield system and tradition A* algorithm in action. We can see that the new system is good at keeping the formation of a large group of units when they move across other moving obstacles, while the A* system would be a bit chaotic in similar situations.

It is good for players to know that developers are bringing new technologies onto the table to improve the gaming experience, and sometimes we are interested to know how. Taylor mentioned that their research is based on the University of Washington's Crowd Continuum Research. The Continuum Crowds is a real-time crowd modeling research that simulates the smooth flow motion of large crowds.



Instead of treating every unit as an individual object to search their own path as in A*, the continuum approach analyses the map with dynamic obstacles to create a vector field for the whole group of units, where they are treated as particles on the field. Discomfort is added around obstacles so that units can flow around the areas of high congestion. As the continuum approach plans the behavior for everyone at once, the simulation can be faster and collision are much reduced.

However, this advantage is limited to the situation when the group is having common goals and it is assumed that every individual already knows the dynamic properties of the environment.