Wednesday, November 3, 2010

Game Object Construction Rabbit Hole

Today I want to write a little bit about a boring, yet utterly fundamental part of game engine design: spawning game objects.

Garry's Mod makes it look easy.
Say you have a level that contains a player object and an enemy object.  However these objects are represented in memory, you have to allocate them somehow.  And probably register them with some sort of update loop, and maybe load some other data (graphics, sound?) associated with those objects.  There's a little bit of bootstrap to just get the game into a state where the simulation can start.

So, how do you do it?  How do you get that player and enemy up and running?  This is one of those problems that can be as complex as you choose to make it.

Well, I mean, you could write a function that looks like this:

void startUpGame()
{
   spawnPlayer();
   spawnEnemy();
   // done!
}

Sounds good until you get to level 2, which has two enemies.  You could make a spawning function for every single level, I guess.  It would work, but it wouldn't scale, especially if you have lots of objects to spawn.  I think the average Replica Island level has several hundred objects to spawn, so writing one of these for each level would suck hard.

Long, long ago I wrote a game called Fysko's Playhouse for Mac OS 6 computers.  If that fact alone doesn't date me, this will: it starred the mascot of a local BBS of the same name.  Anyway, back then I had no idea what I was doing, and so when faced with this problem of how to spawn game objects for different levels in a way that doesn't suck, I hit the code with a hammer and moved on.  My solution back then was to write a level editor (in HyperCard!!) that would output start up functions like the one above.  I could draw a level in the editor, hit a button, and out would pop a bunch of Pascal code which I could then copy and paste into the game.  Great!

Well, not really.  That kind of solution works only for very simple games and only when the programmer is the level designer.  And even then it's kind of crappy.  Move a guy 2 pixels to the left and you have to recompile your code.

Some years later I wrote a Bomberman clone called Bakudanjin.  This time I was a little smarter.  Instead of hard coding my level information, I made a map file describing every level.  The map file was basically just a bunch of indexes with XY locations.  To start the level, I load the file and then walk through each index.  The index maps to a table of function pointers (or, since this was also Pascal, a big-ass switch statement) that call the appropriate spawn functions.  Actually, Replica Island works this way too.

And if you just clicked on that link, you can see why this method isn't so hot either: Replica Island only has about 50 different object types and that code is still 6500 lines long.  And a lot of it is copy and paste, because many objects turn out to be structurally similar.  And god forbid you accidentally get your map format indexes out of sync with your runtime indexes; arbitrary enums needing to correctly index into separate arrays is a recipe for bugs.

Still, this is a quick and easy method, and it worked fine for Bakudanjin and Replica Island.  All that code gets thrown out and rewritten when I start a new game, though.

The problem here is that all this bootstrap code is basically code describing data.  I draw a line between "code" and "data" as follows: code is literally programming that instructs the game how to operate.  Data is non-code that is input to the code system.  You feed data into your game and out comes a playable simulation.  Things like enemy placement on a map are subject to lots of iteration and change; the code to actually move an enemy to that location is probably pretty stable and static.  Therefore, the placement information is data and shouldn't live in code, while the runtime for consuming that data is code but can be generic and reused across multiple levels and games.

So in order to write better code and to enable faster iteration and reusability, it's probably a good idea to move more of the information for spawning guys into data.  Moving spawn locations into a file wasn't a bad first step, but we can go further.

What does spawnPlayer() do, anyway?  It probably allocates a bunch of objects, ties them together with pointers, and sets a bunch of parameters on those objects.  Hmm, sounds like something we could represent with just some smarter data.

How about this: we'll make all objects in the world basically the same, make a single spawnObject() function, and then expose a bunch of parameters which we can use to customize the objects and differentiate them.  If we can do that, all we need to do is serialize all the parameters and pass them to spawnObject().  Health = 5, Speed = 10, Sprite = "AngryGorilla.png", etc.

GameObject* spawnObject(ObjectParams* params)
{
   GameObject* object = new GameObject;
   object->setLife(params->life);
   object->setSprite(params->sprite);
   if (params->isThePlayer)
   {
      object->setRespondToControllerInput(true);
   }
   // ...
   return object;
}

OK, that works, but now we have a new problem: it's actually pretty hard to make all our objects exactly the same.  Take the code that reacts to controller input, for example.  That belongs on a player object but on nothing else; with this type of system every single angry gorilla is going to carry that code around, probably turned off with a flag that we serialized.  Or consider what happens when an object is hit.  The player probably wants to get damaged, go into a short invincibility mode, and then go back to normal.  The enemies probably want to get damaged and not be invincible.  If the player dies there's probably some code to cause the Game Over screen to pop up.  Not so for an enemy.

We could make this all the same code and control it with flags, but it's going to become ugly fast.  Maybe if we can refactor our game such that all objects are functionally similar we can ease the pain, but that will make it hard to say, add in little bits of player-specific hacks to improve the feel of game play later.  A better system would be able to generate objects that only contain the code that they need.  If we use the aggregate object model that I often recommend, we could think of this as only inserting relevant components.  In a more traditional object model, we could think about instantiating the object at a particular level of derivation from the base to provide only the necessary set of functionality.  Either way, we're talking about sticking code together with pointers and setting parameters.  Hmm, sounds like data again.

One method I've seen but never tried myself is to define a hard-coded list of object types ("player", "angry gorilla", "banana bomb", etc), and then provide a unique struct of static spawn data related to each type.  For example, the player object would be allocated to contain code for movement based on the controller, and it would read at spawn time a PlayerObjectData struct.

GameObject* spawnObject(ObjectType type, void* params)
{
  GameObject* object = NULL;
  switch (type)
  {
    case TYPE_PLAYER:
        object = new PlayerObject();
        object->parseParams(static_cast<PlayerObjectData*>(params));
        break;
    // ...
  }
  return object;
}

The attractive thing about this method is that you get a chance to control object creation on a per-type basis, but you can also serialize different data for each type, thus avoiding the one-size-fits-all problem.  That should let you move almost all information about this object into data, and just leave this one spawn function in code.

But let's go a step further.  Say we don't want to have to enumerate every object type in code.  If objects are really just collections of data and code, why can't we move the entire structure of a game object into data?

In a language that supports reflection, this shouldn't be too hard.  We can encode an entire object hierarchy, say as XML, and then use it to allocate classes, patch pointers, and set fields.  In a language like Java, we can look up class names by string and instantiate them, and poke into fields to finish constructing objects.  We can imagine some XML that looks like this:

<object name="gorilla" type="com.gorillaboom.gameobject">
  <field name = "mLife">10</field>
  <field name = "mSprite">gorillagraphic</field>
</object>

<object name="gorillagraphic" type="com.gorillaboom.imagefile">AngryGorilla.png</object>

If we write an XML parser to build object trees for us based on this, our entire spawn code can become a single call to that parser.  The parsing code is complicated but generic, it can be reused across objects and levels and games.  And we still have the ability to customize each object because the hierarchy can contain custom classes or be structured differently per type.

GameObject player = (GameObject)constructFromXML("player.xml");

Even cooler, this method isn't even specific to game objects.  We could use it to serialize all sorts of data, even the contents of our main loop.  The code is still code, but once we put the structure in data we have a crazy amount of control.

But, getting back to just the game object application of this idea, there are two problems.  First, this approach requires us to walk the XML object tree every time we want to spawn an object.  We could try to walk the XML once and then use the resulting object tree as an entity "archetype," but that way leads to a particular brand of hell known as "shallow copy vs deep copy." When trying to copy the tree to create a new game object instance, how do you know which pointers should be recursively copied and which should be copied by value?  People have lost years of their life to that problem.

A less practical but ultimately simpler solution is just to re-parse the XML for every instantiation.  Which brings us to the second problem: reading XML and stuff is slow.  I mean, really slow.  Compared to the simple code functions we started with, it's glacial.  And allocation-heavy.  Not something we really want to do during the runtime of a game.

I know what you're going to say.  Hey, dumbass, just use a binary format instead of XML.  Problem solved.  And that's true, to an extent.  Excuse me for a moment while I go out on a limb to the extreme of this line of thought.

If you're going to go to a binary format, why not just store the entire object tree in its native memory format on disk?  Build the object hierarchy offline, write it as binary data to a file, then load it at runtime and just patch pointers.  Boom, instant object tree.  In C++ you can actually do this by building your own reflection system, making liberal use of placement new, and then walking the objects stored in the file to patch pointers.

I've actually written this system before.  It becomes horrifically complicated, but it does work.  A couple of years ago I wrote an engine that could load a binary blob of C++ objects as a contiguous block, walk the objects therein to patch vtables and other pointers, and then simply start using the objects as regular fully constructed C++ objects.  You lose constructers (objects were constructed before they were written to disk) and destructors (lifetime of the object is the lifetime of the blob; individual objects within the blob can't be freed), and god help you if you try to manage those objects with reference counts or smart pointers, but the method does work and it's pretty fast.  To make a new instance of the object tree, you can just memcpy the whole block and repatch pointers.  Cool.

It starts to break down when you need to target multiple platforms, or build your data files on an architecture that does not match the runtime architecture.  These problems are also solvable, but probably not in-place; you'll need to read the objects out of the file and then allocate them at runtime to ensure padding and vtable placement is correct.  And if you do that you're back to a lot of runtime allocation and object parsing.  The system is still complicated but some value is lost.

So for a new code base that I'm working on, I'm experimenting with a slightly different approach.  I still want to use the "load code structure from data" approach, but I don't want it to be slow or architecture dependent (or complicated, if I can avoid it).  And I need to be able to spawn objects with this system dynamically at runtime.  So instead of constructing objects directly, I'm constructing factory objects that can generate new instances of my object hierarchy on the fly.

The method is to read in an object hierarchy as XML.  Instead of building the tree right there, I build a bunch of "instruction" objects--basically the minimal list of commands required to recreate the object tree described in XML.  "Create an object of type GameObject," "Set field mLife of object index 5 to 10," "Point field mSprite of object index 22 to object index 25."  Each of these small "patch" objects gets initialized with a single command (representing a delta from the default state of the object upon construction), and the whole list of patches is stored in a factory object I call a "builder."  Reading the XML is still slow, but I only need to do it once before the game starts; at runtime, when I want to spawn a new object tree, I simply execute the appropriate builder.  The runtime speed is similar to what we had way back at the top of this lengthy post: just a bunch of object allocations and field initializations.  Should be pretty fast.

Builder* enemyBuilder = makeBuilderFromXML("angrygorilla.xml");

GameObject* enemy1 = enemyBuilder->build();
GameObject* enemy2 = enemyBuilder->build();
GameObject* enemy3 = enemyBuilder->build();

One nifty aspect of this approach is that I can easily extend the XML format to do more complicated things by building more complex patch object types.  The basic set of patches (int, float, vector, pointer, string, etc) are entirely generic, as is the builder system itself.  But I can add to that engine- or game-specific patches if necessary.  I've already added a patch that knows about this particular engine's asset system, and can use it to schedule other files for loading, thus allowing for references to external assets which may be loaded in the future (and patched at that time appropriately).  A different game might have an entirely different asset system, in which case I can chuck the one patch written for this game and write a new one against that engine; the system should scale without losing its general purpose core.

The actual XML parser and builder system is very simple--only a couple hundred lines of code.  But I should mention that it only works in C++ because my game engine is backed by a (fairly involved) reflection system.  Using an Interface Definition Language, I can create classes that are laden with meta data, much like Java's Class object.  Using that data I can poke into anonymous classes at runtime and set fields, which is how the patches in the builder actually work.  I think this approach could be done without reflection, but it would basically resemble the hard-coded types with unique static data structs method that I mentioned above.  I'll talk more about the reflection system in a future post.

To bring this giant document to a close, I just want to note that the methods I've described here are hardly an exhaustive list.  These are the various approaches that I've tried to spawn objects in games; there are many others and probably a lot of really good ideas that I've never considered.  But when making a game engine, the question of how objects get spawned--and what a game object actually is, is a pretty huge piece.  Though sort of mundane, it's probably worthy of a lot of thought.

8 comments:

  1. Other kind of object serialization formats (which is really what you're doing when you talk about defining a data format to represent your levels) you might look into besides XML are JSON and Google's Protocol Buffers. They both are easy to output and have good libraries to parse them.

    ReplyDelete
  2. Hi Anonymous,

    The actual text format that I use is pretty irrelevant, as by the time I'm finished with the game I'll certainly be doing all the parsing offline and loading some binary version of the data anyway. They key was that even if I don't go that route and spend time parsing text (be it JSON or whatever, though I wouldn't choose that format for deep hierarchies of objects mapped to each other via a bunch of pointers), I can do it all once at startup and run the game from the output thereafter, so it's ok even if it's slow.

    Protocol buffers are basically another form of the reflective object system that I mentioned, though one with different goals (and different characteristics) than my own. The nice thing about proto buffers is that they can support partial objects, which is what I'm doing with XML here too. The bad part about them is that they can't really be refactored (once you define a required field and write some data with that format, it's there forever until you can also erase the data), they enforce strong interface restrictions when used from code, and (if I remember correctly), there's some cost to map a partial object to its C runtime format. The existing meta system I have supports all of these features (except for the serialization of partial objects, though I could do that if I decided to) and is less restrictive, though as a trade off it does cause code segment bloat. I'll write a post about that system another time.

    ReplyDelete
  3. Enjoying your blog. Trying to find time to build an Android game...

    I used the XML approach to storing level information for my version of Manic Miner, written in C# / XNA for Windows, Xbox 360 and Zune. It uses refelction on Windows (where that is supported) and a big switch statement on Xbox 360 and Zune (where it isn't). I can confirm that this worked really well for this simple game.

    Here's the first level:





















    300000000K0600006000000000000K03
    3000000000000000K000000000000003
    30000000000000000000000000000003
    30000000000000000000000000000003
    300000000000000000000005K0050003
    31111111111111444414444111111113
    300000000000000000000000000000K3
    31110000000000000000000000000003
    30000000000000000333050000000003
    31111000LLLLLLLLLLLLLLLLLLLL0003
    30000000000000000000000000000113
    30000000000000000000000000000003
    30000000000050000000333444441113
    30000111111111111111000000000003
    30000000000000000000000000000003
    31111111111111111111111111111113



    Here's the game running on Zune: http://www.youtube.com/gunston#p/a/u/1/Hykhj5pKj8s.

    ReplyDelete
  4. OK, that didn't post well! Doesn't like my XML! Gah!

    Try this link: http://pastebin.com/NaUeHHgS.

    ReplyDelete
  5. I keep thinking it would be fun to grab the Replica Island code and work out a random level generator to extend game play after beating the game, but that chuck of code you linked to is a bit intimidating for a new like me.

    ReplyDelete
  6. Android's XML resources are actually already compiled down to a binary format. The format is also designed to minimize object allocations and such. Something we haven't exposed is that you can actually do random access to the binary XML tree.

    If random access were exposed in the API, I wonder how efficient you could build this from the binary XML format? For example:

    - You could do a first scan to collect the locations of your object definitions in the XML; later when you want to instantiate one, you can just move to that location in the already open file to read it.
    - To describe properties, you can use the same approach that the view hierarchy does: define attribute resource types, so that the values in XML can be specified with type information (no need to do a string to int conversion at load time), and assign an ID to the attribute name instead of having to do string comparisons.
    - To read properties, the syntax gives you a way to very efficiently retrieve an entire batch of property values you are interested in, and you can then try to retrieve each one you want or iterate over the retrieved values and process them in a switch statement.

    Anyway, there are a lot of things you are talking about that remind me of the same design requirements we have for inflating a view hierarchy from a layout file, something that has been pretty highly optimized in Android.

    ReplyDelete
  7. Hi Dianne,

    Yeah, sounds pretty good! The slow part of parsing XML is definitely the string parsing and allocation; if I can avoid that then I can probably do this at runtime. The other piece is actually looking up fields to set values on; I thought about doing this with Java reflection for Replica Island but eventually decided against if for reasons I can no longer recall. Assuming it's fast to look up a Class object, find fields by string, and poke data into an instance, this might be a viable approach (ideally, I need to be able to construct an entire object in less than 0.5 ms to meet game framerate requirements without a visible hitch).

    In my C++ builder system, parsing the XML is slow and terrible, but once the game is running the actual construction and pointer patch is really fast. No lookups, no string compares, just *(pointer + offset) = blah.

    ReplyDelete
  8. While reading through this I was reminded of reading the source code for Nethack many years ago. Since it was written in C, it didn't have the concept of objects (and related concepts like reflection or serialisation) but it was certainly written in a fairly object-oriented style. There were big static lists of objects broken down into categories (map features, objects that can be picked up and monsters) and these could be instantiated into concrete objects with variable stats (eg, monsters got a hit point value based on ranges laid out in the static structure). All these were serialised whenever the player changed level, when the game state was saved or when a "bones" file was created. Object behaviour was controlled by a series of enums that were relevant to that object type. There were a lot of power-of-two values, so you could combine them to make a creature resistant to fire and cold, say, or give them abilities like being able to wield weapons, eat objects that they come across, or hide from the player, for example.
    Of course, Nethack had (or should I say "has"---it's still going strong) random levels for the most part, but it also had certain fixed levels. This is really the part that blew my mind the most, because it had a level compiler that used Lex (I think) and YACC (Yet Another Compiler-Compiler) to let the designers write up a description of the level at a high level and have this compiled into the code. I know it's pretty common for people to use XML these days for the same task, but it is, as you say, very slow. Nethack's custom language for level description hit just the right note, I think, in that it was quick to edit, achieved good separation between code and data and, most importantly, was quick to parse and compile.
    I know that in some ways a text-only, turn-based game like Nethack is miles away from even relatively simple arcade games like Replica Island, but I still think that there's a lot that can be learned from looking at its source code, especially as it deals with the questions of object construction, level design and serialisation. I highly recommend that you check it out, if you haven't already.

    ReplyDelete