iOS Development Optimizations Part 5 – Referencing Entities

Closed

For the next couple articles I’m going to get a little bit more technical, and start delving down into the murky depths of our game engine.

If you’ve done any development for OS X or iOS, you know that apple’s preferred language is Objective-C. †Their top-level frameworks and APIs all use Objective-C to interface and, while many parts are†achievable†from simple C, it’s not what I would call “a fun time”.

Fortunately, Objective-C itself has become a lot nicer about interacting with other languages over the years. †At this point, you can actually intermix C++ and Objective-C in an inspirationally named language called Objective-C++. †We use C++ internally for the majority of our projects, so for our game engine we use a very thin Objective-C wrapper for the out-of-game UI (the menu system, basically) and then jump right into C++.

We use C++ internally in the engine for a few reasons:

  • Familiarity – most of our other projects are written in C++, and it’s the language we’re most familiar with as a team.
  • Type-safety – this is somewhat of a personal preference, but C++ allows me to detect far more errors at compile time than Objective-C does.
  • Portability – an engine written in C++ using OpenGL can actually run on most OSes, including Windows, OS X, and Linux. †Sadly, from my investigation it looks like it’s still not quite workable for Android. †And Windows Phone (which I actually love, btw, but that’s another post) disallows ‘native’ code entirely.

There are a number of popular techniques for referencing entities in a game engine. †There are two big issues to tackle in any solution – object lifetime, and serialization. †Object lifetime is a†particularly†tricky issue – if you try to access an object that has already been destroyed, you’ll at best cause a crash, and at worst corrupt your data. †Serialization is the process of ‘saving the game’, such that any reference to an entity (for example, what enemy a spell is targeting) can be restored when loading from disk.

The first solution we considered was having a master list of entities at the engine level, and handing out IDs unique to each entity. †If you wanted to store a reference, you’d actually store the ID instead, and whenever you needed to access the entity you’d †ask the engine to find it for you. †Usually the engine will store this list as a dictionary of some kind – a hash table, or binary tree. †If the entity you’re asking for has already been destroyed — perhaps the enemy was killed before the spell finished executing, for example — then the engine will return a†sentinel†value (NULL in our case) which you’ll need to remember to check for.

The downside is that any access entails a lookup cost, and that you need to remember to check for dead entities. †The big advantage is that this method is very easily serialized – just write the ID number out to disk along side the entity.

The second solution, and the one we ended up implementing, was smart pointers that reference count objects. †One huge point in favor of this solution is that a library we were already using, boost, provides all of the infrastructure in the form of shared_ptr and weak_ptr.

Reference counting, in a nutshell, wraps an object with a container that counts how many references exist to the object. †Every time a reference is made, the count goes up. †When the reference goes away, the count goes down. †If the count reaches zero — no one at all references the object — we can destroy the object safely. †A special kind of smart pointer called a weak pointer maintains a reference without changing the count. †Weak pointers allow us to say ‘hey, I want to use this object as long as it is alive, but go ahead and destroy it if no one else wants it’. †An example is an entity’s ‘target’ – you want to know who your target is, but allow it to die if someone else kills it.

There’s a different kind of overhead to this method. †Rather than a lookup at access time, there’s a reference count increase whenever a new reference is made to that entity, and decreased when that reference goes away. †Initially, it seemed that this performance cost was far too significant to ever consider this method; fortunately, we discovered a few ways to reduce the cost until it was†negligible.

  • The iPhone threading performance means single-threaded access is better, so we removed all atomic actions and thread-safety from boost. †This cut down on 99% of the cost.
  • We pass constant references around, rather than copying the reference every time.
  • For very tight loops where we know the lifetime behavior, we can cheat and get the raw pointer out of the smart pointer and use that. †This is dangerous, and counter to the entire point of the solution, but we ended up using it in the inner rendering loop.

Strong pointers guarantee that the reference exists and is still alive, but weak pointers may point to dead entities. †However, in order to use a weak pointer you must convert it to a strong pointer – which is a huge reminder that hey, you should probably check to make sure the entity is actually alive before using it!

Smart pointers don’t help with serialization at all, sadly. †Our fix was to add IDs to objects as they are written to disk, and convert all references to these IDs. †Then we can load objects along with their IDs later, and restore the smart pointers then.

This entry is filed under Gaming, Programming. And tagged with , , , . You can follow any responses to this entry through RSS 2.0. Both comments and pings are currently closed.

Comments are currently closed.