ENIGMA Entity-Component-System?

[Ideka]

Check it out: http://www.tomseysdavies.com/2011/01/23/entity-systems/
Personally I think this is The Shit (tm).

Do you guys think something like that could be elegantly done in ENIGMA? Because it's possible in GM, but it's a pain in the ass. Probably really slow, too.

Here's a C++ ECS implementation: https://github.com/miguelishawt/anax and there's also https://github.com/alecthomas/entityx

[DaSpirit]

I remember trying to make an entity-component system for an engine I was making in C++ years back. The problem with the system is that it is too dynamic. Most modern CPUs attempt to predict what will happen to your code. If it guesses correctly, your program runs way faster. If not, it has to undo all of that work. Because there are infinite possibilities for components, CPUs cannot optimize the system at all.

[Josh @ Dreamland]

Game Maker already makes that simple, if ugly. Consider this:

Code: (EDL) [Select]

// The parent object's draw event
script_execute(renderer);

// The parent object's step event
script_execute(physics);
for (i = 0; i < number_of_arbitrary_behaviors; ++i)
  script_execute(arbitrary_behaviors[i]);

// Somewhere that wants to demonstrate how "a Ninja could become a Tank!":
myninja.renderer = scr_render_tank;
myninja.physics = scr_physics_tank;
myninja.arbitrary_behaviors[0] = scr_ai_tank;
myninja.arbitrary_behaviors[1] = scr_armor_tank;
myninja.number_of_arbitrary_behaviors = 2;

In GM, any object can call any script. So essentially, you can already do that with either of function pointers or script references and script_execute. So, as long as all of your behaviors are scripts, you can already use this system.

I don't care for this as a design choice; my preference is virtual functions, which are planned. Multiple inheritance is also planned, so that you can inherit multiple behaviors which cannot be changed at runtime.

Disclaimer: This capability is the exact reason Game Maker is slow, and using it will make you quickly discover how slow ENIGMA can be.

In fact, it used to be that ENIGMA would not support this method, until polyfuck changed it. The reason for this is simple. Say scr_tank_armor processes collisions in self.collision, and changes self.armor accordingly. What if a Ninja doesn't have self.health? In GM, that isn't relevant; variables are stored in a hash table, so all variables can exist in all objects, and so we have variable_local_exists, et al, to help us. In ENIGMA, that just isn't the case. So if your behaviors don't all use the same variables, ENIGMA will resort to polygone's map of vars by varname, and you'll get all the speed of var (about 12x slower than double) and all the speed of map.find() (hundreds of times slower than an assign) at no extra cost.

If you have a compelling reason to change behaviors at runtime, then by all means, store a pointer to some behavior class which contains its own variables to modify. Of course, then behaviors can't share variables, and you'll need to work that out by having the health behavior know of or extend the physics behavior so it can respond to collisions... Mess, mess, mess.


The new EDL specification supports or will support the following to help deal with this:

• Multiple inheritance. Right now, each object can only have one parent, so [snip=EDL]with (enemy) { health -= 1; }[/snip] might be useful, and [snip=EDL]with (destructable) { if (distance_to_object(other) < 64) instance_destroy(); }[/snip] might be useful, but since no object can be both destructable and enemy... Well, now they can.
• C++ Classes: The new EDL specification (available in the Wiki) calls for classes which can have fields, inheritance, and virtual functions. Everything you need to make these behaviors as separate classes.
• Closures: Perhaps the element about which I am most doubtful, EDL2 calls for closures. This is catalyzed greatly by C++11's own support for lambdas. A closure is a function that inherits the scope in which it is created, so assignments in the function will change the variables in the calling object. My understanding of C++11's implementation of this is limited; if it's anywhere near as capable as JavaScript functions, this will prove an invaluable asset for dynamic design. Of course, JavaScript offers methods such a bind(), which would make implementing GM's scripts less of a kludge, so I'm not expecting quite that much power from C++11.

That said, you can probably tell that this component-based system is not my favorite design element. I would never use it unless I had a glaring need for a tank to become a ninja, or vice-versa. It sounds powerful and disarmingly fun and silly until you realize that it may be the dumbest and most harmful capability employed by your engine. There's always a trade-off.

ENIGMA's extension system uses multiple-inheritance. A long time ago, when Rusky was interested in the ability to change out fucking graphics systems at runtime, there was a battle over this structure versus components. I have yet to encounter a reason to embrace components for the task, and in general do not encourage them, but if you have one, I'm interested in hearing it.

[TheExDeus]

I always used 1 object for 80% of the games logic. For example, in a tower defense game it would make sense to create an object for every enemy type and I guess it would be the best way (as objects are like classes). But I for some reason prefer to have obj_controller which has 80% of game logic and then obj_enemy which encapsulates every single type of enemy and obj_tower which can be every single type of tower. Then I use either bools (which is bad, as it requires a variable for every kind of system, like "bool can_shoot_flyers = true" or false) or variable_local_exists(), which don't require the ram, but is slower. I guess the best way would be to either use several objects for several types (like obj_tower_shoots_flyers) or to do everything via assigned scripts as Josh pointed out. Doing things like tower_update_scr = scr_flame_trower; is actually pretty powerful (used this in my circuit drawing program, where every component had a drawing script and the draw event just called that script).

Also, Josh, I thought you died.

[Ideka]

I doubt you guys read the entire article. What all of you seem to be talking about is the somehow more widely known, clunky, old, inconvenient, not really useful ECS way of doing things.

In a good ECS, components are not "behaviours". Components ONLY have data (and maybe getters/setters). Systems have behaviors. All defined systems process all game objects that have certain components.

[Goombert]

I like an ECS, take Unity3D for instance, I love shit being attachable/detachable easy, and it is not that big of a deal in something like C#.

[Josh @ Dreamland]

Indeed; I stopped reading around the time he ceased using punctuation in high frequency and just started asserting random ideas. He repeatedly states that this system is better than the "traditional inheritance hierarchy" while giving no indication that he has considered multiple inheritance/typical interface-based systems as an alternative. From what I can tell, this system is identical to multiple inheritance, except the ability to swap out components at runtime. This, he seems to handle using boost::dynamic_bitset to flag entities as having certain components. Personally, the solution makes me want to rip off my own skin, but it's cool if you're into that.

Since ENIGMA's extensions don't change out at runtime, it handles this by keeping lists of items which are known to have what you're calling "components." Instances add themselves to the proper lists on creation, and remove themselves from them upon destruction. You could do the same thing dynamically by just creating classes to handle this automatically, and simply pushing them onto some list in the instance and popping them off and deleting them when done: the ctor/dtor for those classes would take a pointer to the entity (here, instance) and handle everything for you.

That brings me back to my original question: why would you ever want to do this?
This reminds me of a lecture I had to sit through on decorator patterns. I can see this as being a fantastic and brilliant replacement to decorators. To clarify, my question at the time was, why, oh why, would you ever use a decorator?


My assessment of your ability to achieve this easily in either of Game Maker or ENIGMA has not changed. In game maker, nothing is to stop you from setting object.has_component to true, or checking if it has been set. Unfortunately, same in ENIGMA.

That said, I will look into making sure that quickly stapling attributes to objects is possible at runtime. My primary focus, however, will remain on doing so at compile time.

[Ideka]

I can't beleive you're comparing ECS to multiple inheritance. Apart from not being able to swap components (which is, for example, a perfect way of implementing a finite state machine), long inheritance trees are complex and messy, and couple everything together.
Here, say you have a class that inherits from two other classes. How do the parents communicate with each other? They either don't, or do so in a completely ass-backwards way.
In an ECS you can just have two systems that require the same component.
Also see: http://gamedev.stackexchange.com/questions/33062/doesnt-multiple-inheritance-solve-all-problems-that-entity-systems-do?rq=1

An ECS also turns this:

Code: [Select]

  Subtype A
  ---Operation 1
  ---Operation 2
  ---Operation 3
  Subtype B
  ---Operation 1
  ---Operation 2
  ---Operation 3
  Subtype C
  ---Operation 1
  ---Operation 2
  ---Operation 3
Into this:

Code: [Select]

  Operation 1
  ---Subtype A
  ---Subtype B
  ---Subtype C
  Operation 2
  ---Subtype A
  ---Subtype B
  ---Subtype C
  Operation 3
  ---Subtype A
  ---Subtype B
  ---Subtype C
Since the same operation is run looped, threading is EASY AS FUCK. You just set some systems to run in parallel and/or to process their entities in parallel and boom, threading done.
Things like collision detection and resolution is also easy for much the same reasons. You just need a CollisionSystem that requires a PositionComponent and a SpatialComponent (and maybe a 'flag component' CollideableComponent, so you can have stuff with position and spatial information that doesn't collide).
With that, CollisionSystem has a bunch of entities with a position and spatial information that have to be rearranged so they don't collide.

There's also this article if you want to do more reading: http://www.richardlord.net/blog/what-is-an-entity-framework
I warn you though, the code examples are in actionscript (!).

This, he seems to handle using boost::dynamic_bitset to flag entities as having certain components. Personally, the solution makes me want to rip off my own skin

It's usually done that way because it's fast, I believe. All of that is abstracted away though, so you don't really have to worry about it.

[Josh @ Dreamland]

The point was that his system is no more of a revolution to me than Java people constantly spouting [snip=java]if (entity instanceof SomeComponent)[/snip] or C# people doing the same with [snip]if (entity is SomeComponent)[/snip]. I get that you're attached to this idea; I don't get why you don't see the remarkable similarities between it and multiple inheritance. You're looking at the small picture of what it allows; the big picture is this:

Code: [Select]

Operation X
  Subtype A
  ---Operation 1
  ---Operation 2
  ---Operation 3
  Subtype B
  ---Operation 1
  ---Operation 2
  ---Operation 3
  Subtype C
  ---Operation 1
  ---Operation 2
  ---Operation 3
Operation Y
  Subtype A, as well
  Subtype D
  ---Operation 1
  ---Operation 2
  ---Operation 3
Operation Z
  Subtype B, as well
  Subtype E
  ---Operation 1
  ---Operation 2
  ---Operation 3
  Subtype F
  ---Operation 1
  ---Operation 2
  ---Operation 3

Consider this piece of Java:

Code: (java) [Select]

void tank_logic(Object entity) {
  assert(entity instanceof TankArmor);
  TankArmor armor = (TankArmor)entity;
  assert(entity instanceof TankAI);
  TankAI ai = (TankAI)entity;

  MysticalChoiceList choices;
  if (armor.isReallyBadAss())
    choices = makeBoldChoices(ai.getSomeProperty(), ai.getSomeOtherProperty());
  else
    choices = makeRationalChoices(ai.getSomeProperty(), ai.getSomeOtherProperty());
 
  // ...
}

Any game entity which implements both of those required components can be passed to that function. How is this any different from your system, aside from the obvious and already-mentioned ability for me to interchange components at runtime? If that is the key difference, why is it useful? Can you give me one use case where this capability is material?


In the interest of fairness, I'll respond to you on a per-sentence basis.

> Apart from not being able to swap components (which is, for example, a perfect way of implementing a finite state machine),
Why are you using a finite state machine as an example of this? They are the perfect example of something to do at compile time. I assume you're thinking of the game's internal representations of states in terms of such a machine; for instance, in a Mario game, Mario can move between being small, being big, being fire/ice powered, being invincible, etc, etc, and so you'd just keep piling behaviors on. For that, the ability to just tack on an invincibility behavior to Mario is extremely useful. What's the big difference between doing that, and having Mario inherit from an invincible class? You aren't saving anything; you're moving a check from inside an interface to in a boost bitset. I suppose you could be saving upward of 63 bits by doing this, but I hear memory is cheap. As requested, can you give an example of where this could not be accomplished using interfaces?

> long inheritance trees are complex and messy, and couple everything together.
Let's clarify here: do you mean long inheritance trees, or do you mean deep inheritance trees? If you're complaining about the former, you and I really don't see eye to eye, and I'm much more compelled by complaints of a boost bitset and a pointer list. If you're complaining about the latter, I have good news: that shouldn't happen. See the Java code above for the use case you've been describing.

> Here, say you have a class that inherits from two other classes. How do the parents communicate with each other? They either don't, or do so in a completely ass-backwards way.
Or, they do so in the same way yours do: by having a separate function, aware of both components, which performs casting to both. See Java code.

> In an ECS you can just have two systems that require the same component.
I could very easily construct another function which depends on TankAI and TankPhysics, or TankAI and NinjaPhysics, or TankAI and NinjaHealth, which would otherwise look exactly like the above Java code except using NinjaHealth instead of TankArmor as a decision point for how to treat the AI's internal state.

> Since the same operation is run looped, threading is EASY AS FUCK. You just set some systems to run in parallel and/or to process their entities in parallel and boom, threading done.
You can do the same thing with a good number of functions similar to the one I've written above.

> Things like collision detection and resolution is also easy for much the same reasons. You just need a CollisionSystem that requires a PositionComponent and a SpatialComponent (and maybe a 'flag component' CollideableComponent, so you can have stuff with position and spatial information that doesn't collide).
Last I checked, [snip=java]if (entity instanceof CollideableComponent && entity instanceof PositionComponent)[/snip] is valid Java, provided CollideableComponent and PositionComponent are both classes. Any reason I might want to remove CollideableComponent or PositionComponent from an entity rather than remove the entity from some list, temporarily? Or give the component a boolean, instead of using a fucking bitset?

> With that, CollisionSystem has a bunch of entities with a position and spatial information that have to be rearranged so they don't collide.
What I'm demonstrating is that this use case is no different whether these components can be swapped out at runtime or not. Once again, I'm happy to hear an example where this would be useful.


In summary, the two mechanisms are arguably identical except one is done at runtime. A wise man once told me (and the rest of the class, really) that anything which can be done at compile time, probably should be done at compile time. Why can't I do all this neat shit at compile time?

[Ideka]

Consider this piece of Java:

Code: (java) [Select]

void tank_logic(Object entity) {
  assert(entity instanceof TankArmor);
  TankArmor armor = (TankArmor)entity;
  assert(entity instanceof TankAI);
  TankAI ai = (TankAI)entity;

  MysticalChoiceList choices;
  if (armor.isReallyBadAss())
    choices = makeBoldChoices(ai.getSomeProperty(), ai.getSomeOtherProperty());
  else
    choices = makeRationalChoices(ai.getSomeProperty(), ai.getSomeOtherProperty());
 
  // ...
}

Aight, now tell me, can you come up with an algorithm that, given every entity that exists in the game world and every function like that one you show me, automatically figures out which entities can be passed to which funcions and does so one by one?

> Apart from not being able to swap components (which is, for example, a perfect way of implementing a finite state machine),
Why are you using a finite state machine as an example of this? They are the perfect example of something to do at compile time. I assume you're thinking of the game's internal representations of states in terms of such a machine; for instance, in a Mario game, Mario can move between being small, being big, being fire/ice powered, being invincible, etc, etc, and so you'd just keep piling behaviors on. For that, the ability to just tack on an invincibility behavior to Mario is extremely useful. What's the big difference between doing that, and having Mario inherit from an invincible class? You aren't saving anything; you're moving a check from inside an interface to in a boost bitset. I suppose you could be saving upward of 63 bits by doing this, but I hear memory is cheap. As requested, can you give an example of where this could not be accomplished using interfaces?

Well, in an ECS you may have a component for each state and a system for each state, and when you want to change state just remove the components of the current state and plug in the ones of the new state (all of that would be taken care of automatically, perhaps as described here).
Can it be done with multiple inheritance? I... guess? You could give each Component an "active" flag or something?

> long inheritance trees are complex and messy, and couple everything together.
Let's clarify here: do you mean long inheritance trees, or do you mean deep inheritance trees? If you're complaining about the former, you and I really don't see eye to eye, and I'm much more compelled by complaints of a boost bitset and a pointer list. If you're complaining about the latter, I have good news: that shouldn't happen. See the Java code above for the use case you've been describing.

OK, I get that now.
I guess I meant deep by the way. Didn't know there was a difference.
Also will you stop it with the boost bitset thing. That's just something an specific ECS framework implementation uses.

> Things like collision detection and resolution is also easy for much the same reasons. You just need a CollisionSystem that requires a PositionComponent and a SpatialComponent (and maybe a 'flag component' CollideableComponent, so you can have stuff with position and spatial information that doesn't collide).
Last I checked, [snip=java]if (entity instanceof CollideableComponent && entity instanceof PositionComponent)[/snip] is valid Java, provided CollideableComponent and PositionComponent are both classes. Any reason I might want to remove CollideableComponent or PositionComponent from an entity rather than remove the entity from some list, temporarily? Or give the component a boolean, instead of using a fucking bitset?

OK, that's cool, but you would have to loop through every entity in the world and check each and every one of them.
In an ECS you are just passed an iterable with all the entities that have the required components and you are ready to go.

In summary, the two mechanisms are arguably identical except one is done at runtime.

I certainly see the similarity, but they're far from identical .

[Goombert]

Me loves how you all ignore the fact I got real inheritance added and my post takes back seat :\

[Josh @ Dreamland]

> Aight, now tell me, can you come up with an algorithm that, given every entity that exists in the game world and every function like that one you show me, automatically figures out which entities can be passed to which funcions and does so one by one?
As I've stated, the simplest way to do this is to create a queue for each behavior. So, CollideableComponent contains static [snip=Java]Queue<CollideableComponent> all;[/snip], and PositionComponent contains [snip=Java]Queue<PositionComponent> all;[/snip]. In the constructor for each class (which, in C++, is called automatically for all parents), the object adds itself to the end of the queue. In the destructor, it removes itself. ENIGMA does both of these as an O(1) operation. Now, let's say you want all and only objects which are both CollideableComponent and PositionComponent. Pick the shorter of the two queues (CollideableComponent.all and PositionComponent.all) and iterate it, checking that each entity has the other component (you already know it has the first). So, this approach is O(N) in the length of the shorter list.

Another approach, which does not require RTTI, is to make the component queues keep an entity pointer, then iterate the two lists in parallel looking for identical entities. This method isn't that great, as the runtime is O(N × M); this can be reduced to, at very worst, O(M + N), using methods such as time stamps (in ENIGMA's case, entity ID). Basically, you don't have to do any backtracking because the elements were added to the queue in the order they were created. Consider these lists of entities:

Code: [Select]

  Collideable:  1000001 1000004 1000005 1000008 1000009
  Position:     1000002 1000003 1000004 1000006 1000007 1000008 1000010

We have a lot of entities with a position, and a lot which collide. For some reason, we even have entities which can collide but do not have a position (ENIGMA explicitly disallows this, as it uses tiering for these behaviors). But for the sake of argument, let's just say that's our list. We use two pointers, positioned at the start of each list, and advance like this:

Code: (EDL) [Select]

  int i = 0, j = 0;
  while (i < collideable.length() && j < position.length()) {
     if (collideable[i] == position[j]) {
       // Tah-dah; this instance is both
     }
     ++(collideable[i] < position[j]? i : j);
  }

So, we compare instances in this order: (1000001, 1000002), (1000004, 1000002), (1000004, 1000003), (1000004, 1000004) (yay! a match!), (1000004, 1000006), (1000005, 1000006), (1000008, 1000006), (1000001, 1000002), (1000008, 1000007) (1000008, 1000008) (another match), (1000008, 1000010), (1000009, 1000010). So, our naive little method completes in exactly M+N iterations.

Of course, in C++, you'd write template functions to handle this for you. And having ENIGMA do something like this for you would not be very complicated, either.

> You could give each Component an "active" flag or something?
That's one solution. It's kind of an ugly solution, like using a dynamic bitset. But it's still a solution, yeah. Another solution is to give each component a deactivate() method which removes itself from the queue described above, and an activate() method which re-adds itself in the correct position. I was trying to hint at this in earlier posts, but had not yet described my intentions for these queues, so I imagine it didn't make much sense.

> Also will you stop it with the boost bitset thing. That's just something an specific ECS framework implementation uses.
Yes, but it's an ugly solution that has no prettier workaround. There are numerous problems with RTTI in general which are exhibited here and rectified using a bitset. it's not as if the solution I gave above is the epitome of perfection (facing facts, it has a bilinear running time for iteration, while the ideal solution would let you iterate linearly in the number of desired elements), but I want it to be clear that there is no perfect solution. Also, the above code does not provide a solution for [snip=CSharp](inst is class)[/snip], which would probably be as ugly as dynamic_cast (which is scowled upon), or boost::dynamic_bitset (upon which I scowl).

> OK, that's cool, but you would have to loop through every entity in the world and check each and every one of them.
Only over the components in which you are interested, in O(N) in the smallest component list if you like bitsets or RTTI, or in the sum of each entity count if you do not.

> In an ECS you are just passed an iterable with all the entities that have the required components and you are ready to go.
An iterator template class which does that would be trivial to implement from either of the above methods.

[Ideka]

Alright, that sounds pretty good.

The problem I'm seeing is in the methods you describe for finding all entities with certain components. They work fine for two components, but what if you have a system that requires five or ten or more?

[Josh @ Dreamland]

Then you have to check all ten components; it's the same in either system. Though, I suppose if you were using a bitset, that check can be made in O(1), but with a dynamic bitset, you're back up to O(n) (specifically, n / 32 or n / 64 checks). Of course, the compile-time approach isn't incompatible with a bitset, I just dislike the notion.

Knowing at compile time which combinations of components will be required can be used to allow toolkits such as ENIGMA to have children of each notable component combination add themselves to an appropriate list. If you would like something like that, it wouldn't be hard to add a feature for it.

I had an interesting plan for the layout of the new compiler which might allow doing that for specific games without bloating ENIGMA's compiler code at all.

[Ideka]

So your O(N) method is actually O(N * M), where M = 1 in the particular case you describe.
Why are you so set against using a dynamic bitset? And how is it a better idea to use a bunch of queues instead?