Assigning IDs to entities and obects for use in scripts and by other objects

Question

I'm currently planning a small, simple scripting system for my game engine that will allow me to easily define scenes (similar to the "cutscenes" found in 2D RPGs). It consists mainly of simple commands such as "Change scene", "Move to" and so on.

Some of these scripting commands require operands. For example, the "Move to" command should expect an entity ID and a target node ID (where the node is just another placeable object). The aim is that whenever you create an entity, map or other object in the editor, it is assigned an ID that other objects and scripts can use to refer to it easily. These IDs will be stored when the game loads its data and used during runtime to make sure I'm targeting the correct object when an interaction occurs.

The problem I'm having is in how best to assign IDs to these objects of interest. I thought about just automatically assigning an incremented integer ID to new objects, but was unsure of how I should deal with the possibility of stale references. As I work in the editor, I may add and then later remove an item that was assigned an ID when it was created. If I delete an item that previously had an ID, should that ID be released for use by something new, or should I just leave a gap? Also, how should I keep track of assigned IDs between uses of the editor so that I can easily avoid collisions and also check easily for stale references?

For example, if I was to (either accidentally or intentionally) delete door A that is linked to door B, what would be the simplest way to check for any stale references, so that door B can be known to refer to something that no longer exists? Is it literally just a case of iterating through every object and seeing if any IDs it refers to are there or not?

I have the same problem when trying to decide how best to refer to the game's central list of items, spells, etc. These are the things that can be considered a core part of the game, but may be modified or removed over time. How can the game deal with a situation like the deleting of an item that has already been put in numerous places (i.e containers) in the game world?

Thanks in advance for any enlightenment you can offer with the above.

Answer 1

What you are looking for is really similar to a type of smart pointer, called a weak pointer. A weak pointer lets you have a pointer to something, but if that something goes away, that pointer will then point at null automatically.

I mention that because you can search the net for different smart pointer implementations to find more info and techniques if you want them.

Your instincts are good about the method you are trying to use to solve your problem, I've seen the same sort of solution used in multiple AAA game engines!

A nice simple solution to this is something I've seen in object pools, and I think will also apply here.

Basically, an object pool is an array of objects (can be anything), where each object has a bool to specify whether or not it's in use. When someone wants a new object, it finds an unused object, marks it as used, and returns that to the caller. When someone frees an object, it marks that object as unused and is thus returned to the pool. Object pools are great for avoiding dynamic memory allocations. That isn't what you are trying to solve but I wanted to mention that in case it helps you in the future.

Anyhow, you can upgrade the idea of an object pool to solve your situation by adding a "use count" to each object.

Whenever an object is freed, you increment it's use count.

How this helps you is that when you allocate an object, you can identify that object uniquely by it's index in the object pool array, but you also have it's use count.

These two values together make up a "weak pointer", so you could have some struct with these two values in them and treat that as your object reference.

When you want to get the object itself, you pass the index and use count of the object count you want to the object pool, and it does the following logic:

1) If the index specified is unused (or out of bounds), return null 2) If the index specified is in use, but it has a different use count than was asked for, that means the person asking for an object is asking for a STALE REFERENCE, so return null 3) Else, return a pointer to the object

There are other ways to implement weak pointers that may or may not be better for your needs, but I think this is one of the ones that is most appropriate to your usage case.

The only thing you have to watch out for here is that you need to make sure that these object pools are the same on all machines involved.

Essentially, you have to make it so objects are only created or destroyed in a deterministic, synchronized way between clients.

Another option could be to have the server be the only one who can create or destroy objects.

Yet another option though could be to reserve "object id ranges" for individual clients. like player 1 is in charge of object id's 0 to 99, player 2 is in charge of object id's 100 to 199 etc.

There are cheating concerns here to watch out for, but I think this is starting to stray outside of the realm of your question so will leave it at this.

Hopefully you get what I mean, I think this ought to be real useful in your situation!

Answer 2

The approach I prefer treats handles as simple unique integers.

In order to access the data via a handle you must pass the handle to its appropriate manager. For instance, if you have an ObjectId, and you want to get the position of the object with that id, you call a function akin to GetPositionOf(ObjectId id) -> Vector3f.

Because you are always passing the handles to accessor functions for interesting work the staleness of the ID can be checked at each call site. Likewise, a helper function like IsValid(ObjectId id) -> bool can be used if you need to check explicitly.

For more complex uses, you can either return a struct directly (which is far cheaper than most people think) or you can return a pointer to an internal structure. The rule in the latter case is that you aren't allowed to hold on to the pointer for longer than a single frame, since the pointer might become invalidated at the end of the frame (because you only actually delete/deallocate game objects at the end of a frame).

Unlike a weak_ptr model, such a handle system has several advantages. One of them is that you can freely copy the handles around using memcpy, which is a huge advantage for hihgly-efficient threading, graphics, physics, etc. A second advantage is that you can more easily reuse the handle in different systems allowing you to use the same index into otherwise completely independent chunks of code.

An implementation of this approach is covered in this BitSquid article on their "packed_array" (which I've always seen called a "slot map" before the BitSquid article).