Flow fields: share a destination without sharing one rigid path

Share the expensive destination query

When many units have the same destination, a flow field can replace repeated individual route searches with shared guidance. Each unit samples a direction near its current position, so displacement need not require constructing another complete path. The reusable result still belongs to a particular destination and movement model. Emerson describes a tiled implementation; Patel explains the underlying all-sources-to-one-goal search. [1][2]

Separate traversal cost, integration and direction

Keep the cost of entering or traversing terrain separate from the integrated cost of reaching the goal. In a discrete graph model, set D(goal) = 0 and solve D(x) = min(c(x,y) + D(y)) over legal outgoing edges. With nonnegative weights, a reverse Dijkstra search can build these distances. Traverse reversed edges while retaining their original forward costs.

Store an unreachable marker explicitly. Choose a legal outgoing direction using the same cost model; merely following the neighbor with the smallest stored distance is insufficient when edge costs differ.

Worked example: the closest remaining route is not always cheapest

At a junction, route A first costs 8 and then has a remaining cost of 1. Route B first costs 1 and then has a remaining cost of 4. Their totals are 8 + 1 = 9 and 1 + 4 = 5. The field should guide a unit toward B even though A's remaining distance is smaller.

Suppose 200 units share this destination and movement class. They may share the same completed field; this does not imply that their collision resolution or steering is shared or free. These illustrative costs and unit counts describe a design, not a measured speedup.

Build a field that can be inspected

Start with a small map containing a wall, a costly strip and an unreachable pocket. Draw traversal costs, integrated values and chosen directions separately. Follow the arrows from each reachable cell and verify arrival without cycles. Check that diagonal guidance respects the same corner rules used to generate distances.

Key cached fields by goal, movement class and relevant terrain version. Rebuild affected data when a bridge disappears or a traversal permission changes. Publish completed field generations together, so units never sample partially updated distances and directions. Test transitions across tile boundaries and units entering from unexpected positions.

Budget sharing and physical execution separately

Many distinct goals or movement classes reduce reuse and multiply cached data. Coarse cells can conceal narrow passages, while interpolated vectors near walls can point through obstacles. A field supplies route guidance; body clearance, separation, bottleneck traffic and destination occupancy still need explicit treatment. Profile field construction, cache churn, sampling and local motion separately before deciding how much crowd movement the shared field actually saves.

Sources

• [1] Crowd Pathfinding and Steering Using Flow Field Tiles — Elijah Emerson, Game AI Pro.
• [2] Flow Field Pathfinding for Tower Defense — Amit Patel, Red Blob Games.