Technology

ECS 1: Inheritance vs Composition and ECS Background

The ECS architecture I’m making isn’t that hard to implement. However, to understand the various choices that must be made when implementing ECS, it’s good to know some background and the main alternative patterns. In this post I cover Inheritance vs Composition and background information on ECS variants and Unity ECS. In particular, I’ve found there’s a lot of confusion over the exact definitions of composition, ECS, and Unity style entity-components. Hopefully this post will elucidate those terms and their relationships.

Introduction

At most universities, object-oriented programming dominates the curriculum, with a focus on inheritance (P-P-POLYMORPHISM!) as the primary tool for code reuse. However, most game architectures use composition instead of inheritance as their main programming paradigm. ECS is a specific architecture that combines the composition paradigm with a specific data layout to maximize performance for game engines. What exactly are inheritance and composition?

What is Object-Oriented Programming?

Defining OOP is a pain in the ass and a great way to get a bunch of programmers up in arms. I’ll leave it at: OOP is great for encapsulation — separating the interface from the implementation. The primary method for reusing code in related objects is inheritance. Let’s move on to inheritance, which is a much more concrete topic.

What is Inheritance? Why is it suboptimal for game engines?

Inheritance is one pattern for code reuse, and involves deriving subclasses from parent classes. The subclasses inherit all the non-private methods and members of the parent classes. Inheritance utilizes the IS-A relationship.

For example: let’s say I have two dwarves, one wielding a warhammer and one an axe, fighting a goblin wielding an shortsword. (I don’t have a sprite for the hammerdwarf, sorry. The axedwarf is the more important dwarf anyway.)

Without any code reuse, I could just code each individual. However, a lot of code would be duplicated: moving, attacking, taking damage, dying, rendering the sprites, collision code (if there are collisions), etc. would all be duplicated for all three humanoids. Code duplication is bad.

Instead, let’s use inheritance! I’ll implement a Humanoid class which contains all the code mentioned above, and then derive two classes from Humanoid: Dwarf and Goblin. Finally, I just need to implement the weapons. I know: I’ll derive Hammerdwarf and Axedwarf from Dwarf and Swordgoblin from Goblin.

Sweet! There is zero code duplication. What’s that? You want an Axegoblin? That’s fine, I’ll derive Axegoblin from Goblin.

The classes Axedwarf and Axegoblin duplicate code for axes but that’s okay, right? NO! If, in the future, I want to change how axes attack in the game, I’ll have to go through every Axe- class and make sure I don’t miss any. Code duplication is bad!

Okay, I know: I’ll just make an Axewielding class and Axedwarf and Axegoblin can inherit from that class.

This seems like a good solution, but it has hidden dangers. Letting subclasses inherit from multiple parent classes is called multiple inheritance. Multiple inheritance is so dangerous that it’s forbidden in many languages, including C#. In C++, multiple inheritance is supported, but it’s a bad programming pattern for our purposes because of the diamond problem.

This example demonstrates the pitfall of inheritance: a rigid inheritance tree. This rigidity works well for many relatively static systems, but for a dynamic system like a game with bits of content flying around it falls apart. What if I want a dozen types of weapons and hundreds of races (I do)? What if I want my Axedwarf to be able to drop his axe and pick up a spear during the game (I definitely do)? There’s a better solution.

What is Composition?

Composition is simple: let’s use the HAS-A relationship instead of IS-A. Every entity is just a bag of components.

The bottom six components on both Axedwarf and Axegoblin represent the components that all humanoid NPCs share.

Now it’s easy to reuse all the common code between Axedwarf and Axegoblin. If I want to change an entity while the game is running, it’s a simple as removing and adding components. I can now remove the Axe component from my Axedwarf and give him a Spear component, and everything runs fine.

NB: Inheritance can be used inside of composition. For example, the Axe, Shortsword, Spear, and Hammer components could all inherit from Weapon.

What is the Entity-Component-System Pattern?

ECS is a specific architecture that utilizes composition for code reuse. NB: ECS is a much more specific term than OOP; OOP is a programming paradigm, whereas ECS is a specific architecture.

Using composition, objects are built using entities and components, while systems operate on the two. Entities are just an ID number and an array of components. Components are only data. All logic goes into the systems, which iterate over components. Components are units of data like Position, Health, Axe, Sprite, Collider, while systems like Physics, AI, Combat, Rendering would iterate over the components.

It’s easy to get confused here: you can have entities and components and composition without using an ECS architecture. For example, (standard, non-ECS) Unity uses entities and components but does not use systems. In Unity, components pull double duty, holding game data and game logic, enforced by inheriting game cycle functions from Monobehaviour. In ECS, the game logic is separated into systems, a concept not present in (standard, non-ECS) Unity.

However, this is not yet the ECS that everyone is talking about. Nowadays, when people say ECS they are referring to ECS with a specific data layout. For the rest of this post I too will use ECS to mean “the ECS with the good data layout.”

In ECS, related components are stored together. The exact layout is dependent on the type of ECS, but the key is that in ECS, components are arranged in memory by type not by entity.

In (standard, non-ECS) Unity, entities are stored with their components. For example, in memory, all the components on my Axedwarf would be stored together, and and all the components for my Axegoblin would be stored together.

In ECS, related components are stored together. All of the physics components (taken from all the entities using physics) would be stored together, all the combat components would be stored together, etc. My poor Axedwarf‘s components would likely be scattered across different regions in memory. Instead, ECS guarantees that my Axedwarf‘s Health component is next to my Axegoblin‘s Health component, their Axe components are together, and so on.

Why ECS? It’s Fast

ECS is just fast. I believe (you can trust me, a random guy on the internet) that any game that uses more than 20 MB of non-graphics data would get better performance on ECS instead of OOP. So, basically all of them.

The Technical Explanation

In brief: Data locality minimizes cache misses.

In long: CPUs nowadays are really fast. Your processor can crunch a bajillion numbers per second. The bottleneck (for the CPU, ignoring rendering) is in fetching data from RAM (or, the horror, your drive). To combat this, the CPU tries to predict what data your program will use and preemptively brings additional data into the cache. So the bottleneck then becomes how effectively does your program utilize the cache?

Both OOP and simple entity-component architectures like non-ECS Unity generally lay out data terribly for the cache. When the physics system iterates over all the physics components in a scene, it has to skip to nearly random places in memory as it goes from entity to entity. ECS places related components together in memory, so iterating over a component type optimizes cache usage.

The “Duh” Explanation

I can also just point to the fact that Unity is overhauling their engine to ECS. Unity wouldn’t spend so many resources rebuilding their engine and asking developers to learn a new, less intuitive programming pattern unless it really is vastly, universally faster.

Why ECS? Good for Procedural Generation and Simulations

For simulation or procedurally-generated games, ECS can actually be more intuitive than OOP-style programming. OOP-style game programming is very intuitive for games with fewer, more complex objects with significant graphical assets associated with them (think Blueprints in Unreal or Prefabs in Unity). OOP works well with visual editors, like designing an FPS level by hand with drag-n-drop.

For simulation and procedurally-generated games with few graphical assets, programmatically designed levels (or no levels at all), and an emphasis on complex, interlocking systems, ECS can be much more intuitive.

An AI Aside

This is specific to my project — I want to make a complex AI system with as much decision-making potential as is possible, modeled on cognitive architectures like SOAR. Such systems require that the agents have the capability to know and understand the state of their world at a fundamental level. Agents must be able to query the world state, understand which actions it can take on which objects, and judge which possible actions will help it achieve its goals.

Useful and general state representations commonly are variants of first-order logic. The entity-component pattern, where all of the state representation resides in the components, components are small and dumb, and it is very fast to iterate over all entities with component X, easily lends itself to a sort of first-order logic state representation. With a few special component types denoting relationships between entities, all state information can be contained within a single, performant, and well-defined data structure: components.

Want to Learn ECS? Go to Github

Despite moves towards ECS in various engine communities and Unity’s ECS push in their DOTS stack, there’s surprisingly little literature on the Entity-Component-System paradigm. Honestly, if you are trying to learn ECS, your best bet is to read through the source code of open-source ECS packages.

There are several great ones in C++: I looked at EnTT and EntityX. EnTT is faster and has been used in some high profile projects (Minecraft!), but it contains a lot of very advanced and modern C++ (I’m still struggling with type erasure with templates). I found EntityX more readable, so I started with reading through EntityX and then tried to understand a few of the key features in EnTT that provide additional performance gains.

The author of EnTT, Michele Caini, also recently spoke at an Italian C++ conference about ECS, and his slides are on Github.

Specific Types of ECS

There are two main types of ECS: Archetype and Sparse Set. Overall, archetype ECS is faster in the best case but is more complex, both for the ECS implementer and the game developer using the ECS system. Archetype ECS requires that the game developer tell the ECS system how data will be organized. If the hints are bad, archetype ECS will have reduced performance.

Sparse set ECS is simpler to implement and to use. The game developer generally doesn’t need to consider how the ECS system works and will achieve good performance regardless. The EnTT developer reported that archetype ECS is only faster than sparse set somewhere above 100,000 or 1 million entities, but I’m not sure if his archetype implementation was as optimized as his sparse set implementation. Archetype ECS has a lot more room for optimization.

NB: the EnTT developer also recently added pseudo-archetype functionality as an option in EnTT for maximum performance.

Sparse Set ECS

I’ll start with the simpler one. Sparse Set ECS is very straightforward: each type of component has its own component manager, which guarantees all the instances of a component are stored contiguously in memory. In other words, every component class gets its own array.

For good performance, Sparse Set ECS relies on a clever data structure: the sparse set. At a high level, the sparse set uses two arrays, one sparse and one densely packed. The dense array stores the actual components (maximizing data locality) and is the array used by systems when iterating over components. The sparse array is a hashtable that is indexed by entityID and points to the dense array of components. The sparse array is used by the entity to access its own components. I’ll go into implementation details in the next post, since I implemented a sparse set ECS.

Let’s cite! My knowledge of this type of ECS is almost entirely drawn from the EnTT source code and information disseminated from Michele Caini.

Archetype ECS

This is the approach that Unity uses, and, from the little bit I’ve read, when the developer knows the data layout in the game, approaches optimal data layout.

In Archetype ECS, components may be grouped into common groups or archetypes. Each archetype gets an archetype manager which guarantees all the instances of an archetype are stored contiguously.

For example, in Sparse Set ECS, each physics component such as transform, collider, and rigidbody would have its own data array. In Archetype ECS, since many entities with physics have those three physics components, the programmer would declare a Transform-Collider-Rigidbody archetype. Then, whenever an entity contains those three components, the components would be chunked and stored in the Transform-Collider-Rigidbody archetype array. This results in just about the optimal data layout for when the physics system iterates through dynamic objects, detects collisions, and moves them around.

The drawbacks are that Archetype ECS is more difficult to code and use.

Hold on, if Unity is moving to ECS, why don’t you just use that?

Unity moving to ECS is amazing, and I’m excited to use it in the future on other projects. I’ll likely eventually use it for some things in this project, like physics and rendering.

I’m not going to use it for the bulk of my game logic for a few reasons:

  1. It’s not ready yet. The documentation is much spottier than the more established parts of Unity, and API changes make life hell. Since this is a long term project, I want to keep up-to-date with Unity versions, so I’d like to avoid non-stable APIs. I also prefer to decouple my core code from Unity for the underlying simulation. I am using Unity for rendering, physics, input handling, UI, and debugging. The simulation itself I don’t need Unity for.
  2. Unity’s ECS is too strict. Unity’s ECS is laser-focused on performance at the expense of flexibility. A major constraint is that components must be structs (for those unfamiliar with C#, C# structs are value types whereas C# classes are reference types). This makes sense: if a component is a class, then you lose related-component data locality (due to indirection when referencing a class), which is the entire point of ECS. However, I want to be able to have the ability to have class components. I’m happy with sacrificing performance for better structure in the more complex areas of my project. What’s more important to me is that everything goes uniformly into a single ECS architecture so I have a consistent interface. Later on I can optimize by profiling components and converting bottleneck classes into structs.
  3. I need lower-level access: To make my AI system feasible, it must be baked into the core engine architecture. It’s much easier to plug into my own ECS system than to figure out how to integrate my AI system into Unity’s ECS system.

Next Up

That’s it for ECS background. Whew, that felt like a chonker of a post. My next post will start on my ECS implementation. I’ll probably start with the sparse set data structure.