Game Entity Management
In this post: I outline a fundamental, pattern-independent system of storing and identifying base game objects.
Useful background: C++ classes, smart pointers.
A vast majority of tutorials and guides on game programming available online tend to focus largely on the graphical side of things, covering things like OpenGL, SFML etc. Currently, I'm finding myself more interested in the object-oriented design of game engines themselves, completely decoupled from the graphical engines. There's many different areas of study in this department, as well as many different approaches and philosophies, so I'm going to start off by detailing a bit about the fundamental management of game objects within the engine.
Let's start by outlining some terminology. An Entity is going to be the fundamental class for any sort of object within our game engine. An entity could be some physical object like a character or piece of terrain, or it could be a sound source, or it could be an invisible collision area... the possibilities go on. Functionality could be added to the base Entity class through various methods, such as deriving specialisations (e.g. a Solid could be an Entity which undergoes physics) or an entity-component-system pattern (e.g. a MovementSystem could move any Entity which possess a TransformComponent and PhysicsComponent). But, for now, we don't care about any of that. We simply know we have entities, and we need to achieve two basic things:
Declaration:
Definition:
As you can see, this is very straightforward. We typedef'd the ID for abstraction purposes. Don't forget that the static idCount must be explicitly initialised, and also note the usage of the postfix increment operator: idCount is assigned and then incremented afterwards.
Test:
Output:
Testing it out, each entity is incrementally assigned an ID starting from zero. I've tested this using dynamic allocation because we're about to start dealing with entity removal. When we do remove an entity, what happens? Well, nothing much as of yet. Deallocating entity "B" would have no effect on a new entity "D" being assigned the next ID of 3. But, this is somewhat wasteful, as ID 1 is now unused. Sure, unsigned long int gives us a maximum value of 4294967295, so you may think this is nitpicking somewhat. It's unlikely that 4294967295 bullets will exist at once... but it's a lot more likely that 4294967295 bullets will cumulatively exist over the course of the game loop. We need to re-use ID numbers which are no longer tied to an entity. In the class declaration, add a static queue of ID numbers and a destructor.
Bonus: if you haven't already, why not try coding your own queue?
Definition:
I've updated the definition of both the constructor and our new destructor (as well as initialising the static queue). When an entity is destroyed, it pushes its ID number to the back of the queue. If there are previously-used ID numbers waiting in the queue when an entity is created, it will use one of them up, but if it is empty then it will use the next number as per idCount. Let's test this out manually with our dynamic allocations.
Test:
Output:
Hurray! It wasn't really complicated at all, but it's a nice solid base moving forward. In fact, it's all our Entity class needs to be for the scope of this tutorial, as anything further would be moving into a more specific system. We've simply achieved the first of our two goals: uniquely identifying entities. For the second goal, let's look at how to store and retrieve them by their ID numbers.
The first instinct might be to store Entity instances themselves in the vector; this provides very desirable efficiency for access and iteration. However, it potentially poses a crippling problem: slicing. If we're working with a system of subclasses of Entity, these instances will lose their subclass specialisation due to the fixed allocation of the base type. In other words, this approach does not support subtype polymorphism. Luckily, there's a simple solution: storing pointers to dynamically allocated Entity instances, instead. This extra level of indirection, however, impacts the speed of iterating over the collection, so if you're working with a system which doesn't derive Entity subtypes, such as ECS, then you can benefit from storing statically allocated instances instead. Here, I've stored pointers, as it's a more flexible approach for the reasons given.
To make life easier, I've used smart pointers to reduce the load on our garbage collection. The collection stores std::shared_ptr in order to model the manager's ownership of the entities, and it hands out a std::weak_ptr to the requested entity. C++11 smart pointers provide a number of really useful practical and semantic features, so if you're not familiar with them or their syntax I'd highly recommend reading into them.
Declaration:
Our manager provides three abilites: instantiating an entity, retrieving a pointer to an entity from its ID, and removing an entity. This interface allows us to instantiate an entity by name and be given its assigned ID in return. It also gives us a weak_ptr, as the manager should retain strong ownership of its entities. You'll see why I bothered to typedef the collection type shortly as we build upon this framework a little more.
Definition:
The instantiation method is by far the simplest: all it does is allocate a new Entity, create a shared_ptr to it, store that pointer in the collection and return its assigned ID.
The retrieval method is not so straightforward. At the moment, we have no choice but to perform a linear search through the collection until we find the correct ID, then returning a weak_ptr to it.
The removal method is stickier still. Again, we must perform a linear search to find the correct element by ID, but this time we need its array index. Usually, removing from the array in an arbitrary location is of linear complexity, as all subsequent elements must be moved backwards to fill in the gap. However, in this context, the order of the entities in the collection is of no importance to us, so we can perform a constant-time removal by just swapping it to the end position, then popping from the end (don't forget to #include <algorithm> if using std::swap like me, or alternatively write a little swapper template yourself: T temp = a; a = b; b = temp).
Let's test this out! Don't forget that our retrieval method gives a weak_ptr, so we need to check that we can lock() it into a local shared_ptr successfully before attempting to dereference it.
Test:
Output:
Note: retrieval from an std::unordered_map is constant-time on average, but linear at worst due to the possibility of multiple elements existing in one bucket. With the container's default settings, the number of buckets increases when the number of elements would exceed it. We've got a situation in which our keys start from zero and never leave gaps unfilled when increasing in maximum, so we're effectively guaranteed that a bucket will never have more than one element. In other words, we've got constant-time retrieval. It's always a good idea to think about the hashing involved when using an std::unordered_map, and to consider using an (ordered) std::map if the inferior yet guaranteed logarithmic-time lookup would be better in practice.
Declaration:
I decided to typedef the vector index as EntityCollectionIndex, too, for two reasons. Firstly, the size_type member of the container ensures the variable is of precisely the correct type. Secondly, it corresponds to the same style of abstraction as EntityCollection.
Definition:
It's immediately apparent that creating a lookup table has actually simplified our code considerably. The only addition to the instantiation method is that the map entry must be inserted. The retrieval function is now actually a single, constant-time statement. We make sure the entity index exists by getting an iterator to it, before constructing a weak_ptr from the entity vector, returning an empty weak_ptr if it doesn't exist. We can reap the performance benefits of using the [] operator on the entity vector without worry because, by that point, we know for a fact that it is present!
The removal method has been updated in much the same way: we first ensure the entity exists by finding it, then we swap-and-pop the entity out of the vector. Of course, we must also update the index lookup map afterwards, because the entity previously stored at the end of the vector has now moved to occupy the freed space.
Testing this version in the same way, we should get exactly the same results, but an important improvement from linear- to constant-time lookup and removal has been achieved.
But perhaps those are blog posts for another day. For now, I want to have a crack at refactoring my specialisation-based game engines over to an ECS system and see if the latter is all it's cracked up to be.
Useful background: C++ classes, smart pointers.
A vast majority of tutorials and guides on game programming available online tend to focus largely on the graphical side of things, covering things like OpenGL, SFML etc. Currently, I'm finding myself more interested in the object-oriented design of game engines themselves, completely decoupled from the graphical engines. There's many different areas of study in this department, as well as many different approaches and philosophies, so I'm going to start off by detailing a bit about the fundamental management of game objects within the engine.
Let's start by outlining some terminology. An Entity is going to be the fundamental class for any sort of object within our game engine. An entity could be some physical object like a character or piece of terrain, or it could be a sound source, or it could be an invisible collision area... the possibilities go on. Functionality could be added to the base Entity class through various methods, such as deriving specialisations (e.g. a Solid could be an Entity which undergoes physics) or an entity-component-system pattern (e.g. a MovementSystem could move any Entity which possess a TransformComponent and PhysicsComponent). But, for now, we don't care about any of that. We simply know we have entities, and we need to achieve two basic things:
- Entities must be uniquely identified.
- Entities must be stored and retrieved.
The Entity Class
The most obvious way of identifying an Entity object is with an ID number. When constructing an entity, we want it to be assigned the next available integer ID. So, we'll store a static count starting at zero, which the object constructor can take as its ID before incrementing it ready for the next object. We'll also give each entity a name as a string to better illustrate and test them.Declaration:
typedef unsigned long int EntityID; class Entity { private: EntityID _id; static EntityID idCount; std::string _name; public: Entity(std::string); EntityID id() const { return _id; } std::string name() const { return _name; } };
EntityID Entity::idCount = 0; Entity::Entity(std::string name) : _name(name) { _id = idCount++; }
As you can see, this is very straightforward. We typedef'd the ID for abstraction purposes. Don't forget that the static idCount must be explicitly initialised, and also note the usage of the postfix increment operator: idCount is assigned and then incremented afterwards.
Test:
Entity *a = new Entity("A"); Entity *b = new Entity("B"); Entity *c = new Entity("C"); std::cout << a->id() << b->id() << c->id() << std::endl; delete a; delete b; delete c;
012
Testing it out, each entity is incrementally assigned an ID starting from zero. I've tested this using dynamic allocation because we're about to start dealing with entity removal. When we do remove an entity, what happens? Well, nothing much as of yet. Deallocating entity "B" would have no effect on a new entity "D" being assigned the next ID of 3. But, this is somewhat wasteful, as ID 1 is now unused. Sure, unsigned long int gives us a maximum value of 4294967295, so you may think this is nitpicking somewhat. It's unlikely that 4294967295 bullets will exist at once... but it's a lot more likely that 4294967295 bullets will cumulatively exist over the course of the game loop. We need to re-use ID numbers which are no longer tied to an entity. In the class declaration, add a static queue of ID numbers and a destructor.
Bonus: if you haven't already, why not try coding your own queue?
Definition:
EntityID Entity::idCount = 0; std::queue<EntityID> Entity::idRemoved; Entity::Entity(std::string name) : _name(name) { if (!idRemoved.empty()) { _id = idRemoved.front(); idRemoved.pop(); } else _id = idCount++; } Entity::~Entity() { idRemoved.push(_id); }
I've updated the definition of both the constructor and our new destructor (as well as initialising the static queue). When an entity is destroyed, it pushes its ID number to the back of the queue. If there are previously-used ID numbers waiting in the queue when an entity is created, it will use one of them up, but if it is empty then it will use the next number as per idCount. Let's test this out manually with our dynamic allocations.
Test:
Entity *a = new Entity("A"); Entity *b = new Entity("B"); Entity *c = new Entity("C"); std::cout << a->id() << b->id() << c->id() << std::endl; delete b; Entity *d = new Entity("D"); std::cout << d->id() << std::endl; delete a; delete c; delete d;
012 1
Hurray! It wasn't really complicated at all, but it's a nice solid base moving forward. In fact, it's all our Entity class needs to be for the scope of this tutorial, as anything further would be moving into a more specific system. We've simply achieved the first of our two goals: uniquely identifying entities. For the second goal, let's look at how to store and retrieve them by their ID numbers.
The EntityManager Class
Naïve implementation
We'll create a second class which encapsulates the containment and retrieval of entities. For simplicity's sake, this class will handle the very instantiation of entities as part of this, although your architecture may decide to do this using factories or the like. The first thing we must decide upon is the underlying data structure of our collection of entities. We need to be able to retrieve a reference to an entity by its ID, so random access needs to be efficient. Thus, a contiguous structure is the obvious choice -- we'll use an STL vector.The first instinct might be to store Entity instances themselves in the vector; this provides very desirable efficiency for access and iteration. However, it potentially poses a crippling problem: slicing. If we're working with a system of subclasses of Entity, these instances will lose their subclass specialisation due to the fixed allocation of the base type. In other words, this approach does not support subtype polymorphism. Luckily, there's a simple solution: storing pointers to dynamically allocated Entity instances, instead. This extra level of indirection, however, impacts the speed of iterating over the collection, so if you're working with a system which doesn't derive Entity subtypes, such as ECS, then you can benefit from storing statically allocated instances instead. Here, I've stored pointers, as it's a more flexible approach for the reasons given.
To make life easier, I've used smart pointers to reduce the load on our garbage collection. The collection stores std::shared_ptr in order to model the manager's ownership of the entities, and it hands out a std::weak_ptr to the requested entity. C++11 smart pointers provide a number of really useful practical and semantic features, so if you're not familiar with them or their syntax I'd highly recommend reading into them.
Declaration:
typedef std::vector<std::shared_ptr<Entity>> EntityCollection; class EntityManager { private: EntityCollection entities; public: EntityID instantiate(std::string name); std::weak_ptr<Entity> get(EntityID id); void remove(EntityID id); };
Our manager provides three abilites: instantiating an entity, retrieving a pointer to an entity from its ID, and removing an entity. This interface allows us to instantiate an entity by name and be given its assigned ID in return. It also gives us a weak_ptr, as the manager should retain strong ownership of its entities. You'll see why I bothered to typedef the collection type shortly as we build upon this framework a little more.
Definition:
EntityID EntityManager::instantiate(std::string name) { std::shared_ptr<Entity> e = std::make_shared<Entity>(name); entities.push_back(e); return e->id(); }
The instantiation method is by far the simplest: all it does is allocate a new Entity, create a shared_ptr to it, store that pointer in the collection and return its assigned ID.
std::weak_ptr<Entity> EntityManager::get(EntityID id) { for (const std::shared_ptr<Entity> &e : entities) if (e->id() == id) return std::weak_ptr<Entity>(e); }
The retrieval method is not so straightforward. At the moment, we have no choice but to perform a linear search through the collection until we find the correct ID, then returning a weak_ptr to it.
void EntityManager::remove(EntityID id) { bool found = false; size_t index = 0; for (size_t i = 0; i < entities.size() && !found; i++) if (entities[i]->id() == id) { index = i; found = true; } if (found) { //Swap and pop std::swap(entities[index], entities.back()); entities.pop_back(); } }
The removal method is stickier still. Again, we must perform a linear search to find the correct element by ID, but this time we need its array index. Usually, removing from the array in an arbitrary location is of linear complexity, as all subsequent elements must be moved backwards to fill in the gap. However, in this context, the order of the entities in the collection is of no importance to us, so we can perform a constant-time removal by just swapping it to the end position, then popping from the end (don't forget to #include <algorithm> if using std::swap like me, or alternatively write a little swapper template yourself: T temp = a; a = b; b = temp).
Let's test this out! Don't forget that our retrieval method gives a weak_ptr, so we need to check that we can lock() it into a local shared_ptr successfully before attempting to dereference it.
Test:
EntityManager em; EntityID a = em.instantiate("A"); EntityID b = em.instantiate("B"); EntityID c = em.instantiate("C"); std::cout << a << b << c << std::endl; if (auto e = em.get(b).lock()) std::cout << e->name() << std::endl; em.remove(b); EntityID d = em.instantiate("D"); std::cout << d << std::endl;
012 B 1
Efficient implementation
As you may appreciation, a linear-time complexity for both accessing and removing entities is unacceptable in terms of performance. There are a number of options for improving the linear search: perhaps we could keep the vector ordered in terms of entity ID and perform a binary search, providing logarithmic-time? In my experience, the best solution to this problem is to keep hold of an auxiliary data structure: a map of entity ID to vector index. When we instantiate an entity, we also log where in the vector it was stored; then, we can get the vector index from the given ID in constant-time and simply get the pointer at that index in constant-time.Note: retrieval from an std::unordered_map is constant-time on average, but linear at worst due to the possibility of multiple elements existing in one bucket. With the container's default settings, the number of buckets increases when the number of elements would exceed it. We've got a situation in which our keys start from zero and never leave gaps unfilled when increasing in maximum, so we're effectively guaranteed that a bucket will never have more than one element. In other words, we've got constant-time retrieval. It's always a good idea to think about the hashing involved when using an std::unordered_map, and to consider using an (ordered) std::map if the inferior yet guaranteed logarithmic-time lookup would be better in practice.
Declaration:
typedef std::vector<std::shared_ptr<Entity>> EntityCollection; typedef EntityCollection::size_type EntityCollectionIndex; class EntityManager { private: EntityCollection entities; std::unordered_map<EntityID, EntityCollectionIndex> entityLookup;
I decided to typedef the vector index as EntityCollectionIndex, too, for two reasons. Firstly, the size_type member of the container ensures the variable is of precisely the correct type. Secondly, it corresponds to the same style of abstraction as EntityCollection.
Definition:
EntityID EntityManager::instantiate(std::string name) { std::shared_ptr<Entity> e = std::make_shared<Entity>(name); entityLookup.insert({ e->id(), entities.size() }); entities.push_back(e); return e->id(); } std::weak_ptr<Entity> EntityManager::get(EntityID id) { auto it = entityLookup.find(id); if (it != entityLookup.end()) return std::weak_ptr<Entity>(entities[it->second]); else return std::weak_ptr<Entity>(); } void EntityManager::remove(EntityID id) { auto it = entityLookup.find(id); if (it != entityLookup.end()) { EntityCollectionIndex i = it->second; EntityID back = entities.back()->id(); std::swap(entities[i], entities.back()); entities.pop_back(); entityLookup[back] = i; entityLookup.erase(id); } }
It's immediately apparent that creating a lookup table has actually simplified our code considerably. The only addition to the instantiation method is that the map entry must be inserted. The retrieval function is now actually a single, constant-time statement. We make sure the entity index exists by getting an iterator to it, before constructing a weak_ptr from the entity vector, returning an empty weak_ptr if it doesn't exist. We can reap the performance benefits of using the [] operator on the entity vector without worry because, by that point, we know for a fact that it is present!
The removal method has been updated in much the same way: we first ensure the entity exists by finding it, then we swap-and-pop the entity out of the vector. Of course, we must also update the index lookup map afterwards, because the entity previously stored at the end of the vector has now moved to occupy the freed space.
Testing this version in the same way, we should get exactly the same results, but an important improvement from linear- to constant-time lookup and removal has been achieved.
Conclusion
What we've achieved here is a bare-boned system for entities which uniquely identify themselves and are stored in a collection with efficient lookup by their ID numbers alone. How this system would be expanded depends on the style of architecture the engine is aiming for. With a hierarchy of specialised entities which define their own logic, you'd want to make an iterator over the collection which updates each entities' logic. With an ECS architecture, you may want to first alter the vector to store entity instances instead of pointers to them, if you're sure subtype polymorphism isn't needed. The manager class' responsibility of instantiation is also primitive, so you might wish to create something like a factory pattern for more sophisticated instantiation of entities.But perhaps those are blog posts for another day. For now, I want to have a crack at refactoring my specialisation-based game engines over to an ECS system and see if the latter is all it's cracked up to be.
Comments
Post a Comment