Kravall Windows, Linux game

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)