By Nicolas MERCIER
[color="#555555"]There is so much wrong in the concept of "entities" today ... [a][color="#555555"] C++ object representing the state of an object in the world [color="#555555"]That object has an "update" method, that updates this entity and eventually recursively updates all entities/components lower in the "entity tree".[/quote]He goes describing the issues associated with that approach involving 1) parallelization, 2) self-documentation, 3) deep inheritance trees 4) constraints (update THAT before THIS).
He proposes, as solution
1,2,4) group updates by object type and update type (DOD like) 3) component model.
Ok, this makes a lot of sense. I was thinking about using interfaces so the inheritance tree would have been low but as interfaces come with no implementations I guess it's just better to switch to component-based anyway (there would have been a code of redundant code). And I was already going to pool those objects by type.
However, there are still some thinks I cannot quite figure out.
a) I don't see any way to avoid using [font="Courier New"]Update[/font][font="Arial"], nor propagation.[/font]
This is mostly referring to script-driven entities. The current "core entities" as I call them, are updated with a proper call and do not propagate in general, albeit some modify the values of certain other entities (in a way similar to multithreading or "volatile" values) because of the way they were implemented. But for script entities, I see no way to avoid this, besides forbidding. Maybe I can intercept all the calls and short-circuit them so each entity could be updated only once per frame, but I'm not sure.
b) I'm not quite sure what this "update type" thing even means.
Again, put in scripts. Can a scripted object register an update type? How? How they are pooled? Where? When to refresh? What?
c) Constraints.
The way I was going to deal with them was... uhm, fairly ugly I guess. It revolved around an object database driven by strings, a [font="Courier New"]getNamedObject[/font] call and casting like crazy (or build the objects using an helper script to connect them together). The script execution model was simply "no order guaranteed" so checking a condition could take a few frames. I don't think I'm going to have this problem anyway in the near future.
By Nicolas MERCIER
to sum up, can we get away from that entity tree concept NOW? =)[/quote]Which I guess it's ok as I never got the idea that entities should have been put in trees (I guess it's similar to my scene graph misunderstanding) but there's another thing which I cannot quite understand.
It comes from "Hodgman" and since it seems likely he's the same "Hodgman" here I'd like to ask to elaborate on:
By Brook Hodgman
...the very notion of a 'game entity' itself is fading as well. Having a single way to describe anything ("everything is an entity!") seems like a "well, we've always done it that way" design choice, instead of an actual requirement.[/quote]
I understand the sentiment behind the second statement as I'm having the very same problem (is a game entity collidable? visualized? has logic? is live/nonstatic?). So the whole point here is to have a family of entities instead to compose?
Since I'm going to tear apart the "entity" system yet another time, I suppose it would be a good time to think about "doing it right", so I'd like to hear anything that might come useful.
Demise of the "game entity".
Author
Surfing the net I stumbled on The Game Entity – Part I, A Retrospect. The post itself is quite open but a comment is fairly interesting, let me quote:
I understand the sentiment behind the second statement as I'm having the very same problem (is a game entity collidable? visualized? has logic? is live/nonstatic?). So the whole point here is to have a family of entities instead to compose?Yes. Imagine if all the standard-library objects had a common base type -- i.e. [font="Courier New"]std::string[/font], [font="Courier New"]std::iostream[/font] and [font="Courier New"]std::vector[/font] were all "entities"...
Why? Why would you do such a thing! They're completely different types that can be composed to make more complex types. There's no requirement for having an [font="Courier New"]Entity*[/font] which might point to either a [font="Courier New"]string[/font] or an [font="Courier New"]iostream[/font].
Likewise, if I've got some objects called "[font="Courier New"]game rule[/font]", "[font="Courier New"]animation controller[/font]" and "[font="Courier New"]AI path-finder[/font]", there's absolutely no need to try and force them all into some kind of common interface. They're all completely different types that can be composed to make more complex types. I don't need a base-class or an interface or whatever, here.
a) I don't see any way to avoid using [font="Courier New"]Update[/font][font="Arial"], nor propagation.[/font][/quote]Firstly, the "[font="Courier New"]virtual void Update[/font]" pattern is absolutely terrible for performance. You go through completely unknown objects one by one, executing unpredictable code and accessing unpredictable data for each one. You might update an AI character, then a projectile, then the weather, then another projectile, etc...
Imagine if other software worked like this! A bank that randomly walked through it's accounts checking each one if they've got new transactions... A calculator that checks if '7' was pressed, then updates part of the LCD, then checks if a square-root needs to be computed, then checks if '8' was pressed, etc... That is not a performant design.
Secondly, not everything needs to be "updated" every frame. E.g. a game-rule entity might only need to execute some code whenever a particular event happens -- this code can be triggered by that event, instead of polling for the event each frame, just because we like [font="Courier New"]Update[/font] functions.
A breakable object might only need to execute some code when it's bumped into -- instead of checking for collisions every frame in it's [font="Courier New"]Update[/font] function, the physics sub-system can instead produce an array of collision events during it's processing, then another sub-system can iterate over these results and calling the "[font="Courier New"]Breakable::Bump[/font]" function if required. No collisions generated means no updates of breakables (as opposed to checking each one each frame).b) I'm not quite sure what this "update type" thing even means.[/quote]This often means grouping by type, which addresses some of the performance problems of "[font="Courier New"]virtual void Entity::Update[/font]". Instead of the update method being unpredictable, you group your objects by type and just have "[font="Courier New"]void T::Update[/font]". You iterate through all your [font="Courier New"]Foo[/font] objects, calling [font="Courier New"]Foo::Update[/font], then your [font="Courier New"]Bar[/font] objects, calling [font="Courier New"]Bar::Update[/font], etc... Also, instead of having "[font="Courier New"]T::Update[/font]", you can instead write "[font="Courier New"]TSystem::UpdateMany[/font]", as usually you can write much better code when you're performing an operation on a large number of inputs/outputs, instead of writing code that only operates on a single item at a time (and then running it many, many times).c) Constraints.[/quote]Once your code is split up into a directed graph of jobs that need to be done (e.g. "simulate physics", "break bumped breakables", etc...) you can plot the data-dependencies between the jobs (e.g. "breaking bumped breakables" consumes the collision list, which is produced by "simulate physics") and then either manually or automatically create a dependency graph for your jobs, and execute them in the appropriate order.
Imagine if all the standard-library objects had a common base type -- i.e. [font="Courier New"]std::string[/font], [font="Courier New"]std::iostream[/font] and [font="Courier New"]std::vector[/font] were all "entities"...
Why? Why would you do such a thing! They're completely different types that can be composed to make more complex types. There's no requirement for having an [font="Courier New"]Entity*[/font] which might point to either a [font="Courier New"]string[/font] or an [font="Courier New"]iostream[/font].
I don't know much so I may be missing the point of the conversation here, but surely the purpose of an entity object is to serve as a base class so that all objects in the game can be held in the same container? Otherwise you have a list of trees, a list of monsters, a list of players, a list of particle systems etc., all with similar interfaces, but which need to be accessed seperately...
surely the purpose of an entity object is to serve as a base class so that all objects in the game can be held in the same container? Otherwise you have a list of trees, a list of monsters, a list of players, a list of particle systems etc., all with similar interfaces, but which need to be accessed seperately...Yes, that is the purpose, but it's an anti-pattern.
Does a tree really have the same interface as a monster? Do you really have a requirement to access both player data and particle-system data at the same time? Surely you want your particle-systems to be accessed separately than players? Can a player be safely substituted by a tree and have all player-related algorithms still function? This is just a horrible abuse of object oriented design done out of laziness, and as mentioned earlier, it's a great way to absolutely destroy the performance of your game, while not actually satisfying any real requirements.
Yes, that is the purpose, but it's an anti-pattern.
Does a tree really have the same interface as a monster? Do you really have a requirement to access both player data and particle-system data at the same time?
Yes, sometimes. Admittedly this system can get awkward, but without a common interface, what would prevent code like this from occurring?:
for (std::list<Tree>::iterator it = trees.begin(); it != trees.end(); ++it)
it->UpdateAnimation(dt);
for (std::list<Monster>::iterator it = monsters.begin(); it != monsters.end(); ++it)
it->UpdateAnimation(dt);
for (std::list<Player>::iterator it = players.begin(); it != players.end(); ++it)
it->UpdateAnimation(dt);
for (std::list<ParticleSystem>::iterator it = particleSystems.begin(); it != particleSystems.end(); ++it)
it->UpdateAnimation(dt);
Sure, everything would be stored in some form of scene graph rather than a list, but you get the idea. As soon as you add a new type of object you have to add special-case lines all over the code for purposes like this. I'm not arguing, just trying to understand.
I don't know if what MERCIER describes with update() is just a general example? I suppose if you didn't care about cache coherency this is how you would do it? It really seems wrong-headed to me and ignores data-oriented design principles.
Admittedly this system can get awkward, but without a common interface, what would prevent code like this from occurring? As soon as you add a new type of object you have to add special-case lines all over the code for purposes like this.The same [font="Courier New"]UpdateAnimation[/font] method shouldn't belong to trees, monsters, players and particle systems (separation of concerns). If that functionality is re-used by many different classes, then it should be packaged up into it's own class.
For example, if a monster needed a dynamically-sized vector, you don't go adding a [font="Courier New"]push_back[/font] method to the monster -- you add a [font="Courier New"]std::vector[/font] as a member variable of monster, and use it's [font="Courier New"]push_back[/font] method.
Likewise, if both players and monsters need an "animation", then you add an [font="Courier New"]animation[/font] as a member variable of player and monster.
All the animation objects for a scene can be kept track of seperately of the objects that own them (e.g. following the law of demeter, you should be able to update a player/monster's animation without even [font="'Courier New"]#include[/font]ing [font="'Courier New"]player.h[/font] or [font="'Courier New"]monster.h[/font]). If you add a new "Spaceship" class that also needs an animation, there's no need to give it an UpdateAnimation function, or to write a new loop like you've done. You just give it an animation member object, which is kept track of (and updated by) the animation-manager.
e.g.
class Player {
Animation* anim;
Player( AnimManager& am ) : anim( am.Create() ) {}
};
...
void AnimManager::UpdateAnimations()
{
for (std::vector<Animation>::iterator it = animations.begin(); it != animations.end(); ++it)
it->UpdateAnimation();
}You don't need a common interface at all -- all you need to do is pull that duplicated logic out into it's own class, following the single responsibility principle.Sure, everything would be stored in some form of scene graph rather than a list...[/quote]Once you've pulled all the animation data out into it's own isolated class, there's no reason to go putting it into some kind of 'scene graph'!! Just put it in an array, and put spatial objects in the spatial graph!
Does a tree really have the same interface as a monster? Do you really have a requirement to access both player data and particle-system data at the same time?Yes, sometimes.[/quote]That was a rhetorical question. If you break your classes up properly so they're not overflowing with different responsibilities, the answer is 'no'.
There might be some member variable of a player, which is the same type as a member variable in a particle-system (e.g. maybe they both have world-transformations) -- but this is not a part of the player and particle-system interfaces, this is the interface of one of the objects they've been composed out of.
So if you had an algorithm that operated on world-transformations, then as is, yes, you might have a need to iterate over both players and particle systems.
If you instead break that common interface out into it's own class (i.e. the world-transform class), then now your algorithm can iterate over a collection of world-transforms without caring if they belong to a player or a particle-system, without inheritance and without interfaces... and with much better performance...
C++...
A thought experiment. Let's make "an entity" in JavaScript.
Given entity, how do we know it's a car, that it's updatable and that it has speed? How to update the position? We don't have inheritance, interfaces, introspection (well), .... We have blobs.
But what we need to do is update all cars or perhaps update all entities with certain attribute or all with position. We lack a facility that would allow us to query such things. The simplest way is to do it manually:
How do we update? JS lacks set intersection, but let's pretend there is. To update "physics", one might do something like this:
Let's add a new entity:
And then... well, that is it. Really, this is all there is to the magic of entities. No joke. It's just that C++ is horribly complicated when attempting to explain something absurdly trivial. Above, there is nothing saying our entities cannot be JSON objects. Or copy-pasted. Or renamed. Or changed during run-time (as long as registeration is respected).
We have sets of data, intersections of which form our "entities".
And system described above would likely work just find for reasonable number of entities and properties. C++ implementation of above design just allows some further optimizations. But at very core, it's just set algebra, so learning SQL is a good idea. Not for syntax, but for concepts.
The "radical departure from OO" is quite trivial. We have plain state that is dumb. Then we have smart methods which know about *all state* and make the best of it. In OO, each instance knows about itself and is oblivious to everything else. Here, the caller specifies what they are interested in and what they need, select that subset and manipulate it (see above, we care about speed and position, nothing else, even though we could ask for more).
A thought experiment. Let's make "an entity" in JavaScript.
function Car(...) {
this.speed = 10;
this.position = [0,0,100];
}
var entity = new Car();
all_entities.push(entity);
Given entity, how do we know it's a car, that it's updatable and that it has speed? How to update the position? We don't have inheritance, interfaces, introspection (well), .... We have blobs.
But what we need to do is update all cars or perhaps update all entities with certain attribute or all with position. We lack a facility that would allow us to query such things. The simplest way is to do it manually:
var with_speed = [];
var with_position = [];
function Car(...) {
this.speed = 10;
this.position = [0,0,100];
with_speed.push(this);
with_position.push(this);
}10 lines of code. And I think it might even work.How do we update? JS lacks set intersection, but let's pretend there is. To update "physics", one might do something like this:
var s_and_p = set_intersect(with_speed, with_position);
for (e in s_and_p) {
e.position.x += e.speed;
}Voila...Let's add a new entity:
function Kettle {
this.position = [100, 100, -1];
with_position.push(this);
}Won't move, doesn't have speed.And then... well, that is it. Really, this is all there is to the magic of entities. No joke. It's just that C++ is horribly complicated when attempting to explain something absurdly trivial. Above, there is nothing saying our entities cannot be JSON objects. Or copy-pasted. Or renamed. Or changed during run-time (as long as registeration is respected).
We have sets of data, intersections of which form our "entities".
And system described above would likely work just find for reasonable number of entities and properties. C++ implementation of above design just allows some further optimizations. But at very core, it's just set algebra, so learning SQL is a good idea. Not for syntax, but for concepts.
The "radical departure from OO" is quite trivial. We have plain state that is dumb. Then we have smart methods which know about *all state* and make the best of it. In OO, each instance knows about itself and is oblivious to everything else. Here, the caller specifies what they are interested in and what they need, select that subset and manipulate it (see above, we care about speed and position, nothing else, even though we could ask for more).
That's a very intelligible example Antheus though I don't know Java.
The only thing though, it seems your with_speed and with_position are going to have pointers to all different places in memory, not a contiguous allocation? Many cache misses?
The only thing though, it seems your with_speed and with_position are going to have pointers to all different places in memory, not a contiguous allocation? Many cache misses?
That's a very intelligible example Antheus though I don't know Java.
Well, good news then. It's JavaScript.
The only thing though, it seems your with_speed and with_position are going to have pointers to all different places in memory, not a contiguous allocation? Many cache misses?[/quote]
Oh forget about that. Really. You're not working for DICE or Intel, so just ignore that for now. And it's JavaScript, so it's 10,000 times slower than C++ code could be. Yet I'm willing to bet it would work just find for reasonable number of entities.
Understand the design and the idea behind it first, especially why and how it departs from typical OO.
And it's JavaScript. Write a few more classes, then run it in browser. No IDE or anything needed, see how many entities you can get before things become a problem. 3 or 4 years ago, before all these fancy browsers I managed to replicated Dune 2 in browser. It was just barely doable for 4096 tile map and 250 units. Today it would probably fly at 60FPS. More if using Canvas or WebGL or such.
The whole "entity" doesn't even have a name, it's just how everyone in dynamic languages programs. This is why it's important to notice the "10 lines only" argument.
The original question was about design first and it didn't mention any performance mentrics, so it's not useful part of discussion. However, if you want to run 1000 entities with 20,000 properties at 60Hz on a 3GHz CPU, then one simply writes a benchmark and tunes until that is achieved. If memory optimization helps with that, fine, otherwise it's not important.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
