[MUD-Dev2] Entity Systems for MMO development

[Adam Martin]

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
post is going to try and explain the entity-system/MMO connection, and
the few brief conversations I've had with people about this so far
have been split between those who totally get it already and those who
totally don't get it at all.

So ... I thought it would be a good idea to bring it to MUD DEV and
try to iterate an explanation and understand better why some people
completely disagree.

For archival convenience, a full copy/paste follows (I believe this is
the preferred thing to do? maybe? I hope so! Apologies in advance if
not)

Adam
---

A few years ago, entity systems (or component systems) were a hot
topic. In particular, Scott Bilas gave a great GDC talk on using them
in the development of Dungeon Siege. The main advantages to entity
systems were:

    * No programmer required for designers to modify game logic
    * Circumvents the "impossible" problem of hard-coding all entity
relationships at start of project
    * Allows for easy implementation of game-design ideas that
cross-cut traditional OOP objects
    * Much faster compile/test/debug cycles
    * Much more agile way to develop code

I first started using entity systems in anger back in 2001-2003, when
I was working on MMOG server middleware. We were targetting the few
most painful problems in MMOG development, one of which was the
difficulty of constantly changing your game logic after launch, which
led us to entity systems. I learnt then that entity systems were an
almost perfect solution to massively speeding up the development time
for most MMOG's, and for also allowing almost unrestrained re-writing
of fundamental game features post-launch with very little effort.

That last issue is critical to the success of an MMOG: once an MMOG is
launched successfully, its long term success or failure depends more
upon the ability of the dev team to evolve that game into a better
game month after month than upon anything else.

I learned a lot from that first run-in with them, more about the
things that go wrong and what makes developing with entity systems
particularly hard than about the things that went right. We also
discovered that performance could easily become a major issue -
although they are very flexible and dynamic, the lack of pre-compiled
lookups and optimizations can make runtime performance disappointingly
(unacceptably) poor. Why? Mainly because of the amount of indirection
and checks needed to run even a single method call (but I'll go into
detail on that problem, and how to fix it, a bit later).

I moved on, and didn't think about them again, until last year. In
2006 I joined the Operation Flashpoint 2 team as the lead network
programmer, where we trying to make an MMO-FPS on an unprecedented
scale, and I discovered that the programming team was considering an
entity-system to drive the whole game. The attractions for the OFP2
team were different - mainly around the improvements to memory
management they could get from it, and the stream-oriented coding
(which is essential for PS3 development) - but it turned out to be
something of a silver bullet for the "MM" and "O" parts of the MMOFPS.
As the network programmer, discovering that an entity system was going
to be the interconnect for all other subsystems was a huge relief: the
entity system meant I could implement the complex latency hiding and
prediction techniques with minimal interference with the coding of all
the rest of the game systems. When you've got 20+ programmers on a
team, you really don't want to be placing yourself in a position where
you're going to have to redesign code for all of them just to make it
"network friendly".

whilst I was working on OFP2, I got in touch with Scott, and exchanged
ideas on what the future might hold for entity systems, including
additional uses for them, and on how to share this knowledge more
widely. He encouraged me to start a blog (and, actually, a year later
that was one of the main reasons I even started this blog, T=Machine),
so I figured now was a good time to start (finally) writing about
those entities :).

And to blame Scott for the existence of this blog?

Since then, I've been thinking a lot off and on about entity systems
and their appropriateness for use in MMOG development (again!). Only
this time around - thanks to OFP2 and some of the issues it threw up -
I had a much better idea how to use them to increase performance
rather than reduce it, and had come across some other major problems
that they conveniently solve. Most obviously, they work wonders for
PS3 development. Knowing how PS3's fundamental architecture works, I
can't immediately see how you'd want to use anything other than a full
entity system for game development. There's so much horsepower in that
beast that you can certainly write games many different ways, but it's
particularly well-suited to this approach.

As it stands, I'm beginning to think that next-generation MMOG's are
going to be practically impossible to develop unless based heavily
around a core entity-system. "practically" being the key word - unless
you're willing to spend $100 million for your development?

"Anything is possible", of course, so there'll be many exceptions to
that - but I think any team that doesn't go this route is going to
suffer a lot because of it.

I think most people would agree. But ? recent discussions on
game-industry mailing lists - and the experiences I had within games
companies with programmers who were much better at programming than I
was - made me realise that there's a lot of ignorance over these
systems, and many people aren't getting anywhere near the full
potential of them. So, if you're interested, read on?

I'll do this in a series of posts (it's going to take some time to
write it all up!), but it'll go something approximately like this:

    * Part 1 - intro (you're reading it)
    * Part 2 - what is an entity system
    * Part 3 - what can you do with your shiny new entity system
    * Part 4 - why are they so hard to understand
    * Part 5 - how to change your development process to use entity
systems efficiently

Part 2 - What is an Entity System?

(Part 1 is here)

Sadly, there's some disagreement about what exactly an Entity System
(ES) is. For some people, it's the same as a Component System (CS) and
even Component-Oriented Programming (COP). For others, it means
something substantially different. To keep things clear, I'm only
going to talk about Entity Systems, which IMHO are a particular subset
of COP. Personally, I think Component System is probably a more
accurate name given the term COP, but then COP is improperly named and
is so confusing that I find if you call these things Component Systems
they miss the point entirely. The best would be Aspect Systems, but
then AOP has already taken ownership of the Aspect word.

An entity system is simply a part of your program that uses a
particular way of breaking up the logic and variables of your program
into source code.

For the most part, it does this using the Component Oriented
Programming paradigm instead of the OOP paradigm - but there's
subtleties that we'll go into later.

We refer to an entity "system" instead of entity "programming" because
ES's are usually found embedded in a larger, OOP, program. They are
used to solve a subset of problems that OOP is poor at dealing with.

So, it is generally a replacement for Object Oriented Programming. The
two are mutually exclusive: you have to choose one or the other
(although any complex program may have multiple levels of abstraction,
and you could mix and match OOP and COP/ES at different layers, any
given layer is going to be one or the other (or, of course, any other
alternative way of structuring your program).

Common misconception #1 - Entity Systems are part of OOP
Common misconception #2 - Entity == Class, Component == Object

Where OOP has Classes and Objects, an ES has Entities and Components -
but it is very important to note that an Entity is NOT equivalent to a
class, and a Component is NOT equivalent to an Object, although
superficially they seem to share some characteristics. If you think of
Entities/Component's in OOP terms, you will never understand the ES,
and you will screw up any attempt to program with it.

The whole point of ES's using a different programming *paradigm* is
that this means there CAN NEVER BE a direct equivalent between Classes
and anything, or between Objects and anything - if there were, it
would actually be the same paradigm, and just be a variant of OOP.
It's not. It's fundamentally different and incompatible.
What's an Entity?

An Entity System is so named because Entities are the fundamental
conceptual building block of your system, with each entity
representing a different concrete in-game object. For every
discernible "thing" in your game-world, you have one Entity. Entities
have no data and no methods.

In terms of number of instances at runtime, they are like Objects from
OOP (if you have 100 identical tanks, you have 100 Entities, not 1).

However, in terms of behaviour, they are like classes (Entities
indirectly define all the behaviour of the in-game object - we'll see
how in a second).

So, entities on their own are pretty much entirely useless - they are
coarse-grained, and they serve to do little more than to tag every
coarse gameobject as a separate item. This is where Components come
in.
What's a Component?

Every in-game item has multiple facets, or aspects, that explain what
it is and how it interacts with the world. A bicycle, for instance,
is:

    * Made of metal
    * Can be used by a human
    * A means of transportation
    * Something that can be bought and sold
    * A popular birthday present
    * Man-made

At this point, please note: OOP does not have this concept of multiple
aspects; it hard-codes all the aspects into one glob, and declares
that the set of behaviours and values of data to be the
single-aspected Class of an Object. C++'s Multiple inheritance and
Java's Interfaces can get you a small part of the way towards the
aspects of an ES, but they quickly collapse under the strain in
fundamental ways that cannot be fixed within OOP.

The way that an Entity for an item represents the different aspects of
the item is to have one Component for each aspect. The Component does
one really important thing:

    * Labels the Entity as possessing this particular aspect

It may do several other things, depending upon your implementation and
the design of your ES. However, with an ES, this is the most
important, because this is the basis of all method execution and
processing.
What's a System? (or subsystem)

An ES goes further than OOP in how it splits up the universe of code
and data. In OOP, you make everything into Objects. With an ES, you
have two different things that you split code and data into: the first
is "Entity + Components", and the second is "Systems".

This is the source of a lot of the value of an ES. OOP is very good at
implementing the part of any program that has lots of data floating
around and lots of methods floating around which need to be executed
only on a small, instanced, subset of the data in the program. OOP is
very poor at implementing the "global" parts of a program, which have
to operate "on everything", or have to be invoked "from everywhere".
An Es solves this by explicitly dealing with all the global stuff
using Systems, which are outside the realm of Entity/Component.

Each System runs continuously (as though each System had it's own
private thread) and performs global actions on every Entity that
possesses a Component of the same aspect as that System.

There is a one to one relationship between Systems and AVAILABLE
aspects (i.e. types of Component). A System essentially provides the
method-implementation for Components of a given aspect, but it does it
back-to-front compared to OOP. OOP style would be for each Component
to have zero or more methods, that some external thing has to invoke
at some point. ES style is for each Component to have no methods but
instead for the continuously running system to run it's own internal
methods against different Components one at a time.

Typical Systems in a game would be: Rendering System, Animation
System, Input System, etc.

The Rendering system wakes up every 16 milliseconds, renders every
Entity that has the Renderable Component, and then goes back to sleep.

The Animation system constantly looks out for anything that would
trigger a new animation, or cause an existing animation to change
(e.g. player changes direction mid-step), and updates the data of each
affected Entity (of course, only those that actually have the
Animatable Component, i.e. are animations).

The Input system polls the gamepad, mouse, etc, and changes the state
of whichever Entities with the Inputable Component are currently
marked as being controlled by the player.

In tradtional OOP, if you have 100 units on a battlefield, and each is
represented by an object, then you theoretically have 100 copies of
each method that can be invoked on a unit. In practice, most OOP
languages use runtime and compiler optimizations to share those
methods behind the scenes and avoid wasting memory - although
scripting languages for instance often don't do any sharing, allowing
all the methods to be independently changed on each and every
instance.

By contrast, in an ES, if you have 100 units on a battlefield, each
represented by an Entity, then you have zero copies of each method
that can be invoked on a unit - because Entities do not contain
methods. Nor do Components contain methods. Instead, you have an
external system for each aspect, and that external system contains all
the methods that can be invoked on any Entity that possess the
Component that marks it as being compatible with this system.
That's not an Entity System!

Well ? at least, that's what *most* people I've worked with consider
to be an Entity System. But even within a single project, I've found
multiple different ideas of what an ES is, some of which are
compatible, others of which are incompatible. Here are some of the
other ideas I've come across that people thought were ES's.

Alternative definitions of entity systems:

1. An ES provides a different model of class-inheritance to OOP,
especially w.r.t inheritance of fields. For any given entity-class you
declare which aspects that class possesses, and the actual class is
looked-up at runtime by piecing together all the different aspects.

2. The same as 1., but taken literally for methods as well as fields,
i.e. this provides an interesting way to mix-n-match inheritance of
functions/methods. So long as methods are attached to the fields upon
which they operate, and/or a "pre-requisite" system is implemented
such that "having aspect X automatically causes you to also have
aspect Y", then this works quite smoothly. NB: this is implementing
"modular objects": the "aspects" are complete objects from the
standard theory of OOP.

3. A variant on 1. or 2. where the aspect data is pre-compiled into a
large number of OOP classes at compile time, so that at runtime you
are just running "normal" classes, without any lookup cost of the
dynamic "I've got an entity E which claims to have aspect X; just hold
on a sec while I build a function table to find out what the heck to
do now someone just tried to invoke function Z?"

4. A way of compiling standard OOP classes into runtime-data (note:
disassociating them from their OOP-ness) specifically so that you can
treat them as streamed data instead of chunked binary + data. The main
value of this is to play nicely with hardware that has tiny tiny
amounts of memory available in the code cache and/or very very slow
access to fetch extra code, but has vast bandwidth to stream
SEQUENTIAL data through the CPU. PlayStation consoles especially like
this approach, as opposed to the typical PC approaches. Note that in
this case, the idea is that the game-programmers and game-designers
are UNAWARE that there's an entity system - it's a runtime/compile
time performance optimization, not a design-feature.

5. A system design that revolves around excessive use of the Observer
pattern, but does so using standard OOP techniques. I mention this
because it's a common (ab)use of the concepts of ES's, but lacks much
of the advantages. For what it's worth ? that's the situation I was in
when I first discovered ES's. So, personally, I really don't count
these as ES's. These are not an ES, but an: "OMG, I need an ES!", but
many people persist in thinking (and claiming) they're a true ES.

NB: IMHO this is one of those "you really shouldn't do this" classes
of Entity System usage. Why? Because you end up just creating MASSIVE
OOP classes with tonnes of independent implemented Observer methods
tacked onto them. That's fine as a general approach, it buys you
something whilst remaining ENTIRELY OOP, but it also loses most of
what ES's have to offer, especially in the realm of flexibility and
compound inheritance.
Who cares about ES's and why? (where did they invent these from?)

1. Coders who are used to writing a graphics/rendering engine and
trying to keep it isolated / separate from the rest of the computer
game. They learnt that they can write the entire graphics engine using
only PARTIAL information (a couple of aspects - no more than 2 or 3)
of every OOP object that exists in the game-universe. They need to
use: Renderable (do I have to paint it to the screen every frame? [it
will have all the methods necessary to do that painting generically]),
Updateable (does it potentially change in response to one or more
game-loop-ticks? [animations are a great example of this - their
internal state changes independently of how many times they're
rendered]),

2. Multi-threaded coders who are looking at the concept of aspects per
se (i.e. Renderable as opposed to Updateable) to allow for
coarse-grained multi-threading: you are allowed one thread per aspect,
and this is guaranteed safe simply because the aspects are - by
definition! - independent from one another. Since a typical ES will
have a dozen or more aspects, you've just bought yourself reasonably
effective performance scaling of up to 12 separate CPU cores, for
free.

Also ? going to the next level of difficulty and performance
improvement, they're looking for the largest possible individual
(literally: things that "cannot be divided") things that can be made
the atomic level of multi-threading. The default position is that only
manually-hard-coded atomic operations count, and OOP objects certainly
are full of all sorts of multi-threading individual pieces so are far
too coarse, but maybe components within entities are small enough to
be the unit of atomicity.

3. Game designers who want to enable "everything to become anything".

Do Cameras shoot people?

Do Bullets accept input from the player?

No?

Well ? have you played Unreal Tournament? If you have but didn't
answer yes to the earlier questions then you need to find someone to
show you a Redeemer being used in Alternate Fire mode (hint: you get
to manually "fly by wire" the rocket from a first-person view inside
the warhead itself).

ES's allow everything and anything to be used as anything and
everything, interchangeably, with no re-coding. That's the beauty for
designers - all the artifical constraints on design that were
previously enforced by coders having to, you know, place SOME
constraints just to write their own damn code and have it be
reasonably performant and bug-free are suddenly lifted.

It's true - you really CAN have strongly-typed safe code and yet have
total freedom to pass any object to any method; at least, you can with
Entity Systems.

4. Coders who go a bit overboard with the Observer pattern.

If you're unsure about this one, and have used Observers a lot, ask
yourself this: have you ever had that problem with Observers where you
found that "just one base class isn't enough"? i.e. one base class
that implemented a handful of different Observers worked great, but as
your system / game / application expanded you found you needed more
variety in that base class, you needed multiple different versions,
and you needed *every possible combination* of those different
versions, because base-classes cannot/will not "stack" nicely on top
of each other.
Thought for the day

Programming *well* with Entity Systems is very close to programming
with a Relational Database. It would not be unreasonable to call ES's
a form of "Relation Oriented Programming".

This needs a followup post, but you might want to think about that :)
both in terms of how the above statement could be true (hint: think
about what most of the code you write for each System is going to look
like, and what exactly it is doing), and also in terms of what the
knock-on effects of this are if it is true.

Bear in mind that no-one's yet managed to do OOP fast with Relations;
the excessively high conversion cost between RDBMS and OOP - both at
coding-time and at runtime - is still one of the biggest single
development problems with writing an MMO.