Entity-Component Confusion

1
Does Artemis actually say that it is a solution for optimising your game?
The "ECS" phrase originally popped up as a solution for flexibility and empowering game-designers. Only recently have people started making ECS frameworks with an eye to performance optimisation.

Some of the older ECS frameworks I've used had horrible performance, but you put up with it because you wanted to use the other features (which at the time was basically writing OOP from an XML file instead of C++ code :()

2
It's common to not compact arrays when items are removed, and instead have two extra arrays/lists of indices. One contains the indices of valid array elements so that you can iterate through all the items in the array, the other contains the free elements so that you can allocate new items.
At this point you're basically dealing with a pool with a free-list, not a basic array.

3
The memory requirements of a game are completely predictable, which means it's quite feasible to use fixed size allocations instead of growable ones.
If that's too hard, a std::vector is still probably a better choice than a std::list though!!

So far... from what I can gather from studying Artemis is that the components are stored in maps. Aren't hash tables less efficient for the cache? Given that it's normally scattered around the memory?

I just looked at the source code, and the components appear to be stored in arrays.

Does Artemis actually say that it is a solution for optimising your game?

Actually, original Artemis doesn't stores components in maps. I know Ashley (libGDX sponsored ECS framework) does, and in fact gives pretty crappy iteration performance. Artemis, its most popular fork artemis-odb and my own fork, all store components in arrays.

What Artemis did is have a component manager storing components in an array of arrays of components. So each slot in the array would correspond to a component type, and the array in that slot would contain all the components of that type for all entities that had them.

Thats why if you look at the source, you got a Bag of Bags of components. For retrieving a component you'd do componentsByType.get(componentTypeIndex).get(entityID). Thats esentially componentsByType[typeIndex][entityID]. Array of arrays of components.

Now, Artemis is made in Java, so the thing is, its not arrays of components but arrays of pointers to components. Yes, this gives bad cache locality*, but thats all you have in Java unless you want to go the way of the ByteBuffer and pretty much implement array of structs by hand, which is only viable if a) You have a lot of experience with this stuff and know exactly what components will get processed often in which groups or b) You already have a semi complete game and can profile to see what components are worth having close to eachother.

I'm not a performance guru but I advocate for the following: Just do plain arrays of pointers to components. Right now it will probably be enough for whatever use case you have, and its something you can perfectly optimize for later when you have enough test cases to try. Its easier to optimize for a specific target rather than thinking right now months (or years!) ahead what your use cases might be in the future to warrant such optimizations.

Moreover, having array of pointers to components means that you don't need to do any complex entity -> component mapping. Just have an array of pointers, and to get a component just index into it with the entity's ID. ie:

Spatial* sp = spatials[entityID];
Velocity* vel = velocities[entityID];

This means that you'll have one indirection when you access the component BUT the important point right now is have something working and nail the ECS way of doing things. Systems shouldn't know the particulars of how components are stored, so you can come up with an interface for the systems to retrieve components, and resolve the way they're stored behind their backs so to speak. That way if in the future you want to optimize further by storing components contiguously or compacting their arrays, you can do so transparently.

* Actually it depends of the GC algorithm, if the component objects are discovered by the GC pass via said array, they'll get copied to an older generation one next to the other. Which helps a bit.

The main issue is that I am writing in C++, and most of the actual game logic is going to be done with LUA. I'd like the engine to be modular, and easily modified when needed to be. So... it's basically turning OOP onto it's head to a degree. Think Dungeon Siege.

The plan is for the engine to support a massive number of items on the screen at once, so... cache performance is kinda needed, when DirectX doesn't have to much problems with rendering thousands of objects. And each item can be scripted if needed, or be skipped if it doesn't use a script.

My previous work with C++ and games... tell me that pointers can get nasty if there are to many, simply because debugging because painful. Especially when you can't always track where something is in the memory, and when it changes.

I'll take a look at Artimis-obd though. I might be able to port it into C. In the mean time. Any other ideas?

The main issue is that I am writing in C++

Look at this C++ port of Artemis?

Huh... didn't see that one. Quick question though. What is a "Bag" this is actually the first time I've heard of this storage method.

What is a "Bag" this is actually the first time I've heard of this storage method.

It's a class in the Artemis framework. Read the source code. The comment says:

Collection type a bit like ArrayList but does not preserve the order of its entities, speedwise it is very good, especially suited for games.

The main issue is that I am writing in C++, and most of the actual game logic is going to be done with LUA. I'd like the engine to be modular, and easily modified when needed to be. So... it's basically turning OOP onto it's head to a degree. Think Dungeon Siege.

ECS is currently a trending fad in the hobbyist world of game development, and while it is a useful tool in your belt, it’s only really useful to you if you know how to wield it.

I’ve already discussed this here and here:

Anyway, based on what you've said and some more thought of my own, I think I'm going to go with an OO/ECS hybrid; utilizing classes for systems of behavior that don't work so well when split up, and supporting components for attachable/detachable behavior where it makes sense (for example, power ups in a racing game would be a great candidate for utilizing components, while the actual driving mechanics might not be).

This is exactly the correct approach. If you scour the forums you will find many cases where people have been exposed to ECS (typically through Unity 3D) and immediately just go full-on ECS without really considering what its real benefits are, especially given the gap between them and the makers of Unity 3D.
If there is anything a programmer needs to know about programming, it’s that there are indeed many approaches to any given system, but there are no single best answers. Every solution should be taking the benefits from one approach and the benefits from another approach.

You might have thoroughly thought about why you’ve decided to go this route and how ECS can benefit you, and maybe you have a tool-chain and scripting language in-place (you seem to have scripting at least), or you might be in the camp with those who just think, “it’s what they do these days, so I will do it too,” (it’s not really what most industry professionals do).

If you haven’t really understood the reasons to go ECS, you should stop and research more and reconsider.

That being said, using it with LUA (a LUA component) could be very powerful.
On the other hand that can be done just as easily via object-oriented programming, while maintaining better overall engine organization (ECS makes it extremely easy to violate a lot of coding practices that otherwise make your code clean, modular, and safe).


In the end, the best way to know if ECS is right for you is to consider how, in the future, you plan to add and initialize all these components to objects.
If you’re planning to have set-up code that adds hard-codedly and initializes components, you are doing it wrong and ECS has no meaning for you.
You have to at least have a fairly complex file format, a good parser, an interpreter, and hopefully a good tool for creating said file format.

If you are not planning on really putting in effort to make these things, ECS has no meaning for you.


L. Spiro

I've already researched a lot of different methods before coming to ECS. And from what I can understand the flexibility is what I needed for the project I had in mind. Not to mention it so far has made certain things easier to do... and interesting at the same time.

Wall that is able to shoot and move around due to a weird glitch with the component arrangement. It was a constantly reproduced bug, so I took a look at what was going on in the memory, and there was the problem in the loop.

It actually further set the idea for me, as that glitch really made a funny feature for me. Which... I may actually explore a little further. But first things first is to get the system working properly.

My end goal is that the engine can be easily modified, with the actual low-levels only being touched to add features to the engine, or make updates and improvements. Other wise, the engine will be a dumb fired fire-and-forget sort of system.

With luaJIT for faster iteration times. I'm not to bothered at the moment with having scripts automatically reload. I'm more concerned with getting things working before features.

What confuses me though is how do you store the component in an efficient way? My understanding of the entity-component system is that it simplify things, and reduces cache misses, right?

I have similar topic http://www.gamedev.net/topic/662559-entity-component-system-data-locality-vs-templates/ and I was directed to this bitsquid blog that I found very helpful. Making a manager for each type of component avoids problems with storing inhomogeneous data in arrays. I also liked their idea not to constrain the component managers that much. Different type of components may benefit from different type of component storage and entity<->component indirection. I personally would create base component manager classes for some most typical situations to avoid code dublication.

I.E. When a player shoots a ship, and the ship is now dead. It should be removed. So it's flagged as such, and at the end of the loop, it gets removed from the list, and everything gets shifted down to keep data clustered tightly.

Use the "swap and resize": move the last item to the place of the removed one and reduce the array size by one. Of course if entities refer directly to component arrays, the one moved component will no longer point to the correct entity. You need to add a layer of indirection: one array stores components, the other maps entities to the components.

Use the "swap and resize": move the last item to the place of the removed one and reduce the array size by one. Of course if entities refer directly to component arrays, the one moved component will no longer point to the correct entity. You need to add a layer of indirection: one array stores components, the other maps entities to the components.

This isn’t appropriate for the arrays of components, and in fact isn’t practical.
An entity is just an index into the array. If you move the last element in the array to a new location you would have to find every copy of that “entity” and change them as well, which is simply impossible in practice unless you’ve designed your system such that you guarantee there are no copies of entities anywhere but in your scene manager at a specific point in your game loop, which is a very poor/unstable/restrictive way to design your system.

Having a map as a layer of indirection is not practical from a performance/debugging standpoint.

Do as Hodgman says:

2
It's common to not compact arrays when items are removed, and instead have two extra arrays/lists of indices. One contains the indices of valid array elements so that you can iterate through all the items in the array, the other contains the free elements so that you can allocate new items.
At this point you're basically dealing with a pool with a free-list, not a basic array.

L. Spiro

In the end, the best way to know if ECS is right for you is to consider how, in the future, you plan to add and initialize all these components to objects.
If you’re planning to have set-up code that adds hard-codedly and initializes components, you are doing it wrong and ECS has no meaning for you.
You have to at least have a fairly complex file format, a good parser, an interpreter, and hopefully a good tool for creating said file format.

If you are not planning on really putting in effort to make these things, ECS has no meaning for you.

Coming back to this. I've actually done a bit of research on how objects could be built.

1. Probably make use of an SQL or Relational database. While it is slow on the load time, I doubt that would matter much once the information strikes the factory, and the factory assembles what's needed into memory. This could be an issue if done many many times, and it would probably be better if it was just a plain text file that is an array. But it does have the attractive solution of making designing tools easier. Statically holding Base IDs, and basic information that can be randomized on runtime, hundreds of items. Maybe it'd add the extra benefit of holding data for things like material if I look into it further.

Especially with the issue of multiple of the same items being spawned in at a time in playing.

I did think about a way to make this more efficient.

Use a que, and reference count the number of times it needs to be loaded, and staple it down.

But I realized that was over engineering for something that was down right impossible on the player end. Especially seeing that something like this happens within microseconds at run time... and running a code like that would... be just wasting time.

And would only be used for loading... which means... wait and see.

2. Protobuf looks like an attractive solution as well. But it doesn't seem like the best idea to use for storing entity information, individually anyways. Especially since we can assume that not all entity data will be used.

3. Blob. Probably my go to method for serializing game states. But maybe not entities.

4. Lua. Could work very well, but would make things annoying in a RPG enviorment with rogue like elements. Not to mention more seeking over the disk.

Hodgman, on 12 Feb 2015 - 5:31 PM, said:
2
It's common to not compact arrays when items are removed, and instead have two extra arrays/lists of indices. One contains the indices of valid array elements so that you can iterate through all the items in the array, the other contains the free elements so that you can allocate new items.
At this point you're basically dealing with a pool with a free-list, not a basic array.

From what I can gather... that means two arrays

[DATA] [DATA] [DATA] [DATA]

[Empty] [Empty] [empty] [empty]

While I iterate through the first array.

I am simply adding data to the Empty array...

[Data] [Data] [Data] [Data] <- [Data appending from various threads]

|

\/
[Data] [Empty] [Empty]


And anything that fails, doesn't get added?

[Data] [Data] [Data] [Data] <- [Data appending from various threads]
|
\/
[Data] [Empty] [Empty]


And anything that fails, doesn't get added?

Not sure what "anything that fails" means, or why threading is relevant. I understand it like this:

free indices: [2] [3] [6]

valid indices: [0] [1] [4] [5]

component list: [DATA] [DATA] [empty] [empty] [DATA] [DATA] [empty]

Then I need to allocate one of these components for an entity. After, it would look like this:

free indices: [3] [6]

valid indices: [0] [1] [2] [4] [5]

component list: [DATA] [DATA] [DATA] [empty] [DATA] [DATA] [empty]

By "Anything that fails" I mean things that needs to be removed from the update loop marked by a simple bool.

Example... An item is on the ground. Naturally we update this repeatedly as long as it's in view. But the moment it's removed from the world, we mark the bool as a fail, and track it's index, or just iterate through the loop once more and remove it as we update. And leave it in place to be removed on the next pass, and everything will quickly be shifted down. The moment an empty space is detected, update stops. If you have a set array of 1000 objects, why iterate through all of them when we only have 502?

The problem likely occurred by the way I was handling entities and components on the update.

By threading, there's going to be a lot of things active at once that will be needing updates. More than what my previous projects were. Right now I don't have threading installed just yet, but I have a safety measure for new items added into the list in case I screw up the threading. This is also to avoid having newly added items being skipped in the update. Though... this is only once in a frame, so it probably wouldn't matter.

And leave it in place to be removed on the next pass, and everything will quickly be shifted down. The moment an empty space is detected, update stops. If you have a set array of 1000 objects, why iterate through all of them when we only have 502?

This shifting of items works if your arrays are arrays of pointers (as they kind of have to be in java or C#). If they are arrays of objects, they probably need to stay where they are for the reasons Hodgman and L Spiro mentioned. Do you understand why?

It doesn’t need to be complicated.

Let’s start off by using more accurate terminology. “DATA” implies there is actual used data there. The second array is supposed to tell us that, so instead, it’s:

[SLOT][SLOT][SLOT][SLOT][SLOT][SLOT][SLOT][SLOT]

[FREE][USED][USED][FREE][FREE][FREE][USED][FREE]

Every [SLOT] contains the full set of components an entity can have.

From this, we know we have entities 1, 2, and 6.

When we allocate a new entity, the first [FREE] is found (0) and it is changed to [USED]. Simple as that.

Each [SLOT] needs to consume however-much data you need for all possible components, but [FREE]/[USED] use only 1 bit, so here I have used only 1 byte for the second “array”.

When you have more than 8 entities and you need to add another, reallocate these arrays.

The arrays themselves don’t have to stay in the same place in memory—the orders of the items in the arrays must remain the same. Entities are just indices into these arrays, so who cares if the arrays themselves move? You can still find all your entity’s components next time you need them.

So you aren’t restricted to a fixed number of entities etc. You just can’t move items around inside the arrays.

L. Spiro

t doesn’t need to be complicated.

Let’s start off by using more accurate terminology. “DATA” implies there is actual used data there. The second array is supposed to tell us that, so instead, it’s:



[SLOT][SLOT][SLOT][SLOT][SLOT][SLOT][SLOT][SLOT]

[FREE][USED][USED][FREE][FREE][FREE][USED][FREE]



Every [SLOT] contains the full set of components an entity can have.

From this, we know we have entities 1, 2, and 6.

Ok, I think I get it now. But I do see some possible future problems. While the game targets desktop... and memory isn't an issue. Wouldn't that explode with time?

Positional Data {X, Y, Z} 12 bytes
Physics Data {vY, vZ, vX, colision mesh, masks} 12 bytes

Entity {ID} 4 bytes.

Mesh Data { refMesh, refTex, refMat}

LUA Logic {?} ??????????
Agent info {?}

ect...

Arrays will only allocate a set amount of data. So this data is made into one cell.

Then comes another issue.

Just about everything in the system will be defined via entity. Terrain, trees, grass, walls, player, AI, ect.

So... that count at 1000 could easily reach MBs of data right?

Not to mention from the sounds of it, it's one super class that is split up for some reason.

But, incredibly viable. Given that I don't know of any desktop that has less than 2 gigs of ram.. with a minimum of 4. And a bit of research says that the processor prefetches.

You know... I think I have been going about my method stupidly. It means that I'd have to rewrite a lot of my code... but I think this design is better. What are your opinions?

1. If the entity is just an index... it generally doesn't make any sense to loop this without a really good reason. So we can probably just scratch that out of the loop. And use it for referencing purposes. ake my life easier in lua by using a function to get data, rather than have it preset immediately? Or maybe it lets the system knows that it's still alive and should be processed?

2. Components are the only ones with data that actually matters. So what if the components simply kept the ID of entity it's representing and iterates blindly of everything else. The biggest problem with this I can think of, is that the code isn't being processed all at once. So while the code data is hot in the cache... it can probably cause errors else where. Especially with lua updating things.

3.Because components knows their entity, and the entity does not know the component. It might mean that LUA scripts can be held in the entity themselves, and be given immediate access to their IDs. To know about it's components, it could do a look up. And for a raycast against a physics, the physics would only need to emit it's entity's ID.

While the game targets desktop... and memory isn't an issue. Wouldn't that explode with time?

What do you mean? Unless you keep allocating entities without ever freeing them, nothing is "exploding". The arrays are not growing without bound.

Just about everything in the system will be defined via entity. Terrain, trees, grass, walls, player, AI, ect.

It is not necessary that everything needs to be modeled as an entity.

So what if the components simply kept the ID of entity it's representing and iterates blindly of everything else. The biggest problem with this I can think of, is that the code isn't being processed all at once. So while the code data is hot in the cache... it can probably cause errors else where. Especially with lua updating things.

I have no idea what you're saying here. Components don't iterate over anything. Errors? What? What does lua have to do with any of this? It's really irrelevant to the discussion in this thread.

Probably lack of sleep taking over my speech skills.


I am thinking of a very possible scenario if the random generator decided to just dump a mess of coins onto the ground. As ridiculous as that sounds, it is the nature of intent. Right now. Lua is the only thing hard coded into entities for testing purposes.

While I guess it's true that not everything has to be an entity, I'd like to keep it, in the case I decide to turn a glitch into a controlled feature. (everything can be scripted, but only when it's actually needed.)

And errors are along the lines of things happening before they actually should, and other with other systems breaking things. I've ran into that on the first design.