The prototyping process news - Kravall

The core mechanic in Kravall 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(n²), 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.