All posts by John Heiding

Pathfinding using flowfields

A flowfield is a form of data structure used to save pathfinding calculations over time. ThisĀ  is useful when you are dealing with a lot of units as most pathfinding algorithms are quite expensive. In our case we plan to have about 1000 units in play at one time, which means that calculation time per unit is vital for performance.

Flowfield Algorithm

The algorithm works by generating a node tree for the entire map and then making one instance of it for each separate destination. The instance is usually calculated with Dijkstra’s algorithm down to each node. After this, whenever a units wants to go towards their goal they simply sample their current position from the node tree. This means that flowfields trades speed for memory. Depending on the specific implementation and sampling routine, the worst case scenario in terms of cycles is in the regions of a few cache-misses per unit. The picture above shows blue lines from the center of the node towards the entry point in the next one, walking in the respective direction gets you to the target in the top.

We’ve tested two types of implementations, grid base and node based. The grid-based tree is pretty self explanatory and is what we used in the prototype. The node based solution is using a number of quads in order to build an arbitrary structure of traversable surface with a bunch of tables storing information on which nodes connects to which, sizes and so on. While a grid based solution benefits from an easier sampling solution and a good relationship to granularity for providing better behaviour, it cost proportionally more memory. A node based algorithm might need some additional functionality to provide a more normal behaviour, if a unit is not just to walking to the centre of the next node and so on. We refer to this as ‘sampling’ and is covered in a bit more detail below.

picture2

Our sampling algorithm builds on two cases. One, in green, when the units position is projected onto the exit edge of the current node. If the projection is on the edge (between the red dotted lines) the unit will approach the exit edge of the next node. The second case, in red, is when the units projection is outside the edge. In this situation the unit will move towards a point on the exiting edge of the current node. This will remove some of the sliding along the walls and solve most of the special cases in the corners. In yellow is the current observed movement when traversing a large cross-way, including a small turn radius.

The current implementation takes <0.1ms to assign directions for 1000 units, using 650 nodes, and requires about 0.4ms to generate a new instance. What might be interesting to note here is that the engine implementation covers a map that is a lot larger than the prototype, which was using a grid solution with 625 nodes. More so, there is most likely a trend in performance in respect to that a grid based solution might reach worst case scenario for cache utilization a lot faster that the node based one, especially for groups that spend a lot of time gathered together.

While the above numbers strongly speak for an advantage for the node solution, the problem with sampling remains. The current implementation uses some positioning checks and assigns a direction accordingly.

Further more, we are also using the node tree together with A* to handle individual pathfinding for the much fewer police units, so that they can chase separate units and stay in formation, etc.

Nice looking scenario.

Future improvement of our algorithm would involve using splines to smooth out the path along with ray-casts to find directly traversable paths. We are currently implementing a system for blocking certain nodes, which might be suitable for a future abstraction that would allow things like buildings collapsing over streets etc.: runtime alterations of the mesh.