Unity RTS – Part 5 – Pathfinding

The most common algorithm used in RTS pathfinding is A*. This algorithm traverses lists of nodes in a specific order to reduce the number of nodes processed while ensuring the fastest path is taken, and requires very little preprocessing of the map data for a trivial implementation. Unity RTS is designed to use this same concept, but combined with flow fields to allow more natural movements (removing the grid-aligned movements in unprocessed A*).

Firstly, a map is created with a value for each terrain cell, which represents if that cell is occupied or not. An int is used here, so that objects stacked on top of each other work correctly when added/removed. An A* pass then propagates the cost values throughout the terrain, but with a small change. When propagating a cost to each cell, the value used is the minimum of (from_cost + 1) or ((from_cost + neighbour_cost) / 2 + 1). This means costs can be propagated diagonally. The most extreme case, where neighbour is 0 and from is 1, this results in a value of 1.5 (quite close to the correct 1.41 when using cell distances).

Objects then move by calculating a movement direction from this persistent pathing query. First the interpolated value at the objects exact position is calculated (based on the 4 surrounding corners). Then for each corner, a desired direction is calculated and finally averaged to get the movement direction. A final piece of code tries to prevent directions from pointing into blocked areas, though is not necessary.

The complicated part here is calculating a desired direction from each corner. Each corner only knows about itself and the current object position, so this direction vector simply indicates how much closer or farther the object should be to the corner, based on the assumption that the cost increases by 1 for every unit distance. The ratio of delta cost and distance is first calculated, then the resulting vector is simply:

dir += deltaP * Mathf.Sign(ratio) / (1.0f – Mathf.Abs(ratio));

Where deltaP is the object position relative to the corner, ratio is the ratio of cost to distance. Of course, this can result in a division by zero; such a case indicates that the unit should move exactly toward the corner (ignoring cost calculation errors); cdir just needs to be very big in this case to overpower the directions from any other lesser corners.

A lot more goes into the pathfinding of a AAA RTS, you can read a little about how Starcraft handles their pathfinding here, or a little about Age of Empires pathfinding here.

When targeting the selected object, the blue lines display the direction each corner is suggesting that the object move in, the white is the resulting normalised sum of these directions. This project is the same as in Part 4 (I just took a long time to write it up), DownloadWebplayer.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s