Finding the Correct Path (or is it?)

Just trying pathing around me!

Ah Pathfinder. It has been around for awhile now, and it is absolutely one of the best things around. There is nothing more interesting than having your Paladin deal 4d6 weapon die to undead and having them die on impact. There was even this one time when our group wen--.... wait, you mean mean PathFINDING? Oh, well I guess we can talk about that, too.

Pathfinding involves techniques and algorithms that are used to model AI characters in gaming. Often times we want our autonomous characters to move on their own Pathfinding utilizes a combination of steering behaviors and weighted movement costs to determine the best appropriate path for a character to move from points A and B.

An example of a fleeing mechanic.

What are steering behaviors? Steering behaviors influence the movement patterns used by an AI. For example, are your AI characters going to march back and forth? This would be an example of a wandering behavior. A seek behavior would cause an entity to see toward a specific target (usually the player) or location (say, a thief moving toward a treasure chest). And if the character was running away from a location or another entity they it would use (you guessed it!) the flee behavior.


Weighted movement can be associated with the cost for a character to move. Once we know how a character will act (due to our steering behaviors), it must choose an appropriate path. However,  obstacles will always impede movement: this includes traveling along a straight road. In order for an entity to move, they must give up something in exchange, whether it be energy, movement points, or in the case of many 3D games, time. Lets use the following image as an example:

Blue equals Good Movements. All the blue!

Our player controlled character (designated by the middle character, next to the unique model that actually has hair, true to Final Fantasy games) has a certain amount of movement points available. In this case, she has 4. The blue squares show all the valid spaces that the unit can move to. Note that in this case, "move to" means in the game "end your turn". The unit can move through friendly units, but cannot end its turn there. The same goes for if the character wanted to move forward: While they can move 4 squares, they cannot stop in the same space as the Chocobo rider (There isn't enough space as it is for them!). Each space costs 1 movement point for our unit: the weighted movement is 1. Also in the picture are rivers. While the character can move to the left, they do not have the movement points to cross the river, because the river has a higher movement cost to move through (in this case, it costs 2 movement points). Different paths can contain different values for pathing. Some may require more effort and resources than others.

Once we figure out which way we are going, and how much each direction will take use, the unit will move based on its pathfinding algorithm. The two most common algorithms are Dijkstra's and A* (pronounced "A-star"). Dijkstra's finds the "best" path to ALL the valid paths for a unit-- our picture from Final Fantasy Tactics Advanced displays this perfectly. However, some games won't be limited by movement costs, such as an open world first person shooter (excluding the game world's boundaries). In these situations, finding all the valid pathing for an autonomous character would take a lot of processing power and therefore time, in a scenario where stopping to determine movement could be deadly (for the AI character, that is).

Most gaming engines will instead use the A* method, a modified, complex version of Dijkstra's algorithm. With A*, a heuristic model is used to determine and estimates the total distance to our goal. Once it finds a valid path to the goal, it stops searching for other paths. "heuristic" in this case means to "guess", and get "close enough" to the target goal without overshooting it- Just like we learned from good old Bob Barker. Overshooting our goal too much can cause our algorithms to incorrectly eliminate an otherwise "OK" path!

And remember kids, spade and neuter
your bad coding habits!