0
\$\begingroup\$

I'm tinkering with an array-backed ECS in C++ along the lines of EnTT. Components are stored in a struct-of-array fashion where each component type lives in its own homogeneous contiguous memory block. I'm using arrays for now, but they could also be vectors. The "entity" itself is simply an index into these parallel arrays, which contain the appropriate components and a mask describing which are valid.

I've run into two cases where I would like some design advice:

Components containing arrays of data

Consider a physics component that contains one or many shapes representing the collision bounds of an entity. These shapes could be of different types (circle, polygon) with different sizes. The data for these shapes is in the order of dozens of bytes, at most. In this situation, would you recommend:

1) In the physics component for each entity, use a fixed-sized array of the maximum possible shape count containing an std::variant for each kind of shape with no indirection. This will induce some fragmentation for both the space between individual variants, and any unused space at the end of the array.

2) Do as in 1, but use a heap-allocated vector for storage rather than a fixed sized array in-place in the component itself. This will still create fragmentation between each variant type within the vector's data block, but will remove fragmentation within the component that was caused by unused pre-allocated space. This option creates a level of indirection (and another cache miss opportunity), but fragments memory less overall.

3) Do as in 2, but create separate vectors for each shape type to avoid fragmentation caused by sequences of differently-sized variants. This will waste some space in the component if a given shape type is unused.

4) Store all collider shapes, grouped by type, somewhere in the physics system itself (using something like Boost's poly_collection). In the physics component for each entity, store keys to these shapes in a fixed size array of the maximum number of possible shapes for an entity. This will induce a small amount of fragmentation at the end of the key array, but the keys themselves will only be a few bytes each.

Components containing heterogeneous data

A more pathological case. Consider a networking system that is sending and receiving containers of state data for objects. A core system is responsible for encoding, transmitting, receiving, and decoding this data into usable state information. However, many other systems will want to read this data once decoded (so as to update position, orientation, health, and so on). A container for a vehicle contains different information than a container for a bipedal character, such that we would have a biped_container and vehicle_container and so on. How would you store such a container on an entity? So far I've considered:

1) As in the physics example, storing each container type in a poly_collection within the network system and storing only a key within a component on the entity. This requires any system that wants to read an entity's network state to also have a handle to the network system itself. I'd like to avoid cross-system dependencies, and so this is less than ideal.

2) Heavy use of std::variant to store the container in-place in a component on the entity itself. This wastes a considerable amount of space on smaller container types (in the order of hundreds of bytes per entity*), and requires a lot of templating on nearly every part of the code involved. I am trying to modularize so that the network system does not know what all the possible container types are, it just uses variadic templates.

3) Storing a std::unique_ptr within the component for the entity, and accessing the data either through use of std::variant or virtual function calls and static_cast where needed. This creates a level of indirection, and another opportunity for cache misses.

4) Creating a different component for each container type, or a different container for each component type. This seems wasteful of memory within the ECS unless I begin using some sort of sparse array/map system for them. It also doesn't seem as though I'd gain much cache coherence here. The latter option (container for each component type) also sounds wildly complicated and error prone.

This case is what I'm really at a loss for what to do, and I would love to hear suggestions on how best to handle this situation.


* - So much space is wasted because we don't store a single container per entity, but rather a fixed-size rolling history window of past containers used to delta-encode state sent over the network.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.