It is several years into the future. Technology has advanced, bringing with it several enhancements to the human body: robot prosthetics and nanotechnology have given people the power to perform better, be superior and live longer. Obviously, this comes at a price – a high one – increasing the gap between the rich and the poor. The less fortunate were banished to the lower levels of the city, with the prosperous living the high life in the upper districts.
You receive word that a riot has started in the lower districts. The poor want something, again, and you know the rioters are going to use all means possible to achieve it. Hopefully, you can lead the rioters through their demonstration without it getting out of hand. It would be very unfortunate if you had to use lethal force…
Kravall is a real-time strategy game which is all about controlling flow. Using advanced technologies such as potential fields and GPGPU computations the player takes on the role of Chief of Police trying to control a large amount of rioters with a much smaller number of police.
As a player, you get to choose from a selection of missions, each with their own objectives. It could be something as simple as escorting a group of rioters from point A to B, making sure they don’t stray away from the path, to more advanced scenarios where you need to disband a group of rioters, arrest important people or make sure two different groups of rioters do not meet and start fighting.
The banner of this game page is a derivative of "A masked rioter", "Riot police" & "Do not give up!" by Ivan Bandura, used under CC BY. "Riot Game Blog Banner" is licensed under CC BY by Lukas Orsvärn.
Since before we begun development of Kravall we were aware that the game we were going to develop was going to be resource intensive, primarily due to the AI systems that would rely heavily on calculation intensive algorithms. One way we mitigate this is by moving some of heaviest algorithms over to the GPU, another is by trying to have a performance focused design philosophy for the primary code-paths of the games reoccurring (per frame) calculations.
In the architecture of Kravall's engine we are following a design philosophy called DOD (Data Oriented Design). The primary idea of this philosophy is to try to minimize memory access delays by designing the program to have memory access patterns that maximize the utilization of the CPU cache. The primary way this is achieved is by trying to allocate memory linearly and tightly packed, trying to have the program access it linearly, minimizing cache misses and using modern processors automatic memory pre-fetching mechanisms.
A practical implementation of this philosophy and the primary way this thinking is realized is in the implementation of our Entity-Component Based Framework heavily inspired by the Artemis Entity System Framework.
The Entity Component Framework is the central core for all logic driving the game. An Entity is a generic object in the world, which consist of one or many instances of different components which, in turn, contain a set of data, this setup of components will be the identity of the entity and define how it will be treated by the game engine. As an example: in the game engine there might be a WorldPositionComponent and a VelocityComponent. If we instance (create) a new entity and give it an instance each of the aforementioned components the game engine will assume, simply due to the topology of the entity, that the velocity values contained in the VelocityComponent should be applied to the WorldPositionComponents world position data each frame making the entity move in the world space (which is then visualized when the rendering system uses the WorldPositionComponent and unmentioned GraphicsComponent). This form of programming allows for some interesting and dynamic combinations of components if the components are well designed (e.g. add a sound component to the entity and it will give off a sound from its position).
The manipulation of the components occurs in what we call Systems. Systems manipulate data and moves it between the components within (and sometimes between) entities. The systems define an Aspect, a list, of components that it is interested in, essentially subscribing to all entities that match the Aspect and perform its specific calculation on them in sequential order. For the previous example we would have defined a system which performs the VelocityComponent to WorldPositionComponent calculation, that are run each frame, moving the entity.
The reason why an Entity-Component Based Framework can work so well in combination with Data Oriented Design is the assumption that one component instance will usually be accessed and calculated close to (in time) other component instances of the same type, this assumption comes from the way systems are designed: only manipulating a single setup of components with some specific transformation. The way we use this information is by allocating all the component instances data sequentially in large memory blocks, one block for each type of component.
Another boost comes from running the same code block in quick succession, not moving to far around in the programs execution memory, which can also result in cache misses if the program is exceedingly large. In contrast, large Object Oriented Designs can do very poorly when the execution chains becomes large and inheritance chains are deep, possibly causing cache misses that add many unnecessary CPU cycles, waiting for memory.
In practice we allocate a large block of data for each type of component at the start of the program (reallocating it when we run out of memory), and then assign parts of these memory blocks to entities as they are created and given a component setup, minimizing allocation run times in the game engine. As a result, creating, destroying and reclaiming entities and component data is without any system memory allocation. Depending on the creation and destruction patterns of entities these memory blocks might become fragmented and the execution order might suffer which can create a performance loss, the effect of this problem and scope in common usage patterns is unknown and is therefore not yet addressed by our implementation but is of interest in our future work.
Max Danielsson (Technical Lead)
Latest tweets from @ekswaised
@_Sjonsson We are studying at Blekinge Tekniska Högskola, Karlskona
Mar 13 2014, 7:29am
@_Sjonsson Last two days of development (for the course we're developing the game for). Then we'll see if we get to continue on it :)
Mar 13 2014, 6:55am
If you haven't already, check us out on the Swedish Game Awards web page. If you like what you see, give us a like! T.co
Mar 13 2014, 5:32am