The Game Entity series by Michael A. Carr-Robb-John Original http://www.altdevblogaday.com/2011/09/23/the-game-entity-part-v-future-ponderings/ # The Game Entity – Part I, A Retrospect I was recently reminded of an old conversation I had some twenty odd years ago, a fresh faced and innocent programmer (yours truly) was discussing with his fellow engineers the future of CPU technology. At the time we were programming on 8-bit processors (6502 and Z80 CPU’s) the 16-bit processor (68000) was in our sights and we joked about the day when we would enjoy… 128-bit registers! While we knocked around ideas of what we could do with the ocean of unlimited memory our attention did for a time focus on what we could do with Game Entities. We thought there would be so many processors that we could run each individual game entity on a single CPU, we would no longer need to give up processing cycles to rendering and audio, we could dedicate all CPU time to game A.I. and game mechanics. This was in a time when getting 5-10% of the CPU for game A.I. was the most you could hope for. We figured a few things would be built in hardware, path generation (i.e. A*), state machines, physics simulation, random number generation, etc. Coming to the present day, 128-bit registers are here (Yay!) but we rarely program in assembly anymore (Doh!). We have our ocean of memory but no matter how much you have it is never enough (He says looking at a 1024 * 1024 32-bit eyeball texture). Advancements in rendering and audio hardware have shifted a lot of work off the CPU meaning more time to actually process A.I. and game mechanics, unfortunately the thousands of CPU’s we hoped for really hasn’t materialized. Some attempts have been made at physics hardware but it has never truly gained enough critical mass to be worth supporting and it certainly isn’t being built into the console or mobile market. This retrospect got me thinking about our most fundamental game system, “The Game Entity” and its supporting architecture. In the past twenty years we have seen some major jumps forward in almost all areas of game technology, but I’m wondering has the game entity kept up? The last major evolutionary step forward that comes to mind was when components came along a little over ten years ago, what major improvements have happened since then? Have components really solved all the problems it set out to tackle? Is it possible that the game entity is perfect and there are no more major evolutions waiting to be made? Would A.I. hardware with even several hundred low spec CPU’s really give us the ability to make better Game A.I.? Inquiring minds want to know! So what is the current state of “The Game Entity” in the industry today, how does it live, how are we using and abusing it? And very importantly, what can’t it do? This is essentially what my next few blog entries are going to be about, me having a “brain dump” of everything I know about “Game Entities”, Components and the supporting architecture. Maybe by the end we might have a clearer idea of where we are, what’s missing and maybe a glimpse at what might be on the horizon. Sorry to leave you on a bit of cliff hanger, but converting my scribbles into something intelligible take’s time. # The Game Entity – Part II, The Life Cycle and Processing Architecture Continuing a series of posts where I try to detail the past, present and maybe have a glimpse at some possibilities of where the Game Entity might evolve in the future. There is a part of me that wishes I had actually written the entire series of posts for this article up front, it’s proving quite interesting writing about things that are supposed to fit together with future posts that haven’t been written yet. So please bear with me while your reading this, I’m hoping it will all make sense by the time we get to the end. In order to keep things simple here I am going to put aside components for the moment and how they have changed the landscape of the Entity. Although a lot of what I am talking about here is still valid under a component system, I will take a look at the different component systems that I have encountered in my next post. ## The Life Cycle You are born and then you die, the bit in-between is called LIFE! Pretty much sums up most things, bumble bee’s, dolphins, developers, dragons and game entities. Here are the stages of life that most entities go through, this hasn’t really changed that much over time. ### Construction A blank slate, everything is cleared, default values set, pointers cleared to null. I have encountered some architecture’s that have banned the use of Constructors and Destructors in game entities! Usually because of a misunderstanding of how C++ works and usually backed up by the fact that some engineers just can’t stop themselves from doing memory allocations and other nonsense in the constructor. ### Init Usually passed into this stage is some kind of configuration data (usually loaded from the level) indicating how this entity should configure itself, for example its position in the world, physical properties, what visual assets to use, what audio assets to work with, how much health and so forth. ### Resolve Once initialization of all entities has taken place this “second” initialization stage allows us to setup inter-entity relationships, sometimes we referred to this as the “First Frame Process”. For example a doors connection to the navigation system, an elevator to its trigger regions, Characters to possessions, etc. ### Update This is entry point for where all the cool things happen, go crazy, have fun, make awesome things! It’s surprising how often I have encountered an architecture that supports the Resolve stage but engineers have still implement something like this at the top of the Update function: if ( m_FirstFrame ) { m_FirstFrame = false; // Do something interesting that I couldn’t do in the resolve stage. } The reasons for doing this comes down to a simple logic problem, Entity A can’t finish resolving itself until Entity B has resolved! There are several ways in which this could be solved one method would be to introduce a processing priority so that Entity B is always processed before Entity A. Another method would be to split the Resolve stage into Pre-Resolve and Post-Resolve steps. On over forty projects I have never seen either of these possible solutions implemented for two very good reasons first there is usually only one or two game entities that require this “Fix” (or “Hack”, depending upon your perspective ) and secondly even these specific fix’s have scenario’s where they too would not be a good solution. ### Draw The draw stage is called prior to rendering of the entity, usually to allow the entity to configure the renderer with the latest information. ### Deinit It is at this point any assets associated with this entity are released and just to be clear this does not necessarily mean (and usually doesn’t) that the assets get removed from memory. Asset management is another whole interesting subject but not for this post. Cleanup and prepare for deconstruction. ### Destruction The de-constructor should really just be a check list to make sure that before the entity is deleted nothing has been left behind… i.e. something wasn’t correctly deinit. Even the simplest of checks in debug mode that scans the objects memory to make sure everything is zero is in-valuable at catching leaks when something has been forgotten. The seven stages of a Game Entities life, a few systems have the additional pre / post functionality for the update and render stages but generally everything here will exist in most if not all systems being used today (I’m sure someone will correct me if this statement is wrong). ## Processing Architecture How we manage our entities can have a huge impact upon the CPU and this is always an area that can be tailored to the specific game genre for optimal performance. Below I have detailed some of the common core processing systems that I have used in the past. ### Basic frame Processing Usually this is the first implementation of an entity system that we write when we are first learning how to write games, it’s quick, it’s dirty, it’s simple and you would be surprised by how many games that are published still even today using this as their processing architecture. Not that there is anything wrong with this, if you have less than a couple hundred objects and are not trying to push any limits then you don’t need to do anything more complicated. The game loop looks pretty much like this: Update Entities Render ... The biggest problem with this is that it locks the render and update stages into sync with each other. If you wanted to maintain 60fps in your game this would mean that you had to update every entity and render them all in 1/60th of a second. A couple of hundred entities you might be fine with, however if you have several thousand objects, you have a problem, even if half of those objects are invisible (i.e. triggers, markers, barriers). ### Time splice processing Time splicing has been used to great effect on a number of games essentially it spreads the processing over a number of frames. The game loop would look something like this: Update 25% of entities Render ... This essentially means that the game update is running at ¼ of the speed of rendering, with 60fps rendering that would be 15fps update. A variation to this system is to specify how much CPU time is available for processing each frame the system would then start processing entities until it ran out of time then would pause until the next frame. It is worth mentioning that this processing system and the following systems are not possible if you do not have a rendering system that is capable of running independently of the game entity update. By this I mean it must be capable of interpolating position, rotation, animation, etc between the entity updates. ### Variable frame processing Not every game entity needs to run at the same speed, for example the player we might want to run at 60fps but do we really need that magical door that fires fireballs at the player to also run at 60fps, probably not it could run at 10fps with no issues. Variable frame processing allows you to indicate on each game entity just how fast it should update. One major issue to watch out for when using this processing system is that it needs to auto balance itself! Let’s say we gave all game entities an update of 20fps… it would be rather pointless if they all triggered at the same time on the same frame that really would make a lovely spike in the CPU graph. Just to give you a sense of how powerful and useful this can be at spreading the entity processing load, the imps in Dungeon Keeper 2 were being processed at 4fps. ### Level of detail processing LOD processing allows the game entity to dynamically calculate its own fps based upon how far away it is from the focus of attention (usually the cameras position). For example a bird flying 500 meters away might only need to be updated at 1 fps unless it happens to be within 50 meters of the camera in which case it would ramp up as it got closer to say a maximum of 20fps. Obviously this method doesn’t work particularly well if all the game objects are clustered together in a small area. ### Scene Processing Scene management isn’t just for rendering it can be used quite dramatically to control CPU usage, especially when combined with variable frame processing. How you decided to manage your scene can also make a huge difference, an octree, visual cells, rooms, zones, arenas, there are plenty of options. For all these different methods of processing game entities I have never seen a priority system implemented, in fact the closest I have seen to an implementation would simply be to switch two entities round in the update link list. Effective I suppose but extremely clunky. One of the things Nicolas MERCIER commented about last post was multi-threading the entity processing. I have never written a game that has used multiple-threads for processing, I have never heard of any game that has used it either. It obviously makes a lot of sense. However there is something niggling at the back of my mind that makes me think there are some serious issues with this. But the short end of it is that I haven’t had the time to run any experiments. Has anyone out there got their entities being processed under multiple-threads? If so what issues have you encountered? By the way Nicolas, I’m still planning on returning to your comments towards the end of the article around part V or VI. Next blog I am going to talk about the current state of components and how it has evolved and changed the landscape of the game entities. # The Game Entity – Part III, Components Continuing a series of posts where I try to detail the past, present and maybe have a glimpse at some possibilities of where the Game Entity might evolve in the future. ## Components Just over twelve years ago I was putting together additional content for one of my previous games. The content included a new trap that you created like a trap, placed like a trap, even interacted with it as a trap but when it was sprung it would jump off the ground and move around behaving like a creature before eventually returning to a trap again. It sounded great when the designers walked me through the idea the reality of actually implementing it however hit as soon as I sat down to write it, the first issue was where to place it in the entity tree structure. At the time the game used a traditional game entity structure similar to this: ![img1] All the trap functionality of the entity existed obviously in the Trap, and all the creature functionality like navigation and piloting, A.I. behaviors, etc all existed off the Character. Where you place it in the tree also has other knock-on issues to other areas of importance such as the GUI and A.I. systems. In the end since the object was for all intents and purposes a trap I attached it coming off the Trap Entity. What this meant was that I then had thousands of lines of code in the creature that I either had to relocate up the entity tree to the base entity or I used the infamous cut-and-paste (with all the issues associated with that). All of this work wasn’t eloquent, wasn’t clever, was incredibly error prone, caused code bloat and took triple the amount of time it should have taken. The only good to come out of it was a very cool trap for the player and a firm conviction on my part that there had to be a better way of doing things. ### The Component Revolution Components have a number of major features going for them over the traditional game entities. - Self contained – Functionality is isolated into manageable containers - Re-usable – No more cut-and-paste, if you want an entity to have an ability you just need to attach it and depending upon your system can be as simple as a tick-box or an extra line in a configuration file. - Resources Efficent – The entity only uses the resources (CPU & memory) it requires. ### Data Driven Components The purest form of components is the data driven version, it uses configuration data to assemble the entity at runtime, for example: Toggle Switch Render Audio Interactive TwoStageSwitchLogic What is really interesting about this system is that because an entity is constructed at runtime it also means it’s possible to modify an entity while the game is running. Not that I have ever seen this done, but there are some intriguing possibilities with the tech. Under this model the game entity is essentially stripped of its functionality and data, making it for all intents and purposes a blank container, what is left of the game entity is pretty minimal: Name (String) Unique Id World Transform List of attached components. Components written under this model must be bullet proof and because of that you tend to get more stable and robust code being written (always a plus). The only negative really is the slightly higher memory and CPU overhead of handling components. ### Plug-in Components Sometimes the overhead of working with a data driven model is too high especially if you are developing for a platform that has some major limitations (at least when compared to the X360, PS3 or PC) such as Nintendo’s DS, Sony’s PSP, even the PS2 and Wii might not have enough kick. The Plug-in model offers a way to still have components and tap into their benefits while removing some of the overhead of the data driven model. With plug-ins you no longer create entities at run time, instead they are usually declared in code and built at compile time, for example: Class CToggleSwitch : public CEntity { public: EntityDeclare( CToggleSwitch, CEntity, eEntityToggleSwitch ); //- Constructor / Destructor - CToggleSwitch( void ); virtual ~CToggleSwitch( void ); private: //- Plugins - EntityUsePlugin( CToggleSwitch, CPluginRender, m_pRender ); EntityUsePlugin( CToggleSwitch, CPluginPhysics, m_pPhysics ); EntityUsePlugin( CToggleSwitch, CPluginInteractive, m_pInteractive ); EntityUsePlugin( CToggleSwtich, CPluginTwoStageSwitchLogic, m_pToggleSwitch ); }; Obviously this means that the plug-in model has an entity tree structure, however it is generally flat. There is nothing stopping you from creating a more complex structure but personally I have always steered clear of that choice mainly to make sure I never get into the same scenario I was in years ago. ### When Components Go Bad Granularity is the biggest pitfall when working with components, I’ve seen engineers take the entire contents of their game entity and just dump it into a single component. Often saying that because the new component requires all the functionality it made sense to include it all, one engineer even did it so he wouldn’t have to worry about any inter-component interactions. Making components that were so large that they couldn’t be re-used by other entities is one extreme of the scale, the opposite end of course is when components encapsulate such small functionality that the overhead of managing and processing the components becomes more than the cost of the features they provide. A more insidious issue with components to watch out for is circular dependencies as a general rule data should only flow one way, from higher levels to lower levels. For example you do not want your physics component talking directly to your A.I. Brain. ### Component to Component Interactions The simplest method of interaction from one component to another is simply to retrieve a pointer to the required component and make direct calls. The problem with this of course is that you have just made a link between the calling component and the target component. If you wanted to avoid this there are two methods available, the first is by way of an event (or message), sent to the components to either perform a specific task or return some information. The components usually handle this event immediately allowing access to component functionality without necessarily creating a hard link to the component. The second method is the Mailbox, where a message is sent to the component and stored for when the component is ready to process the message. This is usually during its next update phase and gives the ability to completely isolate one component from everything else, the negative side is that it’s a pain to debug and you will start to get latency issues as it can take several frames to handle a message. ### The Processing Architecture Under the traditional entity system calling update on an entity meant everything relating to that entity was processed. One of the benefits of isolating functionality into discrete components is that we no longer need to update everything in one go, we could for example have our rendering components updated during the render phase, the physics components updated straight after the simulation step. I have actually never needed to do more than the basic components like rendering, physics and audio, that however doesn’t mean that it’s not something that can’t be exploited and used if the game would benefit from it. ### Next Time… In part four I’m going to consider the bigger picture of how game entities interact with other game systems. # The Game Entity – Part IV, Game Systems Continuing a series of posts where I try to detail the past, present and maybe have a glimpse at some possibilities of where the Game Entity might evolve in the future. ## Game Systems You might call them systems or managers others call them modules while others prefer singletons. Whatever your pattern of choice at their core they are all the same, they wrap up a mechanism / section of functionality into a self contained handy package. ### The Entity Manager When you have a collection of game entities you are guaranteed that somewhere there is an entity manager lurking in the background creating the entities, maintaining them, handling their delayed deletion, keeping statistical data for profiling, occasionally prodding an entity when it misbehaves, shouting at the youngsters to keep up and trying to keep the world in harmony. From the Entity Manager’s perspective it believes that it has ownership over the entities. As far as it is concerned no other system touches its entities, no-other system has influence over the entities except through the normal entity / component update. How the Entity Manager sees the entity / component connections is like so: ![img2] ### Other Game Managers What the entity manager doesn’t know is that there are a large number of game systems that are not only talking directly to the entities but they are also passing references between systems, compiling them into lists and making major changes to the game entity itself all outside the normal entity update. Some of these systems might include Player Manager, Squad Manager, GUI Manager, Cut-scene Manager, Task Manager, in your average game there are probably more managers that touch entities than those that don’t. So what are these managers doing? Let’s consider the Player Manager, it stores a list of the game controllers connected to the hardware and which controller is controlling which entity. The GUI system might ask the Player Manager which entity “player 1″ is controlling so that it can display the correct HUD information or an enemy entity might ask which entity the player is so that it can focus its attention on the Player. Having the manager store a reference to the player controlled entities means that it can quickly provide the information upon request. A Squad Manager might contain all the information about each squad in the world, which entities are in each squad and each squad’s alliances, etc. It might also handle the higher level thinking required to achieve the objective or goal, once it has planned the required steps it instructs the members of the squad (the entities) to go and do what is necessary. The squad manager might also contain references to other important entities that it needs to track in order to carry out and execute it’s plans, for example kill this character, retrieve that object, move this object from here to here, activate that switch, open this door, etc. The point I’m trying to make here is that there are plenty of managers regularly interfering with game entities before, during and after the update frame usually without much constraint or control other than mechanisms / interfaces that might have been built into the entity. And of course managers are not the only ones that reference entities, entities do it themselves as well. If we were to rebuild the diagram above with all the real connections that are going on we end up with something like this: ![img3] ### Connections How we make these connections to an entity can be done in a variety of methods, the most basic is a pointer to the entity or component. Obviously the biggest issues with this is if the entity itself is deleted you all of a sudden have a dangling pointer with no way of validating before using it. Although I don’t recommend this you would be surprised how many games have shipped using this method with very few issues (mainly because of some good interface design and a fair amount of liquid pixie dust (that’s luck in English) ). Other methods that have been employed with success have been Weak Pointers or Smart Pointers on one project I even got to use Unique Id’s which was great but costly doing the lookup of Id to pointer. The only reason great is because it made a difference to me at 2am in the morning and looking up variables that read within a human context, i.e. entity 15 is targeting entity 89, instead of 0x5feabeda targeting entity 0xa3922ef1. I once encountered GUIDS being used once, and I hope never to see them again! ### The Core Managers Let’s consider for a moment three of my favorite core managers, Rendering Manager, Physics Manager and Audio Manager. These three have evolved from very early on to take advantage of multi-threading and part of that evolution has been to isolate the internal low level data and force any external interactions through an interface or handler. You don’t get the player manager tweaking the audio sample data as it is being played and you don’t have Entities adjusting their vertex data. This is not just because that data might be shared but because this is a good way to protect against multi-threaded issues. ![img4] ### Next Time… In part five I’m going to try and bring this series of articles to a close by considering where the game entity is and what its future might be. # The Game Entity – Part V, Future Ponderings I would like to start by apologizing for how abruptly my last post (Game Entity – Part IV) finished, I actually hadn’t realized just how abrupt it was until it was pointed out to me in the comments. Lesson learned – don’t post when up to your eyeballs with other things. ## Future Ponderings Over this series of posts I have brain dumped a lot of what I know about game entities, how we use and abuse them and the various issues that can occur. While doing this I have tried to maintain a high level perspective, mainly so that I don’t get stuck in any low level nitty-gritty implementation details of one system over another. So what conclusions have I come to in regards to our humble game entity and where it might be heading in the future? ## Entities The Game Entity is very much alive and kicking, it is evolving and still a fundamental part of most games in development today. As much as we all want to move away from the traditional hierarchical tree structure it still has its uses, usually when developing on machines that don’t have enough processing / memory to allow the use of components. In some cases the traditional structure is used because the game doesn’t require anything more complex. I don’t see an issue with this after all it makes sense to use “The right tool for the right job”. ## Components Since components have come along the game entity has lost its grip on the data and functionality it once commanded, now it is reduced to a container or the glue that binds components together. I remember a few years ago trying to sell the idea of components to someone with promises that level designers would be able to put game entities together without the need for taking up valuable programming time. Unfortunately my experience to date has not reflected this and engineers are still building the entities for games, albeit under a system that is a lot more flexible. The only exception and pleasant surprise to this has been when prototyping with Unity3D I have witnessed not only level designers building entities but artists as well. Components evolved out of the issues we had with the bloated game entity, it hardly seems surprising that the Life Cycle and Processing Architecture have not really changed that much from their ancestor. I suspect that as components continue to evolve their architecture will adapt to the components requirements and not the entities they are attached to. Some issues still haven’t been resolved, circular dependencies and processing priorities are just as much an issue under components as they were under entities. In the past we solved them on an individual basis rather than with a major change to the core system. This seems to have carried over to the components as well. Nick MERCIER’s suggestion that components could be placed into processing groups has some interesting possibilities not least of which it seems to offer one solution to the inter-component dependency issue where component A must be updated before component B. At various points during the game (level load, scripted event, etc.) entities are created, components are attached and initialized and then they are left to run within the world. At some point the entities are not needed anymore and they are then de-initialized and deleted. This is common for so many projects you can almost see that we are still thinking in the traditional game entity way. What seems to be slipping people’s minds is that data driven components are dynamic, they can be disabled / enabled, deleted / created even detached from one entity and attached to another. The idea that a game entity could be radically morphed during game play from one thing into another is an area that I don’t believe we have even begun to explore yet (designers take note!). ## Multi-threading The potential gains with a multi-threaded game entity / component system is obviously enormous and just the thought of those extra additional cycles certainly has a fair few game engineers excited, me included. The hardware is going to keep getting better so the sooner we start to take advantage of it the better we will be placed in the future when more cores become available. My main question is why hasn’t it happened yet? Before I answer that question I have to confess that although I have experience working with multi-threaded systems I haven’t actually tried to implement a multi-threaded entities / component system yet. That is on my list of things to do when my current project has finished and I have some free time again. Just making you aware of this in case you think the following is based upon empirical data or hard won experience. Architecture – In order to become multi-threaded we need to change more than just the component system, you need to look at all the supporting game systems as well. Of particular importance is putting under scrutiny how the various systems interact and communicate with entities. What is interesting is the way that Unity3D makes all game systems components as well, maybe this is the way we need to go? It certainly simplifies the problem. Refactoring – I could see it being a bit of a nightmare to retrofit a component system to be multi-threaded, it would certainly be easier to implement from scratch. Memory – It doesn’t matter how much memory you have it is never enough! Splitting a component update into multiple stages (read, execute and write) is going to create additional requirements on the amount of memory entities consume. Educate – When we moved from writing traditional game entities to component based entities a fundamental shift in thinking was required. I suspect the shift in thinking that is going to be required when adapting to multi-threaded components is going to be even larger. The shift from linear entity processing to multi-threaded processing is not going to be a quick over night transition. I suspect that we will convert first the easiest components then expand upon that slowly bringing the other components into the fold. Now that I have said that, someone will probably prove me wrong next week. ## What have I forgotten? I didn’t really get around to talking as much about A.I. and entities as I had originally hoped, maybe I will come back to them at a later date. I solemnly swear I will not write another blog series without first preparing it up front. :) I will also follow up at some point in the future with how I got on writing a multi-threaded entity / component system, keep your eyes peeled! These posts were written while under the influence of coffee, thank you to Taree, Sharon and Roberto at Sip Café for the most awesome coffee in Brisbane.