Saturday, March 10, 2012

The Components and Systems of Morgan's Raid

I've written before about the entity system architecture of Morgan's Raid. I am just now polishing a paper on the topic which I will present at the FDG conference in May. I contacted Adam Martin to get his feedback on the paper, and he was very helpful. He made a few suggestions that I simply did not have space to address in the eight-page conference paper, but since Blogger has no page limit, I would like to address one of them here: what are the actual components and systems of Morgan's Raid?

By way of simple introduction, an entity system architecture is a software architecture in which game object data is stored in simple objects called "components" and these are processed by "systems." Game objects then are simply unique identifiers that aggregate components. This approach favors delegation over inheritance. It proves useful in game development due to the highly experimental nature of such systems: the domain model itself is subject to dramatic change during practically every stage of development. For further discussion, check out the entity systems project wiki.
Numbers of components and systems during development
The figure above shows the growth of the number of systems and components during the development of Morgan's Raid. This figure appears in the paper with a brief interpretation. I provided the small initial set to help bootstrap the students, but most of the rest were written by them—the 25 developers who worked in Fall 2010 and eight who worked in the Spring 2011. I am very proud of the team, don't confuse my pride in their achievement with any claims of elegance and beauty. Indeed, there are quite a few smells in our implementation.

Without further ado, tearing into the source code of Morgan's Raid, we can see how the systems and components are related. (It appears that Blogger automatically scales large images down. You can grab a full-size PDF here.)
System-Component Dependencies
The systems are on the left and components on the right, with edges showing system-component dependencies. As evidenced by the diagram, there are a few components which are heavily used throughout the implementation. OnScreenBoundingBox, for example, is used by anything that involves bounding boxes. (This was originally called Position, but that caused serious confusion when dealing with world vs. screen coordinates. After refactoring, we ended up with OnScreenBoundingBox and GPSPosition, the latter because world coordinates were actual GPS coordinates.) There are a few systems that have no out-edges because they use no components at all. For example, FadingSystem handles the fading of the screen based on time of day, but it does not deal with a component explicitly: it is passed a long integer that represents the current time of day and performs its computation from that.

Several of the components have no in-edges. A handful of them are, sadly, rotten code that was never removed. In fact, some are added to game objects and never accessed by anything else. Others of these disconnected nodes are used directly by the non-system game code. The Morgan's Raid implementation reifies the state design pattern, and there are many places where critical game logic was done directly within these classes rather than delegating to explicitly named and tested systems. This is not ideal, and I ascribe it to the novice level of many of the developers. Ask anyone on the team what they think about the 1700-line behemoth InGameState and they will cringe and tell you it should have been done better, but at the time, they did not know how to actually make it better.

In the diagram above, I have hidden the inter-system and inter-component dependencies for one very good reason. When they are shown, the diagram becomes a bit of a mess. Check it out (or full-size PDF here).
System-System, System-Component, and Component-Component Dependencies in Morgan's Raid

Ignoring for the moment the fact that you cannot discern the system-component dependencies, this diagram does show that the number of system-system and component-component dependencies is relatively low. However, if I were to throw InGameState into the mix, it would have its fingers in practically everything.

The diagrams were generated with dot, and you can download the graph file here. (Note that Google Docs thinks this is some kind of Microsoft file due to naive handling of file extensions. Just download the original and open in your favorite plain-text editor.) I created that file manually by inspecting the Morgan's Raid source code, and so it may contain minor errors.

For your reading convenience, here's a simple tabular view of the systems and components as well.


SystemsComponents
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

13 comments:

  1. I'd be glad to check out the paper when you finish it.

    In my ES / component architecture efforts I have since evolved things past hard coding "components" as data and "systems" as logic. IE for instance previously in the component manager interface of my efforts (IComponentManager) I had setComponent(...) and setSystem(...) with similar getAs(...) and getAsSystem(...) methods that explicitly accepted and returned via generic method signature IComponent and ISystem interfaces.

    In December I finally made the leap with one more generic method modification to allow meta-types. Instead of specific setters / getters for "components / data" and "systems / logic". Things now become in my efforts w/ : set(DATA, IPosition.class, new Position()) and set(SYSTEM, IGameLogic.class, new GameLogic()) likewise.. getAs(DATA, IPosition.class) / getAs(SYSTEM, IGameLogic.class)

    Both DATA and SYSTEM are static includes for IData.class and ISystem.class interfaces and reduce the verbosity a little bit.

    I have also moved away from explicitly calling "data" just "components". IE everything is a component and since my efforts now allow any concrete meta-type I now call "components" -> data components and "systems" -> system components for the two main category breakdowns, but any interface can be defined and create a meta-type and thus a new component type. This certainly future proofs the component architecture for any sort of expansion in concepts in the future beyond "data / logic" boundaries.

    This is kind of nice because really at the core "data" and "system" components don't have any explicit contracts (IE additional defined methods). In a way this separation is more structural or a way of viewing code organization as opposed to a functional organization. Another neat aspect is that this allows "meta-iterators" which are iterators that can iterate over more than one concrete meta-type.

    Anyway.. I'm still plugging away here on my efforts and am ever closer to a release. I should have another early access release in May after AnDevCon III where I'm giving a class on Java performance for Android. I'd definitely be glad to have you take a look at that point or after.

    ReplyDelete
    Replies
    1. Great to hear that you're still working on the system. I'll watch for some news around May.

      Have you had any titles shipped on your framework yet? I wonder what development methodologies it would support, and whether any particular type of gameplay is most applicable.

      Delete
    2. I can't get enough of ES & data oriented design discussions.

      I'm working on it daily and have been lucky to be able to do so full time+ in the last year. I do have to pick up a new 3rd party contract to keep the lights on soon, so that may delay the public launch a bit as I need a little breathing room to make sure that I have at least 6+ months run time to make sure things go smooth on launch. IE I'll only be considering outside investment after the public launch and traction is ascertained.

      There are no shipped titles yet, but there is a good chance the client (a major Android OEM) I am negotiating with currently may license it for a big project in scope / accessibility as a shipped example.

      I expect to be able to get out the next early access release in the May / June time frame that should be suitable for early adopters to work in confidence towards 3rd party usage without all too much changing. Things should be reasonably stable by then and an initial round of documentation available.

      On development methodologies... It's kind of funny because the process of finalizing my efforts has been anything besides lean per se, but usage of the framework should allow lean methodologies, quick prototyping, agile dev, to more structured approaches. The framework itself supports any type of app development including game dev, but the focus has always been on real time app / game dev to provide the basis for performance & tuning the framework. I have generalized the base ES concept to a framework / app wide component architecture of which the ES is an extension of instead of just being an isolated subsystem. IE OOP is down played significantly across the framework. For instance this being contrasted against say combining Artemis w/ Libgdx (OOP / static class based).

      For gameplay considerations an FPS has been my base test case, so it should be able to hold up for any style from a performance angle. Android support of course also has provided plenty of opportunity to work on speed & memory footprint where if one was just concerned with a desktop implementation these constraints might be overlooked. Unity is great and while I haven't used it firsthand I've heard a lot of people mention that it does certain types of games well and others not so much. As a base framework I'm really keen to make sure there are no limitations on what can be built. Granted some of the editor tooling may lead to a little bit of the gameplay / style lock in of Unity.

      What has taken a while is to rewrite all of the existing OOP code in a more data oriented design / component oriented direction and the framework & runtime itself is highly modular thus a good deal of time is spent having to manage and do a lot of tedious file system / IDE project file manipulation of ~700 separate projects until things are finalized. This has been done for long term maintenance as precise dependencies of various runtime / SDK components are well known and a ton of time has been spent to minimize dependencies framework wide in addition to reconfiguration possibilities as this allows the runtime & framework to be configured from a minimal setup to one specific to game dev or other vertical app category. For instance one such category I'll be looking at supporting is Android@Home / ADK.

      The end user doesn't necessarily have to work with the separated projects directly. The planned build system and additional tooling should take a lot of the configuration pain out of using the framework. Unlike Unity though there is no visual editor yet, so devs do need to roll their own engines or use premade components and work with the code directly as an SDK. The general progression seems like the configuration tool will blossom into a more full featured editor in time.

      Delete
  2. So I did get 15 minutes to check out the Morgan's Raid ES implementation. Indeed it works, but as you mentioned there are inefficiencies and various smells. :) Not bad though for getting a class of undergrad students in on the whole ES concept.

    One that particularly stuck out is the inability to store a component under a related interface. Since the addComponent method of an EntityManager explicitly calls the getClass() method internally. This can certainly help reduce the dependencies between components. You probably noticed in the method signatures I posted in my 1st post that with my efforts one can explicitly pass in a type for the component. Of course there are simpler method sigs that will also take a component and internally call getClass() to assign the type.

    adding this method sig to EntityManager should solve this and allow an interface to be specified for the type of the component; just use it instead of calling getClass() internally:

    Entity addComponent(Entity e, Class type, T component);

    I suppose one other larger limitation is not being able to easily store a collection of components by type and more than one single component by type or extended marker interface. I've found that being able to iterate over a collection of typed components contained by an entity to be a powerful design pattern that leads to being able to replace OOP as a design mechanism for the most part.

    Anyway.. Good deal. I'm definitely interested in hearing more about the teaching experience as no matter what context there is a bit of an up hill battle w/ the ES concept insofar to increasing awareness in industry or academia. In other words OOP still rages strong.

    I suppose the neat thing is that technically with some minor modifications the components / systems you created could be translated to my efforts and Slick still could be used rather than my the GL API / layer. In a away the ES concept is "POJOesque".

    ReplyDelete
    Replies
    1. ahh yes. Blogger.. stripping my "HTML"... * is the new bracket..

      *T extends Component* Entity addComponent(Entity e, Class*T*,
      T component);

      Delete
    2. The issue of aggregate components was never elegantly handled. The best we had, as you may have seen, was that some components are ListOfX, where X is another component type. I didn't like this solution, but it was least painful at the time.

      Can you elaborate on the point of "storing a component under a related interface?" I'm not quite grasping why one would want to do this, when the data objects themselves are already strongly typed. That is, it's not clear to me what is lost by using getClass to get runtime type information from the component as opposed to your approach that adds a type parameter to addComponent.

      Delete
    3. On the matter of collections you could extend the EntityManager interfaces to offer addComponent and removeComponent methods and in the BasicEntityManager have an additional Map of Maps that holds a collection rather than a single component.

      private final Map*Class*?*, Map*Entity, Collection*? extends Component** entityCollectionStore = Maps.newLinkedHashMap();

      Granted you already have a removeComponent method.. In my efforts single components have set / unset methods for storage and add / remove methods to add / remove a component to a collection.

      Instead of retrieving a collection directly in my efforts there is a getAsIterator method which retrieves a "protected" iterator interface that allows iteration over the stored collection without the dev being able to remove a component or modify the stored collection externally. IE one must always use the add / remove methods of the entity.

      I do have a whole custom collections API that adds a bit of functionality.

      ---

      On the use of interfaces as the component type vs a concrete class it limits the internal dependencies exposed by the components / systems that are aggregated in other components / systems or entities. In my efforts there are multiple set methods and one just like "addComponent" that doesn't take an explicit type and the type is inferred from getClass() internally, so this is supported as well.

      In the case of Morgan's Raid the entire project is essentially one module, but in a larger game one may want to separate various components / systems into multiple projects. By using interfaces as types one can reduce the dependencies between the projects / modules to a minimum. To do this I often create an implementation project / module which may have extensive dependencies for the component implementations and a commons project / module that contains just interfaces for the components. The implementation module of course references the commons module, however other external projects / modules only reference to commons module thereby potentially reducing dependencies between projects / modules quite a bit.

      Delete
    4. One major difference in my efforts is that components are stored locally in the component manager. An entity extends a base component manager, but is marked final for no further extension. In addition to being able to store single components by type one can also store components by type in a collection as well.

      The final trick of sorts in my efforts is the ability to store more than one single component (or even collection) by an extended marker type rather than being forced to put it in a collection or even worse a component proxy of sorts that simply exists to aggregate multiple components. In some cases it is useful to directly index two or more components explicitly rather than finding them in a collection. I suppose it could be an extended class, but I do this through an extended marker interface.

      An example would be say a space shooter where more than one missile launcher could be attached to an entity. There is a base IMissileLauncher interface for the MissileLauncher component. Extended marker interfaces may be ILeftMissileLauncher and IRightMissileLauncher. Two MissileLauncher components can be added to the entity indexed by the extended interfaces. A little generic method extension allows this and an additional addComponent method would look like this:

      *T extends Component* Entity addComponent(Entity e, Class*? extends T* keyType, Class*T* type, T component);

      entityManager.addComponent(spaceship, ILeftMissileLauncher.class, IMissileLauncher.class, new MissileLauncher())

      entityManager.addComponent(spaceship, IRightMissileLauncher.class, IMissileLauncher.class, new MissileLauncher())

      An addition getComponent method is necessary to retrieve the components stored by a marker interface:

      *T extends Component* T getComponent(Entity e, Class*? extends T* keyType, Class*T* type)

      entityManager.getComponent(spaceship, ILeftMissileLauncher.class, IMissileLauncher.class)

      retrieves the left missile launcher by the IMissileLauncher type. The concrete MissileLauncher component implements IMissileLauncher, but has no connection between ILeftMissileLauncher and IRightMissileLauncher. Through the generic method signature though one can use the keyType when getting the component for retrieval, but casted by the given type.

      IE ILeftMissileLauncher is simply:

      public interface ILeftMissileLauncher extends IMissileLauncher {}

      That is a way to get around having to create an intermediary component that internally stores one or more components while still being able to access them directly. It also gets around having to store multiple component in a collection. A collection is useful for iterating over a series of components, but is laborious when having to track discrete components; IE left or right, etc. as then one has to consider where they are and track which position they are in a collection. The extended marker interface allows direct access to multiple components of the same type directly.

      I suppose some of the verbosity is less than desired, but this has proven useful in my efforts.

      Delete
    5. Finally had a chance to sit and really read through this. Very interesting work! Thanks for making the time to clarify it.

      Delete
  3. "... I am just now polishing a paper on the topic which I will present at the FDG conference in May"

    Is that paper of yours published yet?

    ReplyDelete
    Replies
    1. Not just yet. I present it at the end of the month, and it will be published in the proceedings. In case you'd like something sooner, here's a prerelease version: https://docs.google.com/open?id=0BzmiDU0yxmJwZWJaQTQ1Nm1GZ28

      Delete
  4. Hello,

    I tried to download the source code but I get an error when running the .jar file..Is there any other way to access the source code? (I can run the game itself without issues)

    ReplyDelete
    Replies
    1. Don't run the .jar file---extract its contents. I believe it's an export of the Eclipse project, so you should be able to "import existing projects into workspace" from Eclipse.

      Delete