[MUD-Dev2] Re: Entity Systems for MMO development

[Adam Martin]

On 21/11/2007, Adam Martin <adam.m.s.martin at googlemail.com> wrote:
> http://tmachine1.dh.bytemark.co.uk/blog/index.php/2007/09/03/entity-systems-are-the-future-of-mmog-development-part-1/
> http://tmachine1.dh.bytemark.co.uk/blog/index.php/2007/11/11/entity-systems-are-the-future-of-mmog-development-part-2/
>
> I haven't got as far as explaining exactly *why* I think this
> development technique is so powerful for MMO development, but the next

The next part turned out a lot harder to explain than I thought it
would be, so I've taken a slight detour to answer some recurring
questions I've had from all over (email, face to face, blog comments,
etc).

http://tmachine1.dh.bytemark.co.uk/blog/index.php/2007/12/22/entity-systems-are-the-future-of-mmog-development-part-3/

Adam
---------------------------

Also known as: Nobody expects the Spanish Inquisition!

(because I'm now deviating from the original schedule I outlined in
Part 1; what the heck, it was only a rough agenda anyway?)
Questions, questions?

First of all, there's a bunch of good questions that have been raised
in response to the first two posts:

    * what data and methods are stored in the OOP implementation of an entity?
    * where does the data "live"?
    * how do you do object initialization?
    * what does the ES bring that cannot be accomplished with an AOP framework?
    * what's the link between entity systems and SQL/Relational
Databases? (OK, so that one's my own question from last time)
    * what, exactly, is an entity?

Let's start with that last one first.
What, exactly, is an entity?

Obviously, I've already covered this from the conceptual perspective
in the last post, where I defined them as:

    For every discernible thing in your game-world, you have one
Entity. Entities have no data and no methods

Great. But a couple of people were wondering what ACTUALLY is it, when
you start implementing the thing? Is it a class? Is it an array of
data? Is it a list of Components?

The last statement is particularly important: actually, entities have
NO data and NO methods - an entity is not a stub for a class, it is
not a struct of data, and - ideally - it's not a list of Components.
An entity is really just a name. Last post I also wrote that entities
"do little more than to tag every gameobject as a separate item" - and
that's the key thing here, an entity is just a unique label for an
in-game object.

I was a bit non-specific, because I didn't want to say empirically
that an entity cannot or should not be a list of components - sure,
you CAN implement it that way - because many people do implement
entities like that, and who's to say what's right or wrong here?

Although?I actually think that *is* the wrong way, and think that by
the time you get to the last of these Entity Systems posts, you'll
probably agree with me ;). The problem is, the right way is usually
too slow, so you'll probably end up *to some extent* implementing
entities as lists anyway, but if you do so as a performance
optimization (e.g. by hiding that detail from the rest of the system)
rather than as a logical implementation, it'll cause fewer problems
with your code in the long term.

So, to answer the question directly:

    What is an entity?

    An Entity is a number (a globally unique number)

Remembering, of course, that a String - or any other kind of unique
label - is merely a fancy kind of number, not just in terms of how
computers implement them, but in terms of how Mathematicians think of
them. People tend to think that strings have extra features, for
instance you can encode trees within strings easily
("root.node1.leaf", for instance - as used in most OOP languages
derived from C to navigate the namespace of classes, methods, etc) -
although of course you can encode things like that in numbers, too,
for instance "123045607? (using 0 to stand for the dot? i.e.
"123.456.7?). But ? you *really* don't want to do this!

    Gotcha number 1: only OOP programmers want to give entities
hierarchical names. It can tunr out a pretty dumb idea, if you think
about it: it's usually an implicit refusal to let go of those OOP ways
we're so used to thinking in, when those OOP ways are exactly what
caused most of the problems we're trying to fix by using ES's.

So, don't be tempted into hierarchical encoding, and definitely don't
do ANY encoding in the entity names - there's a much BETTER place to
do metadata for entities (trust me).

And I'll be calling the implementation of an entity a GUID from now on
("Globally Unique IDentifier").
What data and methods are stored in the OOP implementation of an entity?

The answer for the previous question makes this one easy to answer:
none. The entity is merely a label, and whilst you DO want to store
and manipulate some metadata around that label (e.g. it's kind of
handy to have a list of all the entity names you've currently got in
memory, and be able to rename them without breaking everything), you
should be thinking of them as nothing more or less than a GUID
(String. Number. Whatever!).
Where does the data "live"?

The first time I made an ES, I implemented the individual Entities as
classes, and although I didn't put any methods in those classes (that
would just be bog-standard OOP!), I did put the data into them. It
didn't occur to me that I'd need to worry about where the data was
living, so I just stuck it somewhere natural - in the Entity.

Of course, I'd made a cardinal error, because whatever feels "natural"
to an OOP programmer is usually "completely wrong" in ES programming.

Anyway, the last time I did an ES I was a lot wiser, and so we put the
data inside the Components. All of it.

    Gotcha 2: ALL the data goes into the Components. ALL of it. Think
you can take some "really common" data, e.g. the x/y/z co-ords of the
in-game object, and put it into the Entity itself? Nope. Don't go
there. As soon as you start migrating data into the Entity, you've
lost. BY DEFINITION the only valid place for the data is inside the
Component

How does that work?

Well, you need to start thinking about your Components a bit more
carefully here. I previously said that:

    A Component labels the Entity as possessing this particular aspect

So, again, a Component is merely another "label", just like the Entity
itself. Right? Wrong. This is my fault - in the last post, I was
trying to Keep It Simple for you, and glossed over quite a few things;
because the very first ES I made, I treated the components as mere
labels, that description came out most easily as "the simple version"
of what they are. In more detail:

    A Component is the chunk of stuff that provides a particular
aspect to any Entity

?where "provides" means "does all the things that are necesssary to
make this work". Which means that all your Components certainly
*could* be implemented as standard OOP objects. To define an Entity,
you just provide a name (GUID) and a list of Component classes that it
needs, and to instantiate that Entity, you just instantiate one object
from each class (and then you need to somehow attach those in-memory
objects to your GUID, probably by implementing the Entity as an empty
class that just contains a GUID and a list-of-component-instances
(which I said to avoid, but we'll come back to that later)).

But, as you may have noticed by now, I'm vigourously against using OOP
anywhere inside an ES implementation. This isn't some strange dislike
of OOP itself, it's just that in my experience with ES development
it's all too easy for experienced OOP programmers to keep trying to
sneak some OOP back in where it's inappropriate, and it's all too easy
to delude yourself into thinking this is a Good Idea. And, worse, from
the teams I've worked on in the past, it has consistently seemed that
the better you are at OOP programming, the harder this is to resist?

You COULD implement your Components as OOP objects. But, really, if
you go back to the definition of a "System" from the last post, you'll
see that the methods for acting upon Components should all live inside
the Systems, not the Components. In fact, re-reading that last post, I
notice that I explicitly described Systems as doing exactly this: "a
System essentially provides the method-implementation for Components".

One tiny exception to this rule: getters and setters are really
useful. If you're implementing your ES within an OOP language, you
might allow yourself to implement Components as objects just to get
the benefits of get/set and e.g. multiple different versions of each
get/set that do basic type conversion, or integrity checking on data,
etc. Be warned, though, that if you do you MUST implement them as
flyweight objects (go google the Flyweight Pattern if you don't know
it) or else you'll lose lots of the memory-management and efficiency
advantages of a full ES.

    Where does the data "live"?

    Each Component is merely a classification label (e.g.
"Renderable") and a struct/array/list/whatever of the data relating to
it's purpose; all data lives in Components; ALL data.

How do you do gameobject initialization?

Here's a fun one - I haven't mentioned ANYTHING about object/entity
intialization. It was really only from trying to use entity systems
that I finally realized just how bizarre OOP is when it comes to
initialization: you have some "magic methods" (constructor,
destructor, finalizer, etc) that have nothing to do with the main
description of OOP, but instead are part of a meta-programming that
allows you to get your OOP system up and running, and to keep it
running, and then to tear it all down again at the end. Until then,
I'd not noticed how out-of-place those methods are?

Hats-off to the OOP folks: they integrated their meta-programming so
neatly into OOP that in most languages it's unnoticeable. But I've not
yet seen the same trick done for an ES - so, get used to the fact that
initialization is going to be a bit ? "different" ?

There's really a bunch of issues here:

    * what's the technical term for an entity's archetype?
    * how do you define the archetypes for your entities?
    * how do you instantiate multiple new entities from a single archetype?
    * how do you STORE in-memory entities so that they can be
re-instantiated later on?

What's the technical term for an entity's archetype?

There doesn't seem to be one. Really. There's a couple floating
around, influenced by people's own backgrounds but I've heard quite a
few used interchangeably.

My favourites are:

    * template
    * model
    * assemblage

(I actually picked the last one from a thesaurus - looking for
equivalents of "class" ;)).

The problem with both "template" and "model" is that they're both very
frequently used generic terms in programming. Entity is pretty good as
a term, because it's hardly used for anything else (and the main
obvious competitor is now widely called a "gameobject" by game
programmers). I've used both, in the past. Interchangeably. (cackle!)

So. "Assemblage", anyone?

    how do you define the archetypes for your entities?
    how do you instantiate multiple new entities from a single archetype?
    how do you STORE in-memory entities so that they can be
re-instantiated later on?

    Big topics. Really big. Too big to go into here (ah. Now I know
what the next post is going to be about?).

What does the ES bring that cannot be accomplished with an AOP framework?

The simple, facetious, answer is: almost everything.

AOP (Aspect-Oriented Programming) doesn't really help much to solve
the problems that an Entity System solves (although it does solve
similar ones that ALSO tend to be present when the ES-related ones are
present), and doesn't provide the new features that you get from an ES
(e.g. the improved memory/data-performance).

An ES takes a system where there are many things going on that are all
independent, which OOP tangles up together, and pulls them apart and
lets them live on their own. It also highly efficiently manages simple
interoperation between those disparate aspects of the program, and
allows them to be disconnected, reconnected, at will.

AOP takes a system where there are things going on that are
fundamentally DEPENDENT, which OOP tangles up together, and allows
them to be reasoned about "separately, but together" - you can view
the code for logging independent of the code which is being logged,
but you have to still reason about them at the same time, you cannot
merely ignore one or the other. By definition, different aspects
(vested as Components) of an Entity are INdependent, and this whole
"together" thing is an irrelevance.

However ? AOP certainly helps if you have implemented with OOP
something you ideally should have done with an ES, and you want to add
new features to it, because the tangled OOP system is going to be a
pain to modify without breaking stuff accidentally, and AOP will help
you more precisely focus the impact of your changes. But it's a poor
replacement for just implementing the ES you wanted in the first
place.

There is also a fairly large area of crossover between "some things
you can do with entity systems" and "some things you can do with
aspect oriented programming", mainly because they are both
fundamentally data-driven at the function-despatch level (which I'll
come back to later). However, they each use this data-drivenness in
very different ways - AOP uses it to react to, and wrap itself around,
the code of the program, whereas an ES uses it to react to the data of
the program.

Using both together could be really exciting - but I've not been brave
enough to try that yet myself.
What's the link between entity systems and SQL/Relational Databases?

You might have guessed this by now - it's been the theme of most of
the answers above, starting from the very beginning of this post.

Mathematically-speaking, an Entity is a database Key, just as you'd
see in any RDBMS.

Likewise, from a purely abstracted point of view, the "set of
component-instances that comprise Entity #7742? is, literally, a
database Query.

THIS is why I said at the start that, ideally, you do NOT want to
store your component-instances as a list inside a struct/class
representation of each Entity. Fundamentally, that set is NOT defined
as a list (a list is a static thing, it's members don't change without
you changing them), it's defined as a query (whose members are always
changing, whether you want them to or not), and using one where really
you wanted the other tends to cause problems in the long term.

Obviously, you can use Lists as a simple form of query (that query
being "what things are currently in this list"), but that's a rather
poor and inflexible kind of query. Life is much more interesting if
you embrace the dynamicity of the query, and fetch the components
(and, hence, the VALUES of the data?) by running a query every time
you want one or more of them.

This is a fairly star-gazing view of how to make games: the game is
just one giant database, running dynamic queries all the time. Current
performance, even of fast RDBMS's, is just way too slow to be running
thousands of queries per frame on a home PC.

However, these articles are about ES's for massively multiplayer
online game development, not just standard game development, and that
changes two things in particular:

1. Most of the game is NOT running on home PC's, it's running on
arbitrarily beefy server-farms that are already running bajillions of
QL queries (nearly always SQL these days, but any of MS SQL Server,
Oracle, or MySQL).

2. The data is much much more important than rendering speed; we have
almost no problem making incredibly beautiful 3D rendered landscapes,
but managing the data to make those landscapes act and react as if
they were real (i.e. world-logic, game-logic, etc) is something we
still find rather hard
A new thought for the day?

Think what you can do with an ES if you deploy it on an MMO server
farm, and go the full monty by making all your entity/component
aggregations stored merely as SQL queries. Here's some to start you
off?

1. No more pain from "Relational vs OOP"

One of the slowest parts of MMO server performance is translating OOP
objects into RDBMS tables so that the database can save them, and then
translating them back again when the game needs to read them. This
also wastes large amounts of programmer time on boring, annoying,
tricky to maintain code to handle the serialization processes.

2. Massive increase in parallelization for free

If you make all processing data-driven, and you have no
data-structures that have to remain synchronized, then it becomes a
lot easier to "just add more CPU's" to increase runtime performance?

3. Where else could you use SELECT instead of data structures?

When each System has to do it's processing, it's probably going to
iterate over "all Entities that have my Component". Is that something
you can store easily in a standard data-structure? Or is it better off
as a QL query? And what else can you achieve if you start doing your
processing this way? (hint: there's some nice benefits for the
low-level network programming here?)