Object-oriented programming is very bad for high-performance programs like graphics- and simulation-intensive video games. Or, at least, traditional object-oriented design is.
The main culprit is the cache. If I have some thing in a game—say, an enemy character—then it needs a lot of data associated with it: its 3D meshes and textures, its physics information, its current position, its inventory, its AI state… But not all that information is necessarily being used at any given time. For example, when I am running the AI processing step, or calculating physical forces acting on characters, or drawing things in the game, then I'm only using a small part of all the information associated with a thing.
In a proper object-oriented design, I would take all the information relevant to a thing and package it up in an object: for example, in a
Game_Unitobject. That means, however, that in order to operate on just a subset of that information, I need to pull the object into the cache, which puts all the object's information in the cache. This means the cache gets full of extraneous data, and consequently cache misses become much more common, making the program slower overall.
One way of avoiding this problem is using so-called Data-Oriented Design, which involves pulling apart the data stored in objects and storing it all separately. This has the advantage of being much more cache-friendly, but it generally doesn't have language support, and so has to be done manually. The advantages of typical object-oriented design—like encapsulation and data hiding—are much more difficult to retain, and the language you use might actively fight against you in these cases.
Following a similar path, some programmers have started using and advocating Component-Entity Systems, which are a few steps beyond Data-Oriented Design in roughly the same direction, but also a radically different way of structuring programs. At a high level, Component-Entity Systems work like this:
- An entity is an abstract identifier. It has no other data directly associated with it.
- A component is a table which maps entities to a collection of data, ideally to pieces of simple scalar data. Not every entity needs to appear in a given component.
- An entity can be associated with several components. That means the entity can be used as an index into the component, allowing the programmer to retrieve or modify the associated data stored in the component.
- Operations are written in terms of one or more components. These are sometimes called systems.
This all sounds very abstract, so what does this look like in practice? Let's describe a basic game. For the sake of simplicity, let's assume a we have four salient pieces of information for an in-game unit: its position, its current health, its appearance, and the state of its AI (including current goals and actions):
component Position(int x, int y); component Health(int x); component Appearance(Image img); component AI_State(State st);
Every entity in the game will be associated with one or more of these components: scenery will have
Appearancedata; invulnerable characters might have
AI_State, but no
Health; a player character will have
Appearance, but no
AI_State; and so forth. Well: I've been saying that entities have this data, but it's more appropriate to say they're associated with that data. All the relevant data is stored in the components, and the entity is being used as the index used to access that data. If this is hard to visualize, think of components as database tables, and your entity as the primary key used in all your tables, which you can use to access or update that data. You of course wouldn't want to actually implement a game like that, but it's similar in spirit.
Now, to write the salient operations of our game, we can write them in terms of one or more components: when we draw our game, we write the draw operation in terms of
Appearance, which allows us to loop over everything that has image data associated with it. On the other hand, when we want to move units around, we'll write an operation in terms of both the
Positioncomponents, because we need to know what the unit plans to do in order to update its position.
The advantages of Data-Oriented Design that I described earlier are still in effect, because all the data associated with a component can be stored packed together: looping over the
Appearancecomponent won't bring any non-
Appearancedata into the cache. But Component-Entity Systems have an extra advantage over pure Data-Oriented Design: you gain compositionality in a way that's not necessarily present in other designs. This blog post about applying component-entity design to Bomberman has a section called Consider the possibilities of your new Components, in which the author explores the compositions of components as interesting avenues of discovering new gameplay. It also goes into a lot more detail about what a component-entity approach would look like.
For example: you might design a game with a
Health_Pickupcomponent for items that restore health when a player interacts with them. An entity that is associated with both the
AI_Statecomponents will act as a mobile health powerup that can choose how to move around using some kind of AI routine. On the other hand, an entity associated with both the
Healthcomponents is a health pickup which can be destroyed, perhaps so that it cannot be used by an opposing player. In both those cases, no extra implementation work would need to be done for these conjunctions of components: the new, interesting functionality falls out naturally from implementing each feature in isolation.
While Component-Entity Systems are interesting, there are no languages that are inherently component-entity-oriented. At least, if there are, I don't know about them. Component-Entity System are usually implemented using existing object-oriented languages. So my pseudocode examples above which used the
componentkeyword were all pure fiction. But what would a component-entity language look like?
I'm going to change pace a bit and discuss an old and sadly mostly-forgotten paper: Harrison and Ossher's 1993 OOPSLA paper, Subject-Oriented Programming: A Critique of Pure Objects. The primary motivation behind the paper is addressing what they see as a flaw in object-oriented design: most object-oriented languages include inheritance, and therefore involve a tree of is-a relationships. However, objects don't exist in just a single place in a single ontology: a set of objects can be seen as occupying multiple places in multiple ontologies. As a concrete but slightly fanciful example: do we choose a culinary ontology for our program and write
Tomato extends Vegetable, or do we choose a biological ontology and write
Tomato extends Fruit? What if one part of the program needs one and the other needs the other?
More concisely, as Jorge Luis Borges said: From the Jorge Luis Borges essay The Analytical Language of John Wilkins.
It is clear that there is no classification of the Universe that is not arbitrary and full of conjectures. The reason for this is very simple: we do not know what kind of thing the universe is.
Harrison and Ossher propose that, instead of dealing with objects that are instances of classes, we deal with subjects, which can be seen as instances of classes. Any time an object is interacted with, it is interacted with in a subjective context, in which the data and operations associated with it can be different depending on the subjective context. The only thing shared between the context is the identity of the objects:
The essential characteristic of subject-orinted programming is that different subjects can separately define and operate upon shared objects, without any subject needing to know the details associated with those objects by other subjects. Only object identity is necessarily shared.
Harrison and Ossher's proposed system is in some respects very similar to component-entity systems, but is in other respects quite different. There is certainly commonality: what a component-entity system calls an entity, a subject-oriented language calls an object-identifier or an oid, and both consider entities or oids to be abstract identifiers with no directly associated information.
In a subject-oriented language, an operation must exist within a given subject activation, which exposes pieces of information associated with the entity and a set of operations. An entity can, within a given subject activation, have fields and methods, and those fields and methods can be entirely distinct from the fields and methods exposed by a different subject activation. Every method invocation, therefore, has to exist within a subject activation, so that we know the actions and fields available within that subjective frame.
A salient difference is the way that subject-oriented programming allows certain pieces of information, or certain operations, to be shared among different subject activations. Harrison and Ossher's repeated example involves a
Treeobject shared by, among others, a
Woodcuttersubject and a
Woodcutter's view of the tree has an estimated value, which the woodcutter might use to determine whether the tree is worth cutting down. On the other hand, a
Bird's view of the tree involves its suitability for building a nest in. In both cases, though, they might care about a piece of information like the tree's height.
However, Harrison and Ossher's approach to this issue seems awkward: they suggest that, rather than straightforwardly sharing the height between the subjects, the
Birdsubject and the
Woodcuttersubject should both have their own copy of a field representing the tree's height, and that the two must be made to agree: they must return the same value, or some compatible value (for example, by returning some value which is commutative.) If they fail to agree, the program throws an exception. This is almost certain to be a source of frustration in practice, or at least a major source of gotchas.
The Harrison and Ossher approach also describes how to mediate two distinct object hierarchies, so that different subject activations can use inheritance over the same set of classes in very different ways. (The
Cooksubject, for example, could use
Tomato extends Vegetable, while the
Botanistsubject could use
Tomato extends Fruit, so a given oid can be seen by both as being situated within different hierarchies.) They then go on to describe how one subject's class hierarchy might be incomplete with respect to another subject's hierarchy, and describe how to match those hierarchies together, or infer class hierarchies based on interfaces or other mechanisms.
I would argue that the best thing to do is to combine the high-level details of Harrison and Ossher's subject-oriented language design with the specific mechanisms used in component-entity systems. They clearly have a common starting point and a similar approach to modeling the world, in which abstract entities can be viewed in some context as having associated operations and information. The Harrison and Ossher approach unfortunately gets caught in a quagmire of hierarchies and modeling, but much of that complexity can be alleviated if we treat subject activations like sets of components: suddenly, the
Woodcuttersubjects/systems can simply share the
TreeHeightcomponent, without having to resort to awkward and complicated agreement strategies on the hierarchies or results involved.
As for the specifics of what a component-entity language might look like, I leave that as a creative exercise for the reader. I do have ideas. Someday I will implement them.