Tuesday, September 8, 2009

Aggregate Objects via Components

I used to make games like this:

class RenderableMovingCollidableGameObject extends RenderableMovingGameObject {
   public void update() {
      super.update();   // Parent classes implement rendering and movement.
      // implement collision detection here
   }
}

class PlayerObject extends RenderableMovingCollidableGameObject {
   public void update() {
      super.update();  // Run rendering, movement, and collision.
      // update the player
   }
}

...
// Main loop!
while (true) {
   InputSystem.update();  // poll for input.

   for (gameObject : ListOGameObjects) {
     gameObject.update();
     gameObject.draw();
   }
}

This isn't a bad way to start making games, but it doesn't scale. Making a good game requires flexibility and the ability to iterate quickly, and this approach starts to break down when the game becomes medium-sized. What if we have more than one game mode? What if the behavior of a specific game object needs to change for a short period of time? What if Level 27's version of the player needs to be subtly different than Level 26's?

In a nutshell, the problem with this approach is that the structure of the code producing a single frame of the game is hard-coded into the program. What I want is something that can change its structure between levels, or between game modes, or even on the fly. I need something more dynamic than a hard-coded for loop.

Another Approach

Let's look at game objects as an example. Game objects are entities in the game world like coins, enemies, moving platforms, and the player. They often have similar functionality, so one way to go about implementing a set of similar objects is to use an inheritance tree. We can create a base GameObject class, and from that derive RenderableGameObject, and from that derive RenderableMovingGameObject, and from that derive RenderableMovingCollidableGameObject, etc, etc, etc. Each level of derivation can add some common functionality until the leafs of this tree are specific entities, like the player.

The real problem with inheritance trees is that features that don't need to be inter-related become dependent on each other because of the way the code itself is written. Given the example class structure above, it's not possible to make a GameObject that can move but doesn't need to render (short of littering the code with flags--don't do that). Because of inheritance, a dependency between movement and rendering has been created where none actually needs to exist. What if we could mix and match features on a per-instance basis rather than tying them all together in a class hierarchy? This is where object composition comes in.

Object composition (or "object aggregation" depending on which design patterns book you read) is the idea that an object "has a" feature instead of "is a" feature. Rather than using inheritance or some other code-side method of collecting functionality together in a single object, we make the object manage a list of separate feature objects; the contents of that list can be different per instance.

So for Replica Island, I have a GameObject class that contains a list of GameComponents. A game object with an empty list does nothing; it can't be drawn, or make noise, or hit things, or do anything else to affect the game. GameComponents implement all of those features, and they must be inserted into the GameObject for it to actually be able to act. Here's some psudeo-code of how GameObject and GameComponents work:

class GameObject {
   private Array<GameComponent> mComponents;

   public void addComponent(GameComponent component) {
      mComponents.push(component);
   }

   public void update(float time) {
      for (component : mComponents) {
         component.update(time, this);
      }
   }
}


class GameComponent {

   public void update(float time, GameObject parent) {
      // ... functionality goes here
   }
}

A GameObject just runs all the GameComponents it contains to produce its output each frame. GameComponents in Replica Island implement things like movement, physics, collision detection, sprite animation, rendering, animation selection, AI, player control, etc. Once a generic GameComponent is written it can be inserted in any number of objects; if a specific object requires special functionality, a new GameComponent can be written just for that object without disturbing anything else in the system.

The beauty of this approach is that individual components can be compartmentalized features, and brand new objects in the game world can be created just by sticking different pieces of pre-existing code together in new ways. The result is also dynamic: unlike an inheritance-based object, Replica Island game objects can change their structure at runtime. For example, one of the Android robot's powers is to possess other robots. When an enemy robot is possessed, his AI component is removed and a new component that lets the player control him is inserted. All of a sudden the robot is being driven by the player; all the rest of his code for animation selection, physics, and collision detection, continues to work without realizing that anything has changed. When the player releases the robot, the original component structure can be restored (actually, in this case the robot blows up, taking out anything else near it, but you get the idea).

I've made a couple of games now using components and I'm very happy with the result. In Replica Island I took a couple of shortcuts for speed that damage the goal of completely independent components, but I think it was worth it; the sacrifices I've made for frame rate haven't actually proved detrimental to the flexibility or extensibility of the system.

21 comments:

  1. It's great to see this blog up and running. I saw you detail this design pattern on the Google I/O and it's really helped me a lot. After refactoring from a simple update loop (update physics, update AI, update video, update audio ... eugh..) my code is so much easier to deal with. Looking forward to future posts and of course the game's release!

    ReplyDelete
  2. Again this is a great practice and I'll try this in my next game project for sure. Thanks!

    ReplyDelete
  3. I will have to pull an old project or two out and try this; very intuitive way to handle game objects. Another great post.

    ReplyDelete
  4. How do you share data between components? Or is that the idea...you're not supposed to. For instance, position is most likely shared between the physics, mover and renderer components. In which component is this information kept (or is it put in the GameObject itself)? If it is in one of the components how is this information shared between components in a flexible and efficient way?

    ReplyDelete
  5. > Anonymous

    Good question! I could actually write a whole post on this topic, as there are a lot of different approaches and they all have different side-effects. I'll tell you about the ideal system, systems I've made in the past, and the slightly more practical system Replica Island uses.

    In theory, the whole point of components is to reduce dependencies between snippets of code.

    To that end, it would be best to not have any explicit data dependencies (e.g. hard-coded fields in some class). Instead, I think that an ideal system would be able to track "active data" in some sort of bookkeeping system that individual components can read and write from. Just as components can come in and out of scope dynamically, a system for managing fields that come in and out of scope at runtime would be the best approach. Then you could truly write compartmentalized components that with no hard dependencies.

    In the past I've implemented a simple version of this kind of "active data" system with a blackboard or tuple space. The idea is that there's a managed block of memory shared amongst all of the components (one per game object) which all components can read and write name/value pairs to. This way one component can own a field (say "position"), write it to the blackboard, and other components can then subsequently modify it (or do nothing if the field doesn't exist).

    The problem with this sort of approach is that a) it added some fairly significant overhead to common field access, and b) it's pretty hard to debug. (a) is a tractable problem in C++ because you can rely on inlining and a fast hash table to remove much of the overhead. In Java, it's a lot more of an issue. (b) is a problem in any language--you suddenly lose your ability to see common member fields in a debugger.

    So in Replica Island, I went with a considerably less flexible but far simpler and faster solution. First, I push common state (such as position) up into the GameObject class. In fact, the only real difference between a GameObject and any other ObjectManager is that GameObject has position and some other high-level state. I try to keep the state stored there as implementation-neutral as possible. There's some high-level info about recent collisions, movement "style", and position in there, but that's all--nothing that is linked to the implementation of any specific component.

    In cases where I do need to link components more directly, I let one component keep a reference to another. Example: the sprite component needs to pick a texture to draw every frame, but the render component is the thing that actually draws it. So the sprite component takes a reference to the render component and sets a new texture on it every time the sprite frame changes. This is a dependency between these two objects, but it's one way--the sprite component depends on the render component. I could still make derivations of the render component if I needed to, but so far that hasn't been necessary. More likely is that in the future I'll have some other system that talks to the render component, which keeps the render component itself compartmentalized.

    ReplyDelete
  6. Here's an idea that I came up with while waiting for your response (thanks for the quick response). The idea would be to add a key/value-based data structure (e.g. Map<String, Object>) to the GameObject class, "fields". When components are added to a GameObject they would register fields that they wanted to shared with other components. Other components would then pick-up (probably set their own references for speed) these fields when registered with the GameObject.

    I know. There are several drawbacks to doing it this way. Memory, there would be many additional references to the same object (the GameObject's reference, the owning component's reference, and any downstream component's reference). Managing dependencies, preventing upstream components from being removed while other downstream components still rely on it's state. There are probably others too.

    It should be fast. Each component would have their own reference to shared state. Lookups (and casting) would only be required when adding/removing components from an object. However, this should still be pretty fast, at least fast enough to use for game play.

    This would be totally useful for developing a content editor. A component could be developed for listing the GameObjects fields in the editor's UI. As components are added, fields for configuring that GameObject would show up in the UI. That would be pretty neat.

    ReplyDelete
  7. > scribwai

    This is the right idea, and very similar to the blackboard system I mentioned. However, it's going to be slow because you need to do the lookup every frame (or, in the best case, at some frequency higher than "once").

    This is because components can come in and out of scope. Say a component suddenly gets inserted into a game object in order to apply new functionality (the "I've been turned to jelly" physics component or whatever). That component may register new fields that other components might be interested in. So you'll have to do this check at runtime, either every frame or based on some "component contents changed" event.

    Depending on how often this happens, a "reassess your fields" event might be sufficient. Component changes don't happen very often in Replica Island. But you probably can't just cache the references at startup and then rely on them thereafter.

    ReplyDelete
  8. After watching the Google I/O talk where you mentioned not to use interfaces, for a moment there I was scared that this actually means no OOP. I'm not an expert in low-level Java but it looked to me that calling through an interface reference is about the same thing as calling through a parent class reference.

    For someone like me that until now only worked in Java business projects where performance is always traded for scalability/flexibility this would be murder :)

    However I did a quick test, and came up with the following results:
    - On PC (sun-jdk), calling a method through an interface reference is as fast as any other method call.
    - On Android phone, calling methods through an interface reference is about 30% slower.
    - However, calling a method through a reference to a parent class it's as fast as calling the method through a direct reference.
    - Static methods are not significantly faster neither on PC nor on Android.

    Not sure if my test was very scientific but it's good enough for me. Wohoo! OOP for life :)

    However, I totally agree with using compositions over inheritance as often as possible. In my business projects I used a similar architecture as yours, where main entities have pluggable "behaviors". It's incredible flexible.

    ReplyDelete
  9. Hi Cristain,

    Yeah, my results were the same as yours. On Android, I saw a 30% penalty for calling a function via an interface rather than directly or via a virtual. That might be specific to the Dalvik VM, I'm not sure. I'm also not sure that those numbers are still relevant--the VM has undergone a lot of improvement since then, so it's probably worth running the test again. But yeah, I got the same results.

    ReplyDelete
  10. I've been thinking about components for a while now, and have implemented a basic version, but I always come up against a wall. I have (at least) two problems that I can't seem to solve elegantly in a component-based system. As an aside, my Java-based component system is much like what you describe - entity with a collection of properties as a blackboard for shared state and a collection of generic components. Properties also implement inheritance from other property lists.

    The biggest problem is the order of updates of components. I don't want to update the rendering for object A before the physics for object B, as this leads to a kind of de-synchronized game state. One solution is to keep components registered in top-level managers that do the updates instead of piping updates through the object's update() method, but that's something I really don't like doing (one manager per component or component type seems pretty fragile, and the instantiation and destruction of objects becomes much more complex). The only other solution I've seen is to provide a "pass" type as part of the update call, but this leads to a lot of unnecessary calls.

    The other problem is special handling. It's all very well to add a CollidableComponent to an object, but collisions need to be resolved on a higher level in a separate data structure. All I've come up with so far is to use the update pass of the component to register or update the component's entry in the collision structure.

    About access to properties in Java, while it is slower than field access, I don't think it's such a big problem. It is possible to reduce property reading and writing to constant-time by using IdentityHashMap and interned strings.

    ReplyDelete
  11. >Stani

    I sort my components by "phases" within each game object. The idea is that it's a not-very-granular sort; within a phase components can execute in any order, but the order of the phases themselves is well defined. This is how I ensure that rendering happens after movement, animation selection, and collision detection without actually making explicit dependencies between the rendering component and the other components that actually move, animate, and collide the character.

    For things like entity-entity collision detection, I do something very similar to what you describe: I have two separate components, a collision registration and collision reaction component. The registration component registers collision volumes with a collision system (which doesn't do any work quite yet). When all game objects have finished, the collision system runs and calculates all collisions. Then it calls the collision registration component so that game objects have a chance to respond (or, as is often the case, wait until the next frame to respond).

    It sounds like you want to run all components of a certain type, across all active game objects, at once. In that case, why no just register each game component with a master list? If you want to sort by phase like I do, have a master list for each phase. Game objects can register all their components on activation and remove them from the list on deactivation (which, if you make it a doubly linked list or something, you should be able to do in constant time). Then, rather than visiting each object at update time, just execute the contents of the master list (or lists).

    Hmm, that's actually not a bad idea. Maybe I'll give that a shot next time around.

    ReplyDelete
  12. Hi Chris,

    I have a question regarding the data of GameComponents. In your pseudo-code you provide the update method of the GameComponent with a reference to the GameObject. Does this imply that your GameComponents have have no 'private data' or own local state?
    In other words: do GameComponents only operate on data of the GameObjects, and therefor there is only one instance of a specific GameComponent?

    I can imagine that for some Components it would be neccesary to have their own data, so the GameObject doesn't need to contain all data fields neccesary for the GameComponent to work?
    This way you would have various instances of components, all with their own data and owner(a GameObject) when registered to a GameObject.

    Edwin

    ReplyDelete
  13. > Edwin

    Both cases exist. Generally my Components do have local data, but sometimes I can make them effectively static. When that happens, I can share the same component instance across multiple game objects, which is great. Often there's a trade-off between speed and memory involved (e.g. I can save memory by sharing component instances but no local data means I can't cache lookups, which might cause more lookups per frame), so I handle it on a case-by-case basis.

    ReplyDelete
  14. Thanks for your clear answer!

    There's still one thing that I'm breaking my head on:
    For example, when spawning a new enemy, do you dynamically allocate memory for the various Components, or do you have a pool of pre-allocated Components that you use when adding these to a GameObject?

    When allocating dynamic, won't the GC come in every time, smashing the fps?
    When using a pool, how do you determine how much to allocate of each component up front?

    ReplyDelete
  15. I don't ever allocate at runtime. All the Components are allocated up front, put into pools, and reused. Pools that are shared are basically stateless, so they can be recycled without problems. Take a look at GameObjectFactory.java for the implementation.

    ReplyDelete
  16. Thanks, will do.
    Great work on the game btw. Just recently played it, it's pretty impressive :)

    ReplyDelete
  17. Really nice blog and explanations of things. Great work.

    I have a little problem on my own, though.

    I'm implementing your Object Composition model into my game and to collect GameObject's into one ArrayList. When I draw things from this collection or call on it for it physicals updates, the GC starts to run every 30 seconds.

    I have watch at your Replica Island source code and I took a look at FixedArraySize.java. Since my game is that far from complicated, I am wondering if I can be able to implement a non-allocating solution within my code?

    Thanks anyways for your awesome blog!

    ReplyDelete
  18. > Johan

    ArrayList shouldn't do allocations as long as you don't keep resizing it. It might allocate up-front when you first insert things, but a GC every 30 seconds indicates some other sort of (fairly dramatic) leak. You can certainly used FixedSizeArray (though the semantics are a little different than a Collections container), but before you do that I'd use DDMS to find where you are leaking. Just putting things in an ArrayList and then leaving them alone shouldn't cause a leak.

    ReplyDelete
  19. > Chris

    Thanks for answering. Yeah, that was probably a mistake of my own, since the GC was firing when my game was upon front, so the problem is solved.

    Thanks again!

    ReplyDelete
  20. Hello again! I meant " was not firing " instead of was firing.

    Although, I've used DDMS and I tried to find where the leaks come from using "Track Allocations" and it seems to run when my application is closed, so therefore, I misunderstood the case.

    ReplyDelete
  21. Very interesting article. I saw that this was written (in IT terms) ages ago but still find this really relevant. I am not even making a game but application in which responsiveness is critical and these tutorials/articles really help.

    ReplyDelete