Flow Field Pathfinding

Created: 2020-10-29T21:30:44-05:00

Return to the Index

Cost field: a field of prices to enter a particular cell.
Integration field: holds information that "integrates" goal information against the cost field.
Flow field: a field where each cells point in the direction of the best next move from that cell.

Creating integration field

Set all fields to some maximum score.
Goal node has a score of zero.
Put the beginning node in the open list.
Djikstra algorithm occurs: Traverse open list and check each neighbor; each neighbor gets cost of current cell plus cost field to enter that cell. If the score is lower then update that cell and push it back to open list.

Flow field

Iterate each cell of the integration field and find which direction goes towards a lower score.

Performance

Creating flow fields is expensive on large graphs because Djikstra is slow.
Planetary Annihilation found that splitting maps in to multiple flow fields, and using a faster algorithm (A*) to determine which fields to pass through, works.

References

Leif Erkenbrach