Accessing game objects by unique ids

Every game keeps its game object in one or more simple collections. These are used for enumerating the objects every frame to update and draw them.

If objects need to refer to each other, they can easily store a reference to another object, and access it directly. This becomes more difficult however, when we deal with a multiplayer environment. In that case, each game will have its own set of object references, which will never be the same.

That means that we need another way of identifying objects.

Further, we want this access to be fast. After all, a network server might send a client the message that a certain game object should be deleted. If we then need to iterate over all objects to find the correct one, we could easily bog down the performance of our game. Those CPU cycles could be spent much better on something else.

Lastly, whatever data structure we will design for this has to be able to respond appropriately to objects being deleted. See this post for a discussion of how this can be done for simple lists.

Requirements

Before we begin writing code, let us make a succinct list of our requirements:

• our objects are assigned a unique identifier,
• we can retrieve objects by their identifier in (near to) constant time,
• our data structure is kept up to date when objects are deleted.

We will design our system in the same order as this list. While doing so we will see that there are several ways of solving this problem. The one I will fully develop here is one I have used in my prototype Syzygy. Feel free to check the game’s code for the full implementation and application.

Creating unique identifiers

There are many ways to create unique identifiers. One that is often used in all sorts of applications is the Globally unique identifier (GUID), a sequence of 128 bits.

For the purpose of this post however, such a system is much too complicated, and such ids take up too much memory to comfortably send them in our game’s networking protocol.

We will make the simplification that only one of our machines – the server – will generate ids. In that case, we can simply use an integer counter that we increase for every generated id.

Let us write a simple IdManager class to handle this for us:

class IdManager
{
    private int lastId = 0;
    public int GetNext()
    {
        this.lastId++;
        return this.lastId;
    }
}

This looks extremely simple. And it is.

We could now use these ids for all our purposes above, and it would work just fine. However there is one thing I am not happy about: Using plain integers as ids.

Type-safe identifiers

What is the problem with integers?

The problem is that an integer value could mean anything. Only our usage of it makes it into an identifier. Worse, whenever a method asks us for an identifier, we could simply give it an arbitrary integer:

DoSomething(0);

This code might look perfectly fine, and we may only discover the problem at runtime.

Instead, I would prefer for our identifiers to be type-safe, meaning that we cannot simply use integers as ids. If we really want to give a method a fake or arbitrary identifier, it should say so in code:

DoSomething(new Id(0));

This makes it much clearer what is going on, and while this will still compile fine, at least it is clear that we are creating our own identifier, and that this may be a problem.

Let us create this Id type:

struct Id
{
    private readonly int value;
    public Id(int value)
    {
        this.value = value;
    }
}

As you can see, this is really just a wrapper around our original integer. Note that because of that, we are using a structure. We could use a class, and within our application compare identifiers by reference. However we would then run into the problem of how to get the correct identifier object for an integer value from a network message.

Simply creating a new identifier object at that point solves this problem, however it also creates unneeded pressure on our garbage collector.

Since our type is very small, containing only one item of information, and since we do not care to access it by reference (it has neither behaviour nor a changeable state), using structure is the better option.

This aside shows something else we are missing though: We now cannot actually compare our identifiers for equality. At least now using the equality and inequality operators == and !=. We can use the Equals() method, which for structures defaults to a bitwise comparison, which is indeed what we want. However, it would be much nicer for our code if we could use the operators as well.

Luckily, they are easily implemented:

public bool Equals(Id other)
{
    return this.value.Equals(other.value);
}
public static bool operator ==(Id id0, Id id1)
{
    return id0.Equals(id1);
}
public static bool operator !=(Id id0, Id id1)
{
    return !(id0 == id1);
}

Note that I also implemented the method Equals(Id), which means that our Id structure now inherits from the IEquatable<Id> interface, which is a nice property to have, and makes perfect sense for the semantics of the type: An identifier can always be compared to another for equality.

Fast access to objects with identifiers

Now that we can give identifiers to our objects, we have to think about accessing those objects in a fast way. The easy answer to this is keeping a dictionary, or hashmap, with the identifier as key, and the object as value.

Here is a quick implementation of basic game state and game object classes:

class GameState
{
    private readonly IdManager idManager = new IdManager();
    private readonly Dictionary<Id, GameObject> gameObjects =
        new Dictionary<Id, GameObject>();
    public Id GetNewId()
    {
        return this.idManager.GetNext();
    }
    public void Add(GameObject obj)
    {
        this.gameObjects.Add(obj.Id, obj);
    }
}
class GameObject
{
    private readonly GameState game;
    private readonly Id id;
    public Id Id { get { return this.id; } }
    public GameObject(GameState game, Id id)
    {
        this.game = game;
        this.id = id;
        game.Add(this);
    }
}

Now, given an id, we can simply look up the associated game object in our dictionary, virtually guaranteeing us constant time access.

In fact, we can do even better by making sure that our identifiers hash code – which is used by the dictionary – behaves nicely. We can do that by simply returning the hash code of the underlying integer, under the assumption that this is implemented well (and it is).

public override int GetHashCode()
{
    return this.value.GetHashCode();
}

Deleting objects

When our game objects are deleted, we will want to make sure to remove them from our dictionary as well. Otherwise we have created a memory leak, will eventually run out of memory, and are in the meantime bogging down our garbage collector – not allowing it to clean up things we no longer need.

We will go with a reasonably simple solution here:

Each of our game objects will get an event Deleting which will be called when the object is deleted. When adding objects to our dictionary, we will subscribe to that event. This allows us to easily remove them from the dictionary when they are deleted.

See this new version of the two classes above:

class GameState
{
    private readonly IdManager idManager = new IdManager();
    private readonly Dictionary<Id, GameObject> gameObjects =
        new Dictionary<Id, GameObject>();
    public Id GetNewId()
    {
        return this.idManager.GetNext();
    }
    public void Add(GameObject obj)
    {
        this.gameObjects.Add(obj.Id, obj);
        obj.Deleting += () => this.gameObjects.Remove(obj.Id)
    }
}
delegate void VoidEventHandler();
class GameObject
{
    public event VoidEventHandler Deleting;
    private readonly GameState game;
    private readonly Id id;
    public Id Id { get { return this.id; } }
    public bool Deleted { get; private set; }
    public GameObject(GameState game, Id id)
    {
        this.game = game;
        this.id = id;
        game.Add(this);
    }
    public void Delete()
    {
        if(this.Deleted)
            return;
        if (this.Deleting != null)
            this.Deleting();
        this.Deleted = true;
    }
}

We now only have to call Delete() on our objects for them to be deleted from our dictionary through the event.

Conclusion

And with that, we have fulfilled our requirements above. Our game objects now have unique identifiers, and can be quickly retrieved knowing only the identifier.

Further, our data structure cleans up after itself when objects are deleted, preventing memory leaks and bad garbage collection behaviour.

I hope you have found this interesting. Let me know what you think of my solution, especially if you have solved the same problem in different ways.

Enjoy the pixels!