Is there a better data structure for storing components and their associated entities?

user_962155 0
Viewed 195

I'm writing a little Entity Component System (ECS) in Javascript (Typescript specifically) and it currently works, but I was wondering if it could be more efficient under the hood. The way an ECS works is that entities are basically just bags of components. So, a player entity might have a HealthComponent, PositionComponent, SpriteComponent, etc. Then you can create a RenderingSystem that queries all entities with a PositionComponent and a SpriteComponent and then it renders them. Like this:

for (let entity of scene.query(CT.Position, CT.Sprite) {
  // draw entity
}

To make this efficient when querying, rather than iterating through every entity in the scene to see if it has a Position component and a Sprite component every time, what we instead do is that cache it after the first query call and then keep it updated, so every query call can just return us the list of entities, rather than iterating through the entire list of all entities first each time.

So, as an example, the cache might look like this:

{ "6,1,20" => Map(1) }
{ "2,3,1,6" => Map(1) }
{ "2,3" => Map(31) }
{ "9" => Map(5) }
{ "2,8" => Map(5) }
{ "29,24,2" => Map(5) }

// etc..

The numbers refer to the value of the enum values like CT.Position, CT.Sprite, etc. In this case, CT.Position is 2 and CT.Sprite is 3, and there are 31 entities that have those two components. So when querying all entities that have those two components, we can just return that list of entities, rather than computing it each time.

This all works, but it's not very efficient, because adding (and removing!) an entity to the scene is an O(n) operation and also involves a lot of string splitting and concatenation. You need to iterate through every item in the cache to see if the entity's list of components is included by that entry.

Is there any way to improve this to be more like O(log n) or preferably O(1)? Let me know if this is all clear, or if there's any details that need to be clarified.

Here's a link to the Typescript Playground URL reproduction example

typescript hashmap data-structures algorithm javascript
2 Answers

I expect that the number of queries in the cache will be pretty small, since each query will be individually tied to a bunch of code that processes the results. So iterating over the query list and performing some operation for each one won't be that expensive, but if you have problems when adding or removing a whole bunch of entities, then that can certainly be addressed.

First the string representation you use for a subset of component types is indeed pretty inefficient. There are lots of alternatives. Maybe try something like this:

  1. First, assign an integer to each component type (you did this already)
  2. Sort the component types in the subset by their integer
  3. Build a string using each integer as a character

This representation is not too fancy, but it allows you to quickly get at the component types in a subset using charCodeAt(), and you can use that to test for subsets by walking through both strings simultaneously, or by walking through one while doing a binary search in the other.

The real improvements, however, would come from grouping entities by the subset of component types that they present. There are lots of ways. I think something like this would work for you:

  • For each entity, precalculate its component-type-subset string
  • For each subset in use, maintain the list of cached queries that match that subset. This list only needs to be modified when you introduce a new query or a new subset.
  • When an entity is added or removed, get the queries for its subset and add or remove it directly to/from the results.
  • When you get a new query, make a set of the subsets it matches, add it to the query list for those subsets, and check each entity to see if its subset is contained in the match set.
user_54835260

Okay, I think I have a tentative answer to this, in that it seems to be working, but the code is very complex for me to understand, so I'm not sure if this is actually working or if it just seems to be and is actually broken.

So, for the solution, I wanted to maintain the query performance because querying is called for every system for every frame update, so it's executed 1000x more often than entity creation / deletion. Currently querying works as an amortized O(1) algorithm by first checking if the cache contains this mapping of components. If it doesn't, it creates this list of entities associated with this grouping of components (archetype), and then henceforth that list is fetched from the cache. The cache is always kept up-to-date.

The issue in my question was that while it was nice to have an O(1) query operation, it would be desired to have more efficient add and remove operations, as they were O(n*k), where n was the number of distinct query operations (members of the cache) and k was the number of components in the entity. That is, whenever an entity was created or destroyed, the program would have to iterate through each item in the cache and check if the entity should belong to this query operation. If so, add it to that set, and if not, remove it.

The idea I had this morning was to implement another cache / mapping. That is, the original cache mapped from a query component listing (archetype) to the set of entities that held those components. Example:

{ "6,1,20" => Set(1) }
{ "2,3,1,6" => Set(1) }
{ "2,3" => Set(31) }

Let's say 2 referred to the PositionComponent and 3 referred to the SpriteComponent. This means that all entities that contain those two components can be found within that set of 31 entities.

So, my tentative solution to my original question was to also have a mapping where a list of components corresponds to all cache entries they're a member of. That is, say we have an entity with the following components: 1, 2, 3, 6, 25. Then its corresponding entry in this cache would look like this:

1,2,3,6,25 => [ "2,3,1,6", "2,3" ]

The first time an entity of that archetype (component listing) is constructed, that list is manually created. However, afterwards it is simply maintained. Then, whenever there is a request to create an entity of that archetype, we can simply query this cache to find out which cache entries we need to modify.

That way, instead of having to iterate through the entire cache and then iterate through each cache item to determine if it should be a member, instead we simply query our secondary cache to determine which cache entries it is a member of. So, I believe the amortized complexity shrinks from O(n*k) to O(c), where c is the number of cache entries it's a member of.

user_9621550
Related