You can implement a sparse array that stores ranges of components. It's way heavier for storing/removal (you have to search into the range array, shift elements around), but access should be pretty fast.
I got one implemented in my Java ECS framework: https://github.com/dustContributor/dustArtemis/blob/entity-filter/src/com/artemis/CompactComponentHandler.java
Thats a tightly packed sparse array. If you allocate components for entities 50, 51, 52, and 60, 61, 62, it will store all 6 components tightly in the same array, and store two used ranges from 50 to 53, and from 60 to 63. Then for access it searches the matching range for the entity, offsets by the id and reads. No space wasted.
Thanks i will check it!
A couple of comments/questions though, if i understood it right, in the array you have components of different types one after the other, grouped by entityid?
Wouldn't that be an issue for the cache, since the Systems, dealing only with some types, would end up loading components that shouldn't be processed?
Why some components are stored in the system and others aren't? (well that probably has to do with the different meanings that ECS has for different people)
I meant a different thing: components are all stored in systems, but when, lets say, updating the MovementSystem, NetworkComponents are not stored there, but in the NetworkSystem, so they have to somehow be passed to the NetworkSystem, in an way/order that matches the PositionComponent counterpart.
But, regarding the use of contiguous memory:
With a scene graph, components inside game objects, it's fairly possible: objects just need to be added in the flat array *after* the parent. When parsing the game objects, the updates will occur in the correct order, parents first, children later.
With a scene graph, components inside a flat array and game objects as IDs: components need to be added in the flat array close to a component with the same game object ID.
No scene graph: both methods are fairly easy without a scene graph, since there's no need to worry about the order of update.
To be honest, I don't see much difference in putting the logic of a component inside a method (in the component) and putting the logic in a system. If the logic was in the game objects, retrieving and modifying the components according with their specific needs, then I would see a difference.
But, if i understood it right, this go "against" the Systems part if an ECS.
The reason of having components separated by type in different containers and stored in systems, plus the logic be separated from data, is to avoid spaghetti code.
Then also it's a matter of performance: components would need to access different parts of memory (stored in various components), which are scattered around... while having systems storing the components, they can process them in bulk.
And it's also then easier to make the component processing concurrent.
The NetworkComponent should contain information about what variable (in this component or sibling component) the update will modify.
So if you want your NetworkComponent to change the variable "X" in the sibling TransformComponent, you could have a table containing the information of what to modify, maybe a list structures:
/* pseudo code */
structure {
Type VariableType; /* the type of the variable we will update */
String IncomingVariableName; /* "X" is the variable we will parse in the incoming data */
String PathToVariableToUpdate; /* that would be "./TransformComponent/X" */
}
I'm not sure what you mean here, but i might not have explained myself. With X and Y, i wasn't referring to PositionComponent coordinates, or even some generic field of a struct.. i meant indexes of the components inside their array, stored into their system.
If *I* was going to make a ECS, I would make that every game object has every component, but some components are just disabled. That would guarantee that the memory is contiguous, and you would have to parse everything just once per frame (no excess of lookups).
That would guarantee that components of different types are contiguous, but the update pattern of an ECS is to update components of the same type all together, so with your layout you would have to jump around in memory. The ECS idea is to loop components not entities.
Anyways, ECS (whatever definition of it) isn't a magic bullet, it has pitfalls, too. And sometimes doesn't solve real problems (write less code by reusing components, but at the same time write more code by writing more lookups and adding conditions whether the game object has a sibling of specific type or other?). On the other hand, some people argue that it makes easier to make composition with it.
And in fact my question is also half a critique to try to uncover the pitfalls, or the easy optimizations, where thinking about how to structure the code and data isn't a premature optimization.
I didn't have time to read all the replies but I went the way of allowing my entity to be a small struct.
struct Entity
{
std::uint64_t m_entity_name;
std::bitset<NumberOfComponents> m_component_list;
bool m_is_alive = true;
}
This way you can have multiple components, they just know the ID (and it can be 16/32/64bit whatever you need). I hash the string name, and in debug mode keep a list of hash->std::string for debug reasons. Then you know what each entity has component wise. My systems are updated in order, work is then multi-threaded as it should not depend on any other of the same data. That way it can get the info from previous systems that it depends upon.
If it interests you at all, I can write up a larger reply. I'll revisit this one later tonight or this weekend.
I'm not sure i follow you here; I wasn't particularly worried about how to associate entities and components on a debug or editor point of view, but how to solve the needs of algorithms/logic in the systems to work on multiple component types, in a way that cannot be independent from their association with the entity.
The most common solution I've seen for component lookup by entity is a hash-table with entity ID as the key and component index as the value. This level of indirection means that you can defragment (fill holes in the contiguity), sort into arbitrary orders, etc...
So you mean that for each component type there's a hash-table entityid->component index?
Wouldn't this again blow up the cache, given that keys and values in a hash-table are not that contiguous?
Or you actually meant something like
std::unordered_map<int, std::vector<Component>>
where the int key is the entity id and Component is the base class of all Components?
DoD says that you should view your game as a series of data transformation (input->process->output) and then restructure the data layouts and the code to minimise the amount of work that the machine actually has to do.
ECS says you should be a generic framework that will dictate the data layout and corresponding transformation pipeline for your whole game. Moreover it dictates that your pipeline be built around mutable records/objects.
You can use the common optimization mantras of DoD (think about how the machine actually works; cache is important) to optimise an ECS framework, but the two philosophies are fundamentally at odds with each other.
A DoD ECS would allow every entity, component and system to break the rules of the framework in order to reach their optimal design, instead of forcing a general design across the board... Which means you'd no longer be building an ECS framework but more of a collection of utilities that lets you perform ecs style tasks in situations where it is an optimal solution.
So you mean DOD and ECS are kind of working against each other?
What, i think, i have understood is that while ECS per se doesn't dictate that one should use DOD (i've forgot a capitalized O earlier :P), it makes it simpler to use it, because separating code and data and then putting data all together in systems kind of follows what DOD "asks".
Moreveover again, putting data in systems, so that it's contiguous etc, helps the cache.
What i'm trying to understand now is how much of DOD can be used in an ECS without hanging up myself with premature optimizations and architecture rigidity.
Sure the architecture won't be rigid as a normal inheritance based game, but deciding how to resolve the lookups means changing data structures and also the actual code that deals with the lookups.
Probably it cannot be avoided, but again i'm trying to understand if there's some "gotchas" i'm missing here or it really ends up being a case by case decision.