Pathfinding

Testbed Author: Elia Morling, shailejron AT tildruin.com
Website: http://www.tildruin.com

For a movement control scheme, it's important for characters to not walk through solids. In a first person control scheme, this is done in a direct frame-by-frame way using collision detection. For 3rd person games with a point-and-click control scheme, movement is handled in a different way. When the user clicks a target location, a full path from the current location to the target location is calculated, and then the character moves step by step along that path unless a new target location is set.

The example above is a type of pathfinding called a-star. The idea is that there is an underlying grid laid out on the ground plane. Squares are marked as on or off limits. When the player clicks on a square, the player character calculates a path from the current position to the clicked position.

An added twist of a-star is that there is a "cost" associated with each potential path. This means that if there is more than one valid path, the costs can be compared to find the best path. This allows us to set a cost for each square rather then just setting each square as true/false for its passability. For example, road square can have a lower cost than default dirt squares. This gives nice results where characters will have a subtle preferences for roads versus a slightly shorter path that goes off-road.