What is pathfinding?

Pathfinding is figuring out how to get from point A to point B.

 Pathfinding is an essential part of video game development.


Example: When you click your mouse to move. Behind the scenes the game needs to figure out an appropriate path to follow to get you from where you stand to where you clicked.

example of point and click, mouse click pathfinding demo, simple example of pathfinding in a foo game
The pathfinding needs to be smart enough to avoid obstacles like cliffs and lava.

You might have heard of A* pathfinding. A* (Astar) is the most common type of pathfinding for game development as of 2019 and has been for years.


The two pathfinding methods in a nutshell:

Example of what Astar* Pathfinding Is, simple example of a* pathfinding used in game dev
A* is a line.
Example of what Flow Field Pathfinding Is, simple example of flow field pathfinding used in game dev
Flow Field is a river.

Calculating a flow field is slow, roughly 3x slower than A*.

But, multiple units can use the same flow field.


Optimizing a Flow Field Pathfinder

Combining the two pathfinding methods creates a system that is performance minded.

Imagine looking down on a game level.

simple abstract game map
The Map
100x100 Grid of Foo Game Level Map
100 sectors on the map (10×10)
Extremely basic example of A* pathfinding used in game development
Use A* to find a path from A to B
Explanation of sector selection, flow field pathfinding example image
That A* path is used to narrow down the sectors used in the flow field
generating flow field pathfinding example image, explanation of flow field pathfinding, beginner tutorial for flow field pathfinding
Calculate the flow field

Running A* pathfinding before calculating a flow field identifies the sectors needed for the path. In this example it reduced the flow field calculations by 85%. Optimizations like this will drastically boost a video game’s performance.


Conclusion

A flow field provides fluid movement for large groups.

Gif of Flow Field Pathfinding, Example of Flow Field Pathfinder, Game Development Movement AI Logic
A simple demonstration of the flow field pathfinding used in ATTRM.gg.

ATTRM.gg has officially licensed a top-notch flow field pathfinder from Glenn Korver. Glenn wrote a detailed thesis that helped me better understand flow field pathfinding. Thanks Glenn.

Share this page: