# 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.

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.

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.

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.

# Prototyping

The core mechanic in Riot is crowd control. The crowd is made up of a large number of rioters and it is important they move in a way that feels realistic. To make this happen we are using something called potential fields. Simplified, it is like simulating magnets: the different influencing units, called agents, each have a charge that is either repulsive or attractive to other charges. With magnets the same type of charge is repulsive and an opposite charge is attractive, but in our software implementation, we have no such limits. For instance, the rioters each have the same type of charge, but we want them to try to stick together which means we want them to attract each other. Thus the rioters are attracted by the same charge. Potential fields also give us the freedom to implement any type of curve for the charges so that we can make the rioters repulsive very close to the center and attractive further away. This way we make the rioter agents avoid getting too close to each other while still trying to stay in a group.

Potential fields for each unit shown by green and red circles.

Potential fields is a new technique for us, making it hard to asses whether we can make it behave exactly the way we want: Enter prototyping! With prototyping we get to implement a technique to ensure it is what we want. As our development team consists of six programmers and only so many can be working on the core or graphics engine at any one time, whoever not working on those areas can work on the prototype thus maximizing the work done.

## Unity

For prototyping, Unity was chosen. It was the first time I ever used it, which initially meant a lot of learning what I could do. It was fairly straightforward though so I quickly got a good idea of how to do what I needed. Unity is by this experience a great tool for doing simple and even fairly complicated things quickly.

## The prototype

We rapidly got a working prototype showing much promise for potential fields. The first prototype was made for a pitch and had to be finished in a short amount of time, leaving it somewhat of a mess. After the pitch it was scrapped in favour of a new prototype with a structure that had a closer resemblance to what it would look like in our game engine. This, however, suffered from severe performance issues due to the way Unity is made and had to be abandoned by a third version more similar to the first version. However, as much code could be recycled, not much time was lost doing this.

Police (blue units) affecting a crowd of rioters (black units)

Potential fields is a very performance heavy technique, with a complexity of O(n2), of which we are very aware. The prototype gives us an excellent opportunity to try different optimisations and observe their effect on the behaviour of the algorithm. One optimisation we evaluated was to spread the potential field calculations over a number of frames. This gave the agents a weird behaviour that was hard to control. Thus, it is an optimisation deemed best to avoid, if we can help it.

## Pros and cons

There are several obvious advantages to prototyping. We get the chance to evaluate one or several possible options for creating the desired game mechanic, determining which suits us the best based on performance and behaviour. It offers an isolated environment for developing and measuring the algorithm and of course: that it can be started day 1, letting us get a lot of research and, if needed, tuning done while the game engine is still not developed enough to allow for implementation of the AI system.

As for drawbacks, an obvious one is the time it takes developing the prototype. In our case, this is not a very severe drawback as there is little else to be done at this point and as the research needs to be done anyway. Most of the knowledge obtained during the prototyping phase will be useful when implementing it in the game engine later.

## Moving forward

None of the code can be used directly, as Unity uses C# and our game engine uses C++. However, the concept and much of the algorithms can be translated directly. No matter how much tuning can be done in the prototype, it will still be needed for the game. This means it is of no use spending too much time on tuning during the prototype.

The chosen technique is very expensive so optimisations are needed. Performing the calculations over several frames was a suboptimal solution so other options need to be explored. Potential field calculations are in their nature very well suited for parallelisation, so both CPU- and GPU parallelisation will be evaluated.

## Media

The first video shows off potential fields, the main focus of our prototype. The second video shows off something we’ve started to explore using the prototype in the last few days, flow fields, which we will hopefully be able to talk about more in the future.