Sign in to follow this  
rick_appleton

Gather operation in Entity Component System

Recommended Posts

I've started working on an Entity Component System where an entity is only an ID and all the data is held in the different systems. As an example I have two systems: RenderSystem and LocationSystem. Each system stores the data of the entities that have that component in a flat array, and has map of 'entity id'->'array index' for that system.

- LocationSystem contains a position/orientation/bounding box for each entity
- RenderSystem renders each entity using it's position/orientation

Now imagine I have three entities:
[code]
Entity 0:
Location
Render
Entity 1:
Location
Entity 2:
Location
Render

In the LocationSystem the contents will look like this:
array = [Location Component A, Location Component B, Location Component C]
map = [0->0, 1->1, 2->2]

In the RenderSystem the contents will look like this:
array = [Render Component A, Render Component B]
map = [0->0, 2->1]
[/code]

Currently the update for each system is called manually, passing in the map and array from the other systems that are needed, such that each system can then get at the proper data (basically a gather operation):

[code]
renderSystem->update( locationSystem.map, locationSystem.array );
[/code]
[code]
RenderSystem::Update( lsMap, lsArray )
{
for( entityID in this.map )
{
RenderComponent rc = this.array[this.map[entityID]];
LocationComponent lc = lsArray[lsMap[entityID]];

// Do stuff with the two components here
}
}
[/code]

However, I'd like to change this so that the system can iterate over it's own array in it's update function, and doesn't need to bother with the map:

[code]
RenderSystem::UpdateNew( ... )
{
for( i in this.array )
{
RenderComponent rc = this.array[i];
LocationComponent lc = ???;

// Do stuff with the two components here
}
}
[/code]

I guess I could do the reverse lookup outside the function, but I'm wondering if there is some kind of more efficient way to do this, taking into account that if an entity has a RenderComponent, then it also always has a LocationComponent.

Share this post


Link to post
Share on other sites
You can break your map up into an array of keys and an array of values:[code]LocationSystem:
array = [Location Component A, Location Component B, Location Component C]
keys = [0, 1, 2]
values = [0, 1, 2]

RenderSystem:
array = [Render Component A, Render Component B]
keys = [0, 2]
values = [0, 1][/code]Notice values are predictable now, i.e. if iterating through array, we can assert that [font=courier new,courier,monospace]values[ì] == ì[/font], so we can ditch the values array.
Now the problem is you're not using a hash-map any more (you've just got an array of keys), so you can't do fast entity lookups ([i]you've got to search the whole key array[/i]).
One way to fix this, is to keep using your hash-map as usual, but generate the above [font=courier new,courier,monospace]keys[/font] array on each update - i.e. extract the map's keys and sort them by it's values before running the update loop.
N.B. sorting your entire systems can be handy too sometimes. e.g. if Render held [A,B,C,D], but Location held [D,A,C,B], then your [font=courier new,courier,monospace]update[/font] function is going to be iterating forward through the render array, but randomly through the location array. If you first sort them both by their entity IDs, then your [font=courier new,courier,monospace]update[/font] function will be faster due to better cache patterns.

Share this post


Link to post
Share on other sites
[quote name='Hodgman' timestamp='1335344151' post='4934666']
One way to fix this, is to keep using your hash-map as usual, but generate the above keys array on each update - i.e. extract the map's keys and sort them by it's values before running the update loop.
[/quote]
I think this will only work if the components are sorted. If the array with components is not sorted by ID it'll give incorrect results.

[quote name='Hodgman' timestamp='1335344151' post='4934666']
N.B. sorting your entire systems can be handy too sometimes. e.g. if Render held [A,B,C,D], but Location held [D,A,C,B], then your update function is going to be iterating forward through the render array, but randomly through the location array. If you first sort them both by their entity IDs, then your update function will be faster due to better cache patterns.
[/quote]
This is the main idea of having the extra indirection there [img]http://public.gamedev.net//public/style_emoticons/default/biggrin.png[/img]
I didn't think of eliminating the values array like that, it's definately a good point. It makes it a bit easier to think about that way, since I then only need to reconcile the two arrays:
[code]
array from LocationSystem: [0, 1, 2];
array from RenderSystem: [0, 2];
[/code]
I think I can safely set the extra limitation that those indexes will be sorted, although that does mean I'll need to move a lot of components if I erase an item in the middle.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this