Category Archives: entity systems

Unconference on Entity Systems – Pre-Signup

Entity Systems are widely used in gamedev and starting to appear in mainstream IT / software development. But we want MORE developers and designers to benefit from this…

So, Richard Lord and I are going to do a mini conference on ES ideas/designs/uses/implementation/etc.

I’ll arrange venue, agenda (e.g. a Keynote) – but this will be an Unconference, so most/all sessions will be interactive, freeform, with no fixed Speakers.

To book a venue, I need an idea of numbers. So, if you’d like to come, please fill out this google form. Note: I’m planning to do this in Brighton, (UK) – less than 30 minutes from an International Airport (Gatwick).

https://docs.google.com/forms/d/156Sb9Qhx4RIX1d0BZg_22MVlUSoUb-gRqwrOq0zeT-w/viewform

Key info:

  • Date: Summer/Autumn 2014
  • Location: Brighton, UK
  • Cost: minimal (depends on demand + venue)

Your best links and articles on Entity Systems / Component Systems

The Entity Systems wiki is pretty good – simple source-code examples in 5 different languages, and links to 10 x richer, more complex “frameworks”.

But it’s got little (almost nothing) in links to articles, introductions, tutorials on the topic. I know there’s a lot that’s been written – just look at all the trackbacks on my old ES blog posts.

Let’s fill out a page on the wiki with tutorials, techniques, etc. What are your favourites (and can you give a 1-sentence summary of what each one does well?)

Data Structures for Entity Systems: Contiguous memory

This year I’m working on two different projects that need an Entity System (ES). One of them is a non-game app written natively on iOS + Android. The other is an FPS in Unity3D.

There are good, basic Open-Source ES’s out there today (and c.f. the sidebar there). I tried porting a few, but none of them were optimized for performance, and most of them were too tightly coupled to a single programming language or platform. I’ve started a new ES of my own – Aliqua.org – to fix these problems, and I’m already using it in an app that’s in alpha-testing.

I’ll be blogging experiences, challenges, and ideas as I go.

Background: focus on ES theory, or ES practice?

If you’re new to ES’s, you should read my old blog posts (2007 onwards), or some of the source code + articles from the ES wiki.

My posts focussed on theory: I wanted to inspire developers, and get people using an ES effectively. I was fighting institutionalised mistakes – e.g. the over-use of OOP in ES development – and I wrote provocatively to try and shock people out of their habits.

But I avoided telling people “how” to implement their ES. At the extreme, I feared it would end up specifying a complete Game Engine:

…OK. Fine. 7 years later, ES’s are widely understood and used well. It’s time to look at the practice: how do you make a “good” ES?

NB: I’ve always assumed that well-resourced teams – e.g. AAA studios – need no help writing a good ES. That’s why I focussed on theory: once you grok it, implementation concerns are no different from writing any game-engine code. These posts are aimed at non-AAA teams: those who lack the money (or expertise) to make an optimized ES first time around.

For my new ES library, I’m starting with the basics: Data Structures, and how you store your ES data in memory.

Where you see something that can be done better – please comment!

Aside on Terminology: “Processors, née Systems”

ES “Systems” should be batch-processing algorithms: you give them an array/stream of homogeneous data, and they repeat one algorithm on each row/item. Calling them “Processors” instead of “Systems” reduces confusion.

Why care about Data Structures?

There is a tension at the heart of Entity Systems:

  • In an ES game, we design our code to be Functional: independent, data-oriented, highly efficient for streaming, batching, and multi-threaded execution. Individual Processors should be largely independent, and easy to split out onto different CPU cores.
  • With the “Entity” (ID) itself, we tie those Functional chunks together into big, messy, inter-dependent, cross-functional … well, pretty much: BLOBs. And we expect everything to Just Work.

If our code/data were purely independent, we’d have many options for writing high-performance code in easy ways.

If our data were purely chunked, fixed at compile-time, we’d have tools that could auto-generate great code.

But combining the two, and muddling it around at runtime, poses tricky problems. For instance:

  1. Debugging: we’ve gone from clean, separable code you can hold in your head … to amorphous chunks that keep swelling and contracting from frame-to-frame. Ugh.
  2. Performance: we pretend that ES’s are fast, cache-efficient, streamable … but at runtime they’re the opposite: re-assembled every frame from their constituent parts, scattered all over memory
  3. Determinism: BLOBs are infamously difficult to reason about. How big? What’s in them? What’s the access cost? … we probably don’t know.

With a little care, ES’s handle these challenges well. Today I’m focussing on performance. Let’s look at the core need here:

  • Each frame, we must:
    1. Iterate over all the Processors
    2. For each Processor:
      1. Establish what subset of Entity/Component blobs it needs (e.g. “everything that has both a Position and a Velocity”)
      2. Select that from the global Entity/Component pool
      3. Send the data to the CPU, along with the code for the Processor itself

The easiest way to implement selection is to use Maps (aka Associative Arrays, aka Dictionaries). Each Processor asks for “all Components that meet [some criteria]“, and you jump around in memory, looking them up and putting them into a List, which you hand to the Processor.

But Maps scatter their data randomly across RAM, by design. And the words “jump around in memory” should have every game-developer whimpering: performance will be bad, very bad.

NB: my original ES articles not only use Maps, but give complete source implementations using them. To recap: even in 2011, Android phones could run realtime 30 FPS games using this. It’s slow – but fast enough for simple games

Volume of data in an ES game

We need some figures as a reference point. There’s not enough detailed analysis of ES’s in particular, so a while back I wrote an analysis of Components needed to make a Bomberman clone.

…that’s effectively a high-end mobile game / mid-tier desktop game.

Reaching back to 2003, we also have the slides from Scott’s GDC talk on Dungeon Siege.

…that’s effectively a (slightly old) AAA desktop game.

From that, we can predict:

  • Number of Component-types: 50 for AA, 150 for AAA
  • Number of unique assemblages (sets of Component-types on an Entity): 1k for AA, 10k for AAA
  • Number of Entities at runtime: 20k for AA, 100k for AAA
  • Size of each Component in bytes: 64bits * 10-50 primitives = 100-500 bytes

How do OS’s process data, fast?

In a modern game the sheer volume of data slows a modern computer to a crawl – unless you co-operate with the OS and Hardware. This is true of all games. CPU and RAM both run at a multiple of the bus-speed – the read/write part is massively slow compared to the CPU’s execution speed.

OS’s reduce this problem by pre-emptively reading chunks of memory and caching them on-board the CPU (or near enough). If the CPU is processing M1, it probably wants M2 next. You transfer M2 … Mn in parallel, and if the CPU asks for them next, it doesn’t have to wait.

Similarly, RAM hardware reads whole rows of data at once, and can transfer it faster than if you asked for each individual byte.

Net effect: Contiguous memory is King

If you store your data contiguously in RAM, it’ll be fast onto the Bus, the CPU will pre-fetch it, and it’ll remain in cache long enough for the CPU(s) to use it with no extra delays.

NB: this is independent of the programming-language you’re using. In C/C++ you can directly control the data flow, and manually optimize CPU-caching – but whatever language you use, it’ll be compiled down to something similar. Careful selection and use of data-structures will improve CPU/cache performance in almost all languages

But this requires that your CPU reads and writes that data in increasing order: M1, M2, M3, …, M(n).

With Data Structures, we’ll prioritize meeting these targets:

  1. All data will be as contiguous in RAM as possible; it might not be tightly-packed, but it will always be “in order”
  2. All EntitySystem Processors will process their data – every frame (tick) – in the order it sits in RAM
    • NOTE: a huge advantage of ES’s (when used correctly) is that they don’t care what order you process your gameobjects. This simplifies our performance problems
  3. Keep the structures simple and easy to use/debug
  4. Type-safety, compile-time checks, and auto-complete FTW.

The problem in detail: What goes wrong?

When talking about ES’s we often say that they allow or support contiguous data-access. What’s the problem? Isn’t that what we want?

NB: I’ll focus on C as the reference language because it’s the closest to raw hardware. This makes it easier to describe what’s happening, and to understand the nuances. However, these techniques should also be possible directly in your language of choice. e.g. Java’s ByteBuffer, Objective-C’s built-in C, etc.

Usually you see examples like a simple “Renderer” Processor:

  • Reads all Position components
    • (Position: { float: x, float y })
  • Each tick, draws a 10px x 10px black square at the Position of each Component

We can store all Position components in a tightly-packed Array:

compressed-simple-array

This is the most efficient way a computer can store / process them – everything contiguous, no wasted space. It also gives us the smallest possible memory footprint, and lets the RAM + Bus + CPU perform at top speed. It probably runs as fast or faster than any other engine architecture.

But … in reality, that’s uncommon or rare.

The hard case: One Processor reads/writes multiple Component-types

To see why, think about how we’d update the Positions. Perhaps a simple “Movement” Processor:

  • Reads all Position components and all Velocity components
    • (Position: { float: x, float y })
    • (Velocity: { float: dx, float dy })
  • Each tick, scales Velocity.dx by frame-time, and adds it to Position.x (and repeats for .dy / .y)
  • Writes the results directly to the Position components

“Houston, we have a problem”

This is no longer possible with a single, purely homogeneous array. There are many ways we can go from here, but none of them are as trivial or efficient as the tight-packed array we had before.

Depending on our Data Structure, we may be able to make a semi-homogeneous array: one that alternates “Position, Velocity, Position, Velocity, …” – or even an array-of-structs, with a struct that wraps: “{ Position, Velocity }”.

…or maybe not. This is where most of our effort will go.

The third scenario: Cross-referencing

There’s one more case we need to consider. Some games (for instance) let you pick up items and store them in an inventory. ARGH!

…this gives us an association not between Components (which we could handle by putting them on the same Entity), but between Entities.

To act on this, one of our Processors will be iterating across contiguous memory and will suddenly (unpredictably) need to read/write the data for a different Entity (and probably a different ComponentType) elsewhere.

This is slow and problematic, but it only happens thousands of times per second … while the other cases happen millions of times (they have to read EVERYTHING, multiple times – once per Processor). We’ll optimize the main cases first, and I’ll leave this one for a later post.

Iterating towards a solution…

So … our common-but-difficult case is: Processors reading multiple Components in parallel. We need a good DS to handle this.

Iteration 1: a BigArray per ComponentType

The most obvious way forwards is to store the EntityID of each row into our Arrays, so that you can match rows from different Arrays.

If we have a lot of spare memory, instead of “tightly-packing” our data into Arrays, we can use the array-index itself as the EntityID. This works because our EntityID’s are defined as integers – the same as an array-index.

rect3859

Usage algorithm:

  • For iterating, we send the whole Array at once
  • When a Processor needs to access N Components, we send it N * big-arrays
  • For random access, we can directly jump to the memory location
    • The Memory location is: (base address of Array) + (Component-size * EntityID)
    • The base-address can easily be kept/cached with the CPU while iterating
    • Bonus: Random access isn’t especially random; with some work, we could optimize it further

Problem 1: Blows the cache

This approach works for our “simple” scenario (1 Component / Processor). It seems to work for our “complex” case (multiple Components / Processor) – but in practice it fails.

We iterate through the Position array, and at each line we now have enough info to fetch the related row from the Velocity array. If both arrays are small enough to fit inside the CPU’s L1 cache (or at least the L2), then we’ll be OK.

Each instance is 500 bytes
Each BigArray has 20k entries

Total: 10 MegaBytes per BigArray

This quickly overwhelms the caches (even an L3 Cache would struggle to hold a single BigArray, let alone multiple). What happens net depends a lot on both the algorithm (does it read both arrays on every row? every 10th row?), and the platform (how does the OS handle RAM reads when the CPU cache is overloaded?).

We can optimize this per-platform, but I’d prefer to avoid the situation.

Problem 2: memory usage

Our typeArray’s will need to be approimately 10 megabytes each:

For 1 Component type: 20,000 Entities * 50 variables * 8 bytes each = 8 MB

…and that’s not so bad. Smaller components will give smaller typeArrays, helping a bit. And with a maximum of 50 unique ComponentTypes, we’ve got an upper bound of 500 MB for our entire ES. On a modern desktop, that’s bearable.

But if we’re doing mobile (Apple devices in 2014 still ship with 512 MB RAM), we’re way too big. Or if we’re doing dynamic textures and/or geometry, we’ll lose a lot of RAM to them, and be in trouble even on desktop.

Problem 3: streaming cost

This is tied to RAM usage, but sometimes it presents a bottleneck before you run out of memory.

The data has to be streamed from RAM to the CPU. If the data is purely contiguous (for each component-type, it is!), this will be “fast”, but … 500 MB data / frame? DDR3 peaks around 10 Gigabytes / second, i.e.:

Peak frame rate: 20 FPS … divided by the number of Processors

1 FPS sound good? No? Oh.

Summary: works for small games

If you can reduce your entity count by a factor of 10 (or even better: 100), this approach works fine.

  • Memory usage was only slightly too big; a factor of 10 reduction and we’re fine
  • CPU caching algorithms are often “good enough” to handle this for small datasets

The current build of Aliqua is using this approach. Not because I like it, but because it’s extremely quick and easy to implement. You can get surprisingly far with this approach – MyEarth runs at 60 FPS on an iPad, with almost no detectable overhead from the ES.

Iteration 2: the Mega-Array of Doom

Even on a small game, we often want to burst up to 100,000+ Entities. There are many things we could do to reduce RAM usage, but our biggest problem is the de-contiguous data (multiple independent Arrays). We shot ourselves in the foot. If we can fix that, our code will scale better.

es-datastructures-structured-bigarray

In an ideal world, the CPU wants us to interleave the components for each Entity. i.e. all the Components for a single Entity are adjacent in memory. When a Processor needs to “read from the Velocity and write to the Position”, it has both of them immediately to hand.

Problem 1: Interleaving only works for one set at a time

If we interleave “all Position’s with all Velocity’s”, we can’t interleave either of them with anything else. The Velocity’s are probably being generated by a different Processor – e.g. a Physics Engine – from yet another ComponentType.

mega-array

So, ultimately, the mega-array only lets us optimize one Processor – all the rest will find their data scattered semi-randomly across the mega-array.

NB: this may be acceptable for your game; I’ve seen cases where one or two Processors accounted for most of the CPU time. The authors optimized the DS for one Processor (and/or had a duplicate copy for the other Processor), and got enough speed boost not to worry about the rest

Summary: didn’t really help?

The Mega Array is too big, and it’s too interconnected. In a lot of ways, our “lots of smaller arrays – one per ComponentType” was a closer fit. Our Processors are mostly independent of one another, so our ideal Data Structure will probably consist of multiple independent structures.

Perhaps there’s a halfway-house?

Iteration 3: Add internal structure to our MegaArray

When you use an Entity System in a real game, and start debugging, you notice something interesting. Most people start with an EntityID counter that increases by 1 each time a new Entity is created. A side-effect is that the layout of components on entities becomes a “map” of your source code, showing how it executed, and in what order.

e.g. With the Iteration-1 BigArrays, my Position’s array might look like this:

rect3859

  1. First entity was an on-screen “loading” message, that needed a position
  2. BLANK (next entity holds info to say if loading is finished yet, which never renders, so has no position)
  3. BLANK (next entity is the metadata for the texture I’m loading in background; again: no position)
  4. Fourth entity is a 3d object which I’ll apply the texture to. I create this once the texture has finished loading, so that I can remove the “loading” message and display the object instead
  5. …etc

If the EntityID’s were generated randomly, I couldn’t say which Component was which simply by looking at the Array like this. Most ES’s generate ID’s sequentially because it’s fast, it’s easy to debug (and because “lastID++;” is quick to type ;)). But do they need to? Nope.

If we generate ID’s intelligently, we could impose some structure on our MegaArray, and simplify the problems…

  1. Whenever a new Entity is created, the caller gives a “hint” of the Component Types that entity is likely to acquire at some time during this run of the app
  2. Each time a new unique hint is presented, the EntitySystem pre-reserves a block of EntityID’s for “this and all future entities using the same hint”
  3. If a range runs out, no problem: we add a new range to the end of the MegaArray, with the same spec, and duplicate the range in the mini-table.
  4. Per frame, per Processor: we send a set of ranges within the MegaArray that are needed. The gaps will slow-down the RAM-to-CPU transfer a little – but not much

es-datastructures-structured-megaarray

Problem 1: Heterogeneity

Problem 1 from the MegaArray approach has been improved, but not completely solved.

When a new Entity is created that intends to have Position, Velocity, and Physics … do we include it as “Pos, Vel”, “Pos, Phys” … or create a new template, and append it at end of our MegaArray?

If we include it as a new template, and insist that templates are authoritative (i.e. the range for “Pos, Vel” templates only includes Entities with those Components, and no others) … we’ll rapidly fragment our mini-table. Every time an Entity gains or loses a Component, it will cause a split in the mini-table range.

Alternatively, if we define templates as indicative (i.e. the range for “Pos, Vel” contains things that are usually, but not always Pos + Vel combos), we’ll need some additional info to remember precisely which entities in that range really do have Pos + Vel.

Problem 2: Heterogeneity and Fragmentation from gaining/losing Components

When an Entity loses a Component, or gains one, it will mess-up our mini-table of ranges. The approach suggested above will work … the mini-table will tend to get more and more fragmented over time. Eventually every range is only one item long. At that point, we’ll be wasting a lot of bus-time and CPU-cache simply tracking which Entity is where.

NB: As far as I remember, it’s impossible to escape Fragmentation when working with dynamic data-structures – it’s a fundamental side effect of mutable data. So long as our fragmentating problems are “small” I’ll be happy.

Problem 3: Heterogeneity and Finding the Components within the Array

If we know that “Entity 4″ starts at byte-offset “2048″, and might have a Position and Velocity, that’s great.

But where do we find the Position? And the Velocity?

They’re at “some” offset from 2048 … but unless we know all the Components stored for Entity 4 … and what order they were appended / replaced … we have no idea which. Raw array-data is typeless by nature…

Iteration 4: More explicit structure; more indexing tables

We add a table holding “where does each Entity start”, and tables for each Component stating “offset for that Component within each Entity”. Conveniently, this also gives us a small, efficient index of “which Entities have Component (whatever)”:

es-datastructures-structured-megaarray-by-component

Problem 1: non-contiguous data!

To iterate over our gameobjects, we now need:

  • One big mega-array (contiguous)
  • N x mini arrays (probably scattered around memory)

Back to square one? Not quite – the mini-arrays are tiny. If we assume a limit of 128,000 entities, and at most 8kb of data for all Components on an Entity, our tables will be:

[ID: 17bits][Offset: 13 bits] = 30 bits per Component

…so that each mini-array is 1-40 kB in size. That’s small enough that several could fit in the cache at once.

Good enough? Maybe…

At this point, our iterations are quite good, but we’re seeing some recurring problems:

  • Re-allocation of arrays when Components are added/removed (I’ve not covered this above – if you’re not familiar with the problem, google “C dynamic array”)
  • Fragmentation (affects every iteration after Iteration 1, which doesn’t get any worse simple because it’s already as bad as it could be)
  • Cross-referencing (which I skipped)

I’ve also omitted history-tracking – none of the DS’s above facilitate snapshots or deltas of game state. This doesn’t matter for e.g. rendering – but for e.g. network code it becomes extremely important.

There’s also an elephant in the room: multi-threaded access to the ES. Some ES’s, and ES-related engines (*cough*Unity*cough*), simply give-up on MT. But the basis of an ES – independent, stateless, batch-oriented programming – is perfect for multi threading. So there must be a good way of getting there…

…which gives me a whole bunch of things to look at in future posts :).

PS … thanks to:

Writing these things takes ages. So much to say, so hard to keep it concise. I inflicted early drafts of this on a lot of people, and I wanted to say “thanks, guys” :). In no particular order (and sorry in advance if final version cut bits you thought should be in there, or vice versa): TCE’ers (especially Dog, Simon Cooke, doihaveto, archangelmorph, Hypercube, et al), ADB’ers (Amir Ebrahimi, Yggy King, Joseph Simons, Alex Darby, Thomas Young, etc). Final edit – and any stupid mistakes – are mine, but those people helped a lot with improving, simplifying, and explaining what I was trying to say.

Artemis Entity System in ObjectiveC

I wanted to try the latest version of Artemis, and I had an old game project that was quickly written in OOP style. So I went looking for an ObjC port…

Existing port: outdated

There was a port linked on the Artemis site that was OK – but had no documentation or updates, and Artemis has moved on since then.

There were also no unit tests etc – and the current Artemis getting-started wouldn’t work with this port (because so much has changed). So I started a new port…

New port: ObjC Artemis 100%

Primary aim:

  • make it identical to the core Artemis.

Continue reading

2014 Entity Systems: what are your Unity3D questions and problems?

In 2014, I’ll be making a new game in Unity that makes intensive use of an Entity System.

This will give me lots of ammo for a new post exploring the pros and cons of Unity’s “partial” Entity System architecture. I’ve been thinking about this a lot for the last couple of years, but I’ve been unhappy with the draft posts, and didn’t publish them.

Over the next couple of months, I’d love to hear from all of you the challenges, confusions, problems, and questions you have about this. I’m not promising quick answers – but it will help shape the blog posts I write, and as soon as I have a good enough set of answers, I’ll start posting them :).
Continue reading

Designing Bomberman with an Entity System: Which Components?

Today I found a new article on implementing a Bomberman clone using an Entity System (in C#) – but I feel it doesn’t quite work.

It’s a well-written article, with some great illustrations. But the authors “Components” struck me as over-complicated and too behaviour-focussed. If you’re designing a game based on an ES, this isn’t a great way to do it – it feels too much towards old-style OOP gameobjects.

This is an opportunity to talk about good and bad directions in Component design. I really like the author’s idea of using Bomberman as a reference – it’s simple, it’s a well-known game, but it’s got a lot of depth. Read the original article to refresh your memory on Bomberman and how it works. Then come back here, and we’ll do a worked example on choosing components for a game. I’ll completely ignore the programming issues, and only look at the design issues.

Continue reading

Concepts of “object identity” in game programming…

Hume just posted his Lessons Learned from the warmup for Ludum Dare 23 (48 hours to write a game from scratch – starts this weekend!) – and his positive experience using an Entity System.

In his epic comment (sparked by a different Adam – not me, honest), is this gem:

“Using the entity system for the first time was unreal to me. It’s like polymorphic code. I did really weird things on the fly. For example:

- In the health processor, if the enemy was just destroyed, set a flag in the lifecycle component.
- In the lifecycle processor, if the fresh kill flag is set, extract its loot component and put that into a new entity with a small randomized velocity component and a gravity component so that the loot drops; then, remove most of the other components from the entity and add an explosion component.

The “enemy” still has the same entity ID — any other components that are looking for that entity will still find it (e.g. missiles homing in on the wreckage, or score processors looking for slain entities) — but by swapping one set of data with another, its implementation has changed from an enemy to some kind of non-interactive effect object.”

(emphasis mine)

Identity. It’s important.

(Quick sidenote: for all the people asking questions like “but … which variables do I put in Component A as opposed to Component B? How do I manage Events in an Entity System? … etc” – Hume’s approach above is a good concrete example of the first-draft, easy-to-write way of doing things. Copy it.)

Identity in games

This is one of those things that newbie game programmers seem to underestimate, frequently.

And when I say “newbie” I include “experienced, skilled programmers with 10+ years of coding experience – but who haven’t yet shipped a game of their *own*”.

(e.g. I’ve seen a couple of studios that started as Digital Agencies, or as Animation Studios, etc – that then transitioned to writing their own games. This is the kind of thing that they often struggle with. Not for lack of skill or general programming experience, but for lack of the domain-specific experience of game coding)

Examples of Identity in games, off the top of my head – all of these are independent, and interact in complex ways with each other :

  1. Game-role: e.g. … “enemy”, “powerup”, “start location”
  2. Code ‘object’ (in OOP terms): e.g. … “the sprite you are drawing at position (4,5) is part of Object X. X is coloured THIS colour”
  3. Gameplay ‘object’: e.g. … “the sprite at (4,5) represents a Tank. If a Tank sprite ever touches a Glass sprite, we need to play the Broken Glass noise”
  4. Physics element: e.g. … “5 milliseconds ago, our Physics Engine thought this thing was THERE. Now it’s over HERE. Don’t confuse the Physics Engine! Make sure it ‘knows’ they are the same object – not two separate objects”
  5. Network “master/clone”: e.g. … in multiplayer, there are N copies of my avatar: one per computer in the game. One of those N is the original – and changes to the original are constantly used to overwrite the clones; changes to clones are LOCAL ONLY and are discarded. Which is original? What do we do with incoming “changes” – which local Code Object do we apply them to? (your Code Object will be different from my Code Object – but they’ll both be the same identical Network Object, save mine is flagged “clone”)
  6. Proper Noun object: e.g. … “The Player’s Tank” is a very specific tank out of all the Tanks in the game. Many lines of game code don’t care about anything except finding and operating on that specific tank.
  7. Game-Over representation: e.g. … after the player has killed all the enemies, and they see a Game Over (won/lost/etc) screen, and you want to list all the enemies they killed … how do you do that? The enemies – by definition – no longer exist. They got killed, removed from the screen, removed from memory. You could store just the absolute numbers – but what if you want to draw them, or replay the death animations?
  8. …etc

Identity in Entity Systems

ES’s traditionally give you a SINGLE concept of Identity: the Entity (usually implemented as a single Integer). Hmm. That sounds worryingly bad, given what I wrote above. One identity cannot – by definition – encompass multiple, independent, interrelated identities.

But we’re being a bit too literal here. ES’s give you one PRIMARY identity, but they also give you a bunch of SECONDARY identities. So, in practice…

Secondary Identities in an ES

In OOP, the Object is atomic, and the Class is atomic. You cannot “split” an Object, nor a Class, without re-defining it (usually: re-compile).

In ES, the Entity is atomic, and the Component is atomic. But the equivalent of an OOP Object – i.e. “an Entity plus zero or more Components” – is *not* atomic. It can be split.

And from there comes the secondary identities…

A Primary Identity: e.g. “The Player’s Tank” (specific)
A Primary Identity: e.g. “a Gun Component” (generic)

A Secondary Identity: e.g. “The Gun component … of the Player’s Tank Entity” (specific)

Revisiting my ad-hoc list of Game Identities above, I hope it’s clear that you can easily re-write most of those in terms of secondary identity.

And – bonus! – suddenly the relationships between them start to become (a little) clearer and cleaner. Easier for humans to reason about. Easier *for you to debug*. Easier *for you to design new features*.

Global Identity vs. Local Identity

Noticeably, the network-related Identities are still hard to deal with.

On *my* computer, I can’t reference entities on *your* computer. I cannot store: “The Gun component … of YOUR player’s tank”, because your “Player’s Tank” only exists in the memory of your computer – not mine.

There are (trivially) obvious solutions / approaches here, not least: make your Entity integers global. e.g. split the 64bit Integer into 2 32bit Integers: first Integer is the computer that an Entity lives on, the second is the local Entity Integer. Combined, they are a “global Entity ID”.

(I’m grossly over-simplifying there – if you’re interested in this, google for “globally unique identifiers” – the problems and solutions have been around for decades. Don’t re-invent the wheel)

But … at this point, they also offer you the chance to consider your game’s network architecture. Are you peer-to-peer, or client-server?

For instance, P2P architectures practically beg for unique Global entity numbers. But C/S architectures can happily live off non-global. For instance:

  • On each client, there are ONLY local Entity numbers
  • When the client receives data from the server, it generates new, local, Entities
  • …and adds a “ServerGenerated” component to each one, so it’s easy to see that they are “special” in some ways. That component could hold info like “the time in milliseconds that we last received an update on this object” – which is very useful for doing dead-reckoning, to make your remote objects appear to move smoothly on the local screen
  • The server *does* partition all entities from all machines. But none of the clients need to know that

Or, to take it further, if your network arch is any good at all for high-paced gaming:

  • The server differentiates between:
    1. The entity that the game-rules are operating on
    2. The entity that client 1 *believes* is current
    3. …ditto for client 2, client 3 … etc (each has their own one)
    4. The entity that the game-rules accept (e.g. if a hacked client has injected false info, the game-rules may override / rewrite some data in the local object)
  • The server also tags all the entities for a single in-game object as being “perspectives on the same thing”, so that it can keep them in synch with each other
  • The server does Clever Stuff, e.g.:
    • Every 2 milliseconds, it looks at the “current entity”, and compares it to the “client’s belief of that entity”. If it finds any differences, it sends a network message to the client, telling it that “you’re wrong, my friend: that entity’s components have changed their data. They are now X, Y and Z”

… or something like that. Again, I’m grossly over-simplifying – if you want to write decent network code, Google is your friend. But the fastest / lowest latency multiplayer code tends to work something like that.

How?

Ah, well.

What do you think?

(hint: you can do wonders using Reflection/Introspection on your entity / components. By their nature, they’re easy to write generic code for.

But you WILL need some extra metadata – to the extent that you may wish to ‘upgrade’ your Entity System into a SuperEntity System – something with a bit more expressive power, to handle the concept of multiple simultaneous *different* versions of the same Entity. Ouch)

Yeah, I’m bailing on you here. Too little time to write much right now – and it’s been a *long* time since I’ve implemented this level of network code for an ES. So, I’m going to have to think hard about it, refresh my memory, re-think what I think I knew. Will take some time…

Entity Systems: integrating Box2D with Artemis

Thanks to Mike Leahy for spotting this:

http://blog.gemserk.com/2012/02/02/how-we-use-box2d-with-artemis/

…a short blog post (with code) on how a team is integrating Box2D (a very well known open source physics lib) with Artemis (a java implementation of Entity Systems which starts from the same point as my Entity Systems posts, but fleshes it out)

Entity Systems: what makes good Components? good Entities?

In the ongoing, epic comments (300+ and counting!) for my Entity Systems posts, one of the recurring questions is:

What makes a good Component?
How should I split my conceptual model into Entities and Components?
How should I split my algorithms and methods into Systems?

It’s often difficult to answer these questions without concrete examples, which are thin on the ground.

Good news, then…

Paul Gestwicki runs a CS315: Game Programming course, and last year his students used an Entity System to implement their game – Morgan’s Raid. In a recent email conversation, he mentioned he’d been monitoring the actual number – and nature – of the Components and Systems that the teams developed and used on the project.

He’s now posted this list, along with some brief analysis.

All systems and Components

Read Paul’s post – there are some caveats he mentions, and there’s a useful diagram showing roughly how many systems were using each component.

I strongly recommend you play the game too (it’s free, and quick to play) so you can get an idea straight away – just from the names – what data and code some of these contain.

To recap, here’s the list:

“For your reading convenience, here’s a simple tabular view of the systems and components

Systems Components
BackgroundTileSystem
CityNameSystem
DestinationSystem
FadingSystem
GPSToScreenSystem
HoverableSystem
ImageRenderingSystem
IntInterpolationSystem
MinimumSleepTimeSystem
MorganLocationSystem
NightRenderingSystem
OnClickMoveHereSystem
OnScreenBoundingBoxSystem
RaidSoundSystem
RailwaySystem
ReputationSystem
RevealingTextSystem
SpeedSystem
StepwisePositionInterpolationSystem
SunSystem
TimePassingSystem
TimeTriggeredSystem
TownArrivalSystem
TownArrowSystem
TownUnderSiegeSystem
AnimationRenderable
ArrivesAtTownIndex
BackgroundTile
BeenRaided
CentersOnGPS
CityData
CityImages
CityName
CityPopulation
CityTargets
CommandPoint
Destination
DoesCityHaveMilitia
DoesCityLoseGame
DoesCityWinGame
GPSPosition
GPSPositionList
HasMorganGPS
Hoverable
ImageRenderable
ImageRenderLayer
InGameTime
IntInterpolated
MinimumSleepTimeOverride
Morgan
MorganLocation
MovesOnClick
OnClickMoveHere
OnScreenBoundingBox
OnScreenBoundingBoxList
PositionInterpolated
Raidable
Raider
Railway
Reputation
ReputationValue
RevealingText
Road
RoadsToCity
RouteTaken
Speed
Sun
Terrain
TimeToRaid
TimeTriggeredEvent
TownAdjacency
TownArrow
TownUnderSeige

Things I noticed straight away:

  1. There’s approximately 2:1 ratio of “components” to “systems”
  2. In Paul’s post, all the Systems are accessing *something*
  3. In Paul’s post, quite a few Components are NOT accessed
  4. A couple of components are used by almost every System
  5. The names of some Systems suggest they’re very trivial – perhaps only a dozen lines of effective code
  6. The names of some Components suggest they’re being designed in an OOP hierarchy

NB: I haven’t had time to look at the source code, but it’s freely downloadable here, so I’d recommend having a look if you have time.

How many Components per System?

I’ve generally started people off with: “aim for 1:1 ratio”. This is mainly to kick them out of the traditional class-based OOP mindset. In practice, there’s really no need to stick to that religiously – once you get the hang of ES design, you should be freely adding and subtracting components all over the place.

In reality, the pressures on “number of systems” and “number of components” are independent. Ideally, you add a new system when you have a major new concept to add to your game – e.g. “previously I was using hand-made jumping, now I want to add a complete physics-driven approach. This will mean changing collision-detection, changing the core game-loop, etc”.

Ideally, you add a new component when you have a new “dimension” to the game objects. For instance, if you’re adding a physics System, you may not need to add any new Components – it might be that all you need is Location (containing x,y,x position and dx,dy,dz velocity) and RenderState (containing screen-pixels x,y) – and that you already have those components.

Zero systems per component

One of the advantages of an ES is that old code can just fall off the radar and disappear. So I’m not surprised at all to see some components that appear to be unused – and it’s MUCH easier to simply delete this code from your project than it would be on a traditional OOP project. Does anything reference that data? If so, it’s a set of particular systems. For each system, you can look at MERELY the system and the component, and make a very quick decision about whether you still need this access – or if you can refactor to move (some of) it somewhere else. The amount of code you need to read to make such decisions safely is typically very small – i.e. easy, quick, and less error-prone.

Many systems per component

This is fine. However, it can also be an early-warning sign of a design or code-architecture bug. Sometimes, there are components that – innately – are just needed all over the place. For instance, in a team-based game, the component saying which “team” a given object/player/item/building belongs to is likely to affect almost every piece of algorithm code across the board. It’ll be referenced by many systems.

On the flip-side, it may be a sign that you’ve put too much data into one component. There are two usual versions of this:

  1. You have – say – 8 variables in the struct where you should instead have two structs (components), one with 5 variables, the other with 3.
  2. You have – say – 4 variables in the struct, but different systems are using those variables to mean different things. It works OK for now, but it’s very fragile – as soon as the different meanings diverge even a little, your code is going to start breaking

Of course, you get this exact problem in traditional OOP setups, but with an ES it’s trivial to fix. Split – or duplicate – the Component, change a few references in the Systems, and you’re done. If it turns out a week later that the split wasn’t necessary – or worse, was a step backwards (e.g. you find yourself frequently synching the data between those components) – it’s extremely cheap to swap it back.

By contrast, with OOP, this is a nightmare scenario, because you have to worry about every method on the original class. Does that method:

  1. Need to exist on both the new classes, or just one?
  2. Work correctly for the new class it will be on – or does it currently rely on some of the data (and shoudln’t) and will need to be re-written?
  3. Get used by other parts of the codebase in ways that will break if/when you split the class?

Thoughts, Suggestions?

…this is just a lightning quick analysis, but I strongly invite you to do you own digging into the classes – and the codebase – and come up with your own thoughts and feedback. We have here a convenient, real-life, list of components/systems – something to dig our teeth into, and debate the rights and wrongs of each decision. And I’m sure the students involved on the project would be interested in your feedback on their approaches :)

Did this post help you?

You can say “thank you” by giving me your email address, and letting me contact you next time I make a game of my own:

LudumDare 21: Escape from the (Android) Pit

I couldn’t enter this LudumDare competition on a technicality, but here’s my entry which plays by the spirit of the rules. I took a total of 24 hours (out of 48), of which only 12 were actual design + development (see below). Hopefully next time I’ll be able to do it properly, and actually compete. I’ve kept to every rule, except that I did my 48 hours time-shifted :) from everyone else (two successive Sundays, instead of a contiguous Saturday + Sunday).

Screenshot + Android APK

Download link (APK – you need to know how to install APK’s manually (google it if you’re not sure, it only takes 5 seconds)):

Escape From the Pit

Aims

  1. Make a LudumDare entry as an Android application – none of this easy “make it in Flash” or “make it in java” stuff – let’s go for a full mobile game, designed, developed, and launched in exactly 2 days flat!
  2. Use an Entity System (c.f. my long-running series of articles, and also the public Wiki I created), and show that ES’s facilitate you writing new games VERY VERY QUICKLY
  3. Make a game that was mildly challenging and (almost) enjoyable

Failed to officially enter the competition, but otherwise succeeded…

Background

LudumDare challenges you to write an entire game in under 2 days (technically: 48 hours – it’s up to you how much of that you sleep). You can’t even design it in advance – there’s a theme that’s only decided shortly before the 48 hours starts.

LudumDare was the weekend before last – but I had to work that weekend on urgent day-job stuff. Like: I had to work all day Saturday, and there was no way out of it. So I couldn’t do the same 48-hour stint as everyone else.

Also, I know from previous experience that the “48 hours in one stretch” is very different from – say – “12 hours for 4 days”. When you do a 24 or 48 hour game, you tend to only manage a certain percent of “productive” hours. The challenge of designing + building something from scratch forces you to keep taking “time off” to go think about what do next.

So, I kept a diary of hours worked, and hours taken “off” as well. I’m confident I’d have fitted all of this – development time AND down-time – into the 48 hours. But I had to spread it over 2 successive weekends :(.

Day 1

(3 hours) – install Eclipse and the Android plugin, and the Android SDK. Document what I’ve done (1 hour) and check I can re-do it at will. Google, please wise-up and fix your install process – it’s not changed in almost 2 years, and it SUCKS

(1 hour) – install some extra Android OS versions, get the emulator working correctly, get projects imported, get everything in source-control, get empty app running on hardware device. Ready to start project!

— NB: everything up to this line I should have done before the contest started. If I were the kind of person that had free time on weekdays. Which sadly I’m not —

(1 hour) – getting Android base classes up and running. Takes a while: Android is insanely badly designed for the “Core application” part. Needs hundreds of lines of code to make a Hello World app that *actually* works as an app (Google’s code example that does it in 4 lines is fake: no real app could do that).

(3 hours) – on the beach, not working

(4 hours) – upgrading the open source Entity System Libraries on http://entitysystems.wikidot.com to support a bunch of features I’ve been using for a while in my own projects. This required writing a lot of stuff from scratch (using my own old source as inspiration), and integrating some improvements from patches/forks that other people had submitted.

— NB: everything up to this line I could have done before the contest started. Interesting though that I thought this was going to be “about to start writing the actual game” and I’ve only finally got to the point where I can write my first line of game-code —

Day 2

(0.5 hours): trying to make textures in Photoshop. Photoshop really sucks. Half the online resources for making the kinds of textures I want require PSP’s unique filters/effects – useless :(.

(0.5 hours): get a single sprite to appear on screen. A couple of idiot errors in one of my libraries – plus Google’s Eclipse plugin being really really bad at understanding “the scroll bar” (bug in ADT: it implements the world’s only non-static scrollbar)

(1 hour): random maze generation (using: http://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim.27s_algorithm ) that makes nice mazes, printing out onto the screen, still with my default “starfield” background. Rotating the screen is causing the entire game-state to be regenerated – includkng the maze – which was an accident, but actually helped A LOT with testing the maze algorithm (just tilt to re-run the algorithm instantly)

(0.5 hours): learn how to do Android input-handling correctly; en-route, discover I’m missing the SDK docs, and set about downloading + installing them … + updating my blog instructions on how to install Android to include “SDK docs” as a section.

(2.5 hours): discovering MAJOR bugs in Google’s basic “touch handling” API for Android – including bugs on Google’s own website source code, and an API designer on crack who broke the core Java contract didn’t document it. Not Happy.

Day 3

(1 hour) – implementing a collision detection system that does proper swept-collisions, but works OK with the poor fine-grained control of touch input

(1 hour) – added filters to collision detection so I could have background images that the player will NOT collide with
(previously was colliding with every on-screen rendered sprite). Also added a very simple lighting system where squares that the player has walked close to or upon gradually light up, showing how much has been explored

(1 hour) – refined the user-controls so you can hold your finger still and character keeps moving in that direction. Added handling in collision-detection system to allow character to slide along walls and into side-passages without the player having to stop and be ultra-precise (pixel perfect!) in timing the change of direction.

(0.5 hours) – added an exit, fixed bugs in the maze-generation (if started on a right or bottom edge, it crashed)

(1 hour) – fix Android’s brain-dead handlig of Bitmaps, giving a big speed boost, and re-learning how to use DDBS memory-allocation-tracking. I’m now auto-caching each bitmap inside my Sprite object. Sigh. There’s no easy workaround: Google says “don’t use getter methods” but Google also says “don’t call our getDrawable method more than once”.

(1 hour) – added ghosts, made them move around the map nicely, and collide with player was *automatic* on first compile (freebie from using an Entity System!). Also made arrows float nicely in same place on screen even while scrolling.

(1 hour) merge code from laptop back to desktop. Finally add the “win” conditions that makes the app playable!

Source Code

To make this game, I improved the basic Java Entity System up on the ES Wiki, and added some usability improvements and features. I created a whole new page for it here:

http://entity-systems.wikidot.com/rdbms-beta

NB: It’s called “Beta” simply meaning “second generation (beta == second letter of greek alphabet)”. Not because it’s a beta-quality release :).

Source code to the game itself is also up on github right now – https://github.com/adamgit/Game–Escape-from-the-Pit – although that’s a closed repository at the moment. I want to double-check there’s nothing included that shouldn’t be before I set it to “public”.

Entity System: RDBMS-Beta (a new example with source)

I’ve just added a new, improved Entity System design to the wiki. I’ve also created a github project for it where I’m about to check-in working source.

The only source I’ve provided is Java – but it’s an evolution upon the old “RDBMS with Code in Systems” type, that already has full source for Java and Objective-C – so you could easily upgrade the obj-c version to this new type (hint, hint).

What’s new?

Three major changes:

  1. Included a bunch of sensible java-specific improvements, based on the forks other people had done of the previous Java implementation
  2. Added a bunch of FANTASTICALLY USEFUL methods to the EntityManager – things you definitely need when writing a game
  3. Added a new concept: the Meta Entity

The first one is obvious, the second is obvious when you look at what’s added (e.g. a “removeComponent” method; why wasn’t it there originally? Solely because it wasn’t necessary to show “the simplest possible implementation”).

The interesting one is number three: the Meta Entity

What’s a MetaEntity?

A while back, in the first Java/Android ES I wrote about, I mentioned that I was using a fake Entity class.

I made a big fuss about how this was NOT being used to store any game data – but was instead an OOP trick to make it easier to write code.

Thinking about this later, I realised that there was really no need for that class to be named “Entity” – and calling it that ran the risk of tempting people into using OOP for their core data / components (Remember: Never do that!). Instead, looking back at a couple of example ES’s I’d written, I saw that every method – and all data – in this class was a “meta method”.

For the methods, you need to read the source AND the javadocs to see this.

For the data, it’s a lot more obvious: the only data that a MetaEntity has is:

  • The Entity itself (remember: that’s just an integer – or a UUID object in Java, which is a cleaner Java-specific way of handling it)
  • The EntityManager object which created this Entity, and which contains the Components for that Entity, and … basically provides all access to the data etc

i.e. if you pass around MetaEntity objects, you can feel safe that you know where they came from, where their components are, etc.

Because when you pass around raw Entity’s, they’re just an integer – which makes it easy to create an Entity in one EntityManager, then accidentally start using it in another EntityManager. Technically that’s illegal – but from a compiler perspective, it’s 100% legal … so you’ll get bizarre runtime bugs. Ouch.

Equally, the MetaEntity can contain a lot of single-argument and zero-argument versions of methods that exist in the EntityManager as 2-argument, or 1-argument methods. This greatly reduces typing, increases readability, and reduces opportunities for bugs. It may sound like a very small change (2 arguments dropping to 1), but I promise you: in practice, it makes a big difference.

Why not use MetaEntity’s all the time?

They’re very inefficient in how they use memory, and they throw away many (but not all) of the performance advantages of an ES.

For instance, because you’re moving from “integer + array of structs” to “linked-list of objects”, you’re making your game go from “cache friendly” to “cache poor”, and making your MINIMUM mem usage go from “tiny” to “small”.

In practice … if those differences matter to you, you’re probably writing a hardcore custom ES anyway.

More importantly: even in a “hardcore” ES, you don’t actually *need* that performance all the time. If you’re just pulling out a handful of Entities and their Components – e.g. a player Entity (of which there’s only 1 – or a few for multiplayer) – then the above performance differences are NON EXISTENT (vanishingly small).

…but the code is more readable, easier to maintain, and more robust.

So. I recommend using the MetaEntity for *all* your ES coding … until you reach a point where performance is low. Then look at re-coding *only* the affected loops / methods (remember: you can do this on a System-by-System basis; your code is nicely separated already!). That way, you get the best of both worlds.

However … the reason none of this was included in the first Java ES I posted onto the wiki – the ultra-simple “RDBMS-inspired with Code in Systems” – is that really this is all just gloss on top of an ES. You don’t need it. I believe it makes your ES easier to work with – but it distracts from the core theory.

I’d recommend you start with the simpler ES, and understand it, before moving onto something like this for your practical work.

For more info, check out the wikidot link at the top of this post – and try the github project linked from it (currently empty, until I do a check-in)

Did this post help you?

You can say “thank you” by giving me your email address, and letting me contact you next time I make a game of my own:

Using an Entity System with jMonkeyEngine (mythruna)

If you’re interested in using an ES on indie projects, and you’re craving concrete examples, you might want to look at the comments (page 1 and page 2) on Mythruna:

“Since this is a developers forum, I’ll describe a little bit about what went on behind the scenes.

During the early development for this phase, I read about an architectural pattern called an entity system.

I had (pre Entity Systems) a plan for how I was going to store the placement of objects in the world but this past weekend when I actually got to implementing it, I couldn’t make that original plan work and came to the point where I needed to solve the general problem of world state storage. This is the kind of thing that Entity Systems make relatively straight forward… and by Saturday, Mythruna had an embedded SQL database that autogenerates tables based on the components stored. (HyperSQLdb for the win.)

So at some point I swapped out the in-memory version of the entity system with the SQL version… and suddenly objects were persistent. It was so easy I had to double check a few different ways that it was actually working. :)”

…but of course, also: use the Entity Systems wiki – put your questions there, put your ideas there, and (most of all) if you have an ES project or ES source code you want to share, please add it to the wiki!

Entity Systems: updates to source code

I’ve just done a round of fixes for the source-examples of ES’s. Github projects updated on this page:

http://entity-systems.wikidot.com/rdbms-with-code-in-systems

Changed:

  1. Added a complete Java implementation of the most basic ES example
  2. Fixed some minor bugs in the Objective-C basic ES example; added some missing classes
  3. Added a missing class method from the documentation (System.

Help! Which computer games use Component/Entity Systems?

For this page:

http://entity-systems.wikidot.com/start

…I want a list of published / self-published games that were built on top of an Entity System.

I know a few off the top of my head (I think – I’m going to mail some of the authors and double-check), but mostly I have no idea.

So … if you know of any, please add them to the wiki on that page.

BONUS POINTS

…if you can provide *any* of the following info:

  • Link to a public interview / post-mortem about the game that mentions the team’s experiences with ES
  • Names of any programmers and designers that definitely worked on the ES part of the game
  • *SUPER BONUS*: link to a description of how they designed/implemetned the ES part

Entity System 1: Objective-C

(this is a simplified, but complete, version of the “Entity System 1: Java/Android”)

NB: this post is part of the community effort to make working, usable, free, source-examples of actual Entity Systems, found at http://entity-systems.wikidot.com/

Wiki link: http://entity-systems.wikidot.com/rdbms-with-code-in-systems

Github source: https://github.com/adamgit/Entity-System–RDBMS-Inspired–Objective-C-

I’m posting my original design notes here – also copy/pasted to the wiki, but the wiki version will probably evolve over time. Comments on this post will be disabled – please comment direct on the wiki / wiki discussion pages.

NB: the source code is in GitHub, that’s where you should download it from (will include any fixes and updates over time)

Concepts

(integer) Entity
(enum) ComponentType
(interface OR empty base-class) Component
(interface OR empty base-class) System
(class with implementation) EntityManager

Data Classes

Entity

This is a non-negative integer, and uniquely identifies an entity within the ES. If you serialize your ES, this SHOULD be the same after serialization. New entities have to be assigned a new, unique, integer value when they are created. When an entity is destroyed, its integer value is freed, available for re-use.

ComponentType

This is needed because this ES is so simplistic it has no other way of identifying which Component you’re talking about when you’re looking at a single Entity.

(richer EntitySystems MAY not need this type)

Component

This exists purely to make method-signatures type-safe. We need to know that certain objects are valid instances of a “component” (so we use this superclass to indicate that), but we also need a method that’s guaranteed to work on all those objects (see below).

(richer EntitySystems make more use of this, and require it to be a class, but for this simple ES, you can use an interface/header file)

System

This exists purely to contain a known method-signature that your game-loop can call once per game-tick.

EntitySystem Implementation Classes

Each subclass of Component

Internally, the class has the following functions:

  1. (ComponentType) getComponentType();
EntityManager

This contains:

  1. The master collections (arrays, hashmaps, whatever) that contain all the data for all the entities
  2. Logic for creating, modifying, fetching, and deleting entities
  3. Logic for fetching and modifying components-from-entities

Internally, the class has the following variables:

  1. MAP: from “Entity + ComponentType” to “concrete Component subclass”
  2. LIST: all entities in existence (so it never duplicates entity-IDs!)
  3. Internally, the class has the following functions:

    1. (Component) getComponent( Entity, ComponentType );
    2. (List) getAllComponentsOfType( ComponentType );
    3. (List) getAllEntitiesPossessingComponent( ComponentType );
    4. (void) addComponent( Entity, Component );
    5. (int) createEntity;
    6. (void) killEntity( Entity );

Entity System 1: Java/Android

Please note: the design described in this blog post has been much improved and updated and put up – with full source – on http://entity-systems.wikidot.com/.

On the wiki linked above, there is now a wholly new Entity System design, based on this one, but much improved. There’s a brief post about it here, recommended instead of this ES design: http://t-machine.org/index.php/2011/08/22/entity-system-rdbms-beta-a-new-example-with-source/.

I’ve been writing about Entity Systems sporadically for the last few years. Recently, I finally had the time and the excuse to build one of my own (i.e. not owned by an employer). If you haven’t read the main series of ES posts, you should do that first. There are many things in the world masquerading under the Entity/Component banner – and even more that just coincidentally share the name, but describe something else completely. It’s worth understanding which variant I’m talking about before you read about what I’ve done :).

Why build an Entity System?

At a generic level, this is covered in the other posts. But it’s taken years for me to have the time/inclination to write a new one from scratch outside of my day-job. What happened?

  1. I left my iPhone in America, and it took 2 months to get it back
  2. Google gave me a free Nexus One, in the hope I’d write something for it (ha! Their cunning plan worked…)
  3. The Android marketplace is such a miserable morasss of third-rate crap that eventually I was compelled to write my own Android game … just so that I would have something to play (there are very few games on the Android store that are even worth the time it takes to download them)

I’ve been making games for a long time. I know how much effort will go into it, how much time, and how much slog there is before it becomes worth it. Writing a game on your own often means putting in 90% of the effort to get 10% of the reward.

Enter … the Entity System. If I were to pick a game-design that mostly used data-driven game features, I could implement it around an ES, and massively reduce the amount of planning needed to get the game running. I could maybe have a working game after a mere 20% of the effort. Hmm…

Building the ES for Android

Android runs something that’s *almost* Java (although more on that later – Android’s version of Java is very slow at some of the core libraries, and it really shouldn’t be). Technically, Android supports all the core data structures from Java (Collections), and the templating system (Generics).

If I were writing an ES in C++, I’d do it using templates without pausing to think; I wondered how well the same might work with Generics, given that Generics is *not* a complete templating system, although it provides quite a lot.

Getting started: early ES decisions

How to design/implement this thing? Well, we know one thing for sure:

Entities have a single name/label/global-ID. Entities MUST NOT contain ANY DATA: these are NOT objects, this is NOT OOP!

There you go, the Entity class wrote itself:

public class Entity
{
   public int id;
}

This immediately raised some concerns for me, being the seasoned coder I am (ha!). How the heck was I going to write any code that dealt with these things if I didn’t have references to them? Obviously, sometimes you do have references, but other times you expect to follow refs from within the objects you have, to get to the objects you need. That wouldn’t be happening here, since there are no inter-object refs.

public class BaseEntitySystem implements EntitySystem
{
	/** I'm too lazy to write a "safe" method to get a globally-unique ID; for now,
	I just return 1 the first time I'm called, 2 the second time, etc... */
	protected int getNextAvailableID();
	
	/** Whenever you create an entity, you'd better invoke this method too!*/
	public void registerEntity( Entity e );
	
	/** The method to solve my fears above */
	public Entity getEntity( int id )
	
	/**
	 * Merely removes the entity from the store. It becomes a GC candidate
	 * almost immediately (since all other refs are transient)
	 */
	public void killEntity( Entity e )
}

…but, again, being a Veteran coder, the survivor of many painful battles on the field of programming … I didn’t trust myself in the slightest to “always remember” to invoke registerEntity. Quick trick: give the Entity class a static reference to a default EntitySystem, and have each EntitySystem check if that reference is null when starting; if so, set itself as the “default”.

public class Entity 
{
	...
	public static EntitySystem defaultEntitySystem;
	...
	public Entity( int i )
	{
		id = i;
		
		if( defaultEntitySystem == null )
			throw new IllegalArgumentException( "There is no global EntitySystem; create a new EntitySystem before creating Entity's" );
		
		defaultEntitySystem.registerEntity( this );
	}
	...
}

public class BaseEntitySystem implements EntitySystem
{
	...
	public BaseEntitySystem()
	{
		if( Entity.defaultEntitySystem == null )
		{
			slog( "Setting myself as default entity system (Entity.default... is currently null) self = " + this );
			Entity.defaultEntitySystem = this;
		}
	}
	...
}

W00t! I can create Entity’s, and I can find them later on. Awesome. What about those Components, then?

Getting started: Components in Java

I’ve done ES in C++ before, with real templates, so I wasn’t really thinking at this point … I just ran with what seemed natural based on prior experience. The thought process (had there been one) would have been something like this:

  1. This is java, I use Eclipse: I absolutely *must* have the IDE know what data/fields exist in each component so that Content-Assist/Autocomplete works 100%. Otherwise I will gouge my own eyes out having to remember, and doubly so each time the app compiles but dies at runtime because of a typo in a field-name.
    • Requirement: each unique Component must be defined as a java Class, with each of the fields being a public member of that class
    • Requirement: to access a Component of a given Entity, you must invoke a method which returns something that is typed (as in language typing) to the correct Class

I made a Component class, and had all Components extend it; there is a particular reason for this, but it doesn’t matter right now – essentially, it lets you define shared behaviour for all Component subclasses, and just saves you time on typing.

My first real Component:

(NB: I defined this *inside* another class, because I couldn’t be bothered having N source files for the (large number of) N Components I was bound to create. Hence the “static”):

public class MyEntitySystemExperiment
{
	...
	static class Position extends Component
	{
		float x, y;
		int width, height;
		float rotationDegrees;
		
		@Override public String toString()
		{
			return "("+super.toString()+" @ ("+x+","+y+") * rot."+rotationDegrees+")";
		}
	}
	...
}

Great. I have a component. Now comes the largest single piece of work in the entire implementation of the ES: writing the methods to:

  1. Add a component to an Entity
  2. Fetch a component from an Entity
  3. Remove a component from an Entity

Fetching a Component from an Entity

This is the win/lose point: if this works well, our ES will be nice and easy to use. The other two methods (add and remove) are simply twiddling bits of data. This one is the challenge: can you make it *easy* to write code that uses the ES, and for that code to be clearly *understandable*?

public class EntitySystemSimple extends BaseEntitySystem
{
	HashMap<Class, HashMap<Entity, ? extends Component>> componentStores;

	public <T> T getComponent( Entity e, Class<T> exampleClass )
	{
	   HashMap<Entity, ? extends Component> store = componentStores.get( exampleClass );
		
	   T result = (T) store.get( e );
	   if( result == null )
	      throw new IllegalArgumentException( "GET FAIL: "+e+" does not 
possess Component of class\n   missing: "+exampleClass );
		
	   return result;
	}
	...
}

Boom! It works.

Let’s just stop briefly and I’ll explain why. Reading Java generics code from cold (just like reading C++ templates) often takes a lot of hard thinking.

Looking at the “result” of this method, we want it to be (enforced by the compiler):

  1. “an instance of a class that extends Component”
  2. “an instance of the particular class/Component that we requested – not just any old subclass”
/** based on comments at end of blog post, think this is correct,
but not checked */
public <T extends Component> T getComponent( Entity e, Class<T> exampleClass )

It causes you to write application code that looks something like this:

public void doSomethingWithAnEntity( int globalId )
{
	// remember, we NEVER hold refs to Entity objects for long
	Entity e = entitySystem.get( globalId );
	
	Position position = entitySystem.getComponent( e, Position.class );
	position.x = 5;
}

…and what’s important is that the “type” of the “Position position = …” line is already hard-typed to “Position”. So, the content-assist will *auto-complete* anything put after a dot on the end of that line, e.g.:

	entitySystem.getComponent( e, Position.class ).AUTO_COMPLETE

…so you can instead write your method much quicker, and yet very clearly, as:

public void doSomethingWithAnEntity( int globalId )
{
	// remember, we NEVER hold refs to Entity objects for long
	Entity e = entitySystem.get( globalId ); 
	
	entitySystem.getComponent( e, Position.class ).x = 5;
	entitySystem.getComponent( e, Damage.class ).hitpoints = 145;
	entitySystem.getComponent( e, Renderable.class ).foregroundColour = Color.red;
}

Time-out: HashMap

HashMap is the “correct” class to use in Java for this setup: it’s the exact equivalent of Hashtable / Dictionary / etc in other languages. We need to map (somewhere, somehow) from one thing (an entity) to another thing (a component).

NB: this does not mean that you have to use HashMap as your data-store for the ES; I positively encourage you to consider other options. I used it here as the most obvious, simplest possible structure that would do the job. If you think back to my posts on Entity Systems for MMO development, I’ve often suggested that the data store could *and should* be any of many different things. In particular, SQL databases make for an excellent data-store (and remember you can get in-memory SQL implementations that do away with all the expensive write-to-disk stuff).

Unfortunately … Android seems to only partially support HashMap. You can use the class, but it runs an order of magnitude slower than you expect for a normal JVM (compared to the speed with which it runs other methods). It seems to have problems with the hashcode methods, but also even with basic iteration over the Map contents. Odd. Later on, I had to do some tricks to speed up the ES, just because of this problem.

Fetching a Component from an Entity: Redux

The examples I gave above for accessing components were lean and clear on the right hand side (thanks to autocomplete and strong typing), but terrible on the left-hand-side. By the magic of OOP, I’m going to clean up the LHS. BUT (and this is a big “but”) … make sure you fully understand what I’m doing here. With what I’m about to do, it would be very easy to fall into one of the traps of ES development: slipping back into OOP techniques.

Looking at the example:

	entitySystem.getComponent( e, Position.class ).x = 5;
	entitySystem.getComponent( e, Damage.class ).hitpoints = 145;
	entitySystem.getComponent( e, Renderable.class ).foregroundColour = Color.red;

… applying OOP mindset, we see that the first argument is redundant; the Entity already knows about the EntitySystem to which it’s registered.

Also, we know that the Entity class will never have any methods or data other than the ID. If that’s the case, the only thing we’d ever “get” from an Entity is a Component. So, we can add this to Entity:

public class Entity 
{
	...
	/** Gets a filtered view of the entity's data, only returning the subset that
	 * corresponds to a particular one of its components */
	public <T extends Component> T getAs( Class<T> type )
	{
		return source.getComponent( this, type );
	}
	...
}

…which converts our usage example to:

	e.getAs( Position.class ).x = 5;
	e.getAs( Damage.class ).hitpoints = 145;
	e.getAs( Renderable.class ).foregroundColour = Color.red;

Using the ES with Systems

Recap: right now, we can:

  1. Create entities
  2. Add components to entities
  3. Read/Write the data inside each component, on a per-entity basis
  4. Fetch entities by globally unique ID

One last thing is needed before the ES can work: we need a way to fetch Entities “by component”.

e.g.:

public class MyEntitySystemExperiment
{
	...
	public void runLoop()
	{
		while( true )
		{
			// move all the entities
			positionSystem.move( MOVEABLE_ENTITIES );
			
			// check for collisions
			collisionDetectionSystem.process( MOVEABLE_ENTITIES );

			// render all the visible entities
			renderingSystem.render( RENDERABLE_ENTITIES );
		}
	}
	...
}

We need a way to provide the arguments that are capitalized above. We know that these should be plain-old lists of entities. We know they have to come from the EntitySystem. Finally, we know that the only defining characteristic of these lists is that everything in the list has *at least* a particular Component.

(respectively, in the example above, the lists contain: “all entities that are moveable”, “all entities that are moveable AND all entities that are barriers to movement (e.g. solid walls)”, and “all entities that should be displayed on-screen”)

So, one more method for the EntitySystem interface:

public interface EntitySystem
{
	...
	public List<Entity> getAllEntitiesPossessing( Class... requiredComponents );
	...
}

“Class…” is just a convenience; in many cases, you’ll be insisting on a single Component. In many other cases, you’ll be insisting on a set of components. Java varargs provide the minor convenience of doing both of those in one method, while retaining type-safety.

The implementation of this method is obvious: it iterates over every entity that’s been registered, and checks it against ALL the required components. If it possesses all of them, it goes into the output list.

Finis

That’s it. So easy! Obviously, there’s more to it – the other methods you need to create should be mostly self-evident – but this should be enough to get you started.

Now, I’m not sure where to go from here. I’ve got a working Java ES. I’ve got some performance improvements and feature improvements. But … in practice, hardly anyone writes games in Java (except Android programmers, and there aren’t many of those), so … is it worth it?

Alternatively, I might just run through some of the practical pros and cons I encountered when actually using the ES in writing the game-logic. There’s some interesting things that came up which most people encounter sooner or later when doing their first ES, and which might be worth looking at in more detail.

One last thought…

Did it work? Did this ES allow me to write a decent Android game?

Yep. I wrote a space-invaders / bullet-hell game with it. It worked fine on Android phones for a hundred-odd enemies and bullets on screen. On Android, thanks to the crappy JVM, it started to chug after that (dropped below 30 FPS), so I had to make some substantial performance improvements, and now it’s happily rendering 300 things all flying around at 20-30 FPS. The game is far from finished, but it’s playable and fun for a minute or so – a definite achievement considering how little of it I’ve written so far.

many-entities-at-10-fps

NB: it’s got some way to go before I’ll be happy releasing it. But, given a few more spare evenings, I hope to get this up on the Android Market as a free download in the near future.

I’m pleasantly surprised that the Android phones can handle something as high-level as an ES, in a pure, unoptimized “simplest possible” implementation.

Did this post help you?

You can say “thank you” by giving me your email address, and letting me contact you next time I make a game of my own:

Entity Systems are the Future of MMOs Part 5

(Start by reading Entity Systems are the Future of MMOs Part 1)

It’s been a long time since my last post on this topic. Last year, I stopped working for a big MMO publisher, and since then I’ve been having fun doing MMO Consultancy (helping other teams write their games), and iPhone development (learning how to design and write great iPhone apps).

Previously, I posed some questions and said I’d answer them later:

  • 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?

Let’s answer those first.
Continue reading