2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ May I ask how you would go about looking up a related object in this way? For example, you have two linked objects, one with an ID of 50, another with an ID of 22. If all objects are inserted into an array at the next available index, how can I quickly determine the index of an item I only hold an ID reference to? When item ID 50 wants to interact with ID 22, it needs to find it, but how do you do this when the actual index it resides at isn't a fixed value? Iterating through the entire array until I find the correct ID seems bad considering how many items might be in the array. Thanks again! \$\endgroup\$ – Triforcer Jun 15 '15 at 12:36
  • \$\begingroup\$ The id is in fact the array index (: the use count is involved just to make sure the reference isn't stale. \$\endgroup\$ – Alan Wolfe Jun 15 '15 at 15:16
  • \$\begingroup\$ If you get stuck let me know and I can make some example code \$\endgroup\$ – Alan Wolfe Jun 15 '15 at 15:32
  • \$\begingroup\$ I have a habit of overcomplicating things :) would it then be valid for me to assign new items the first available ID when they're created in the editor, have that list of IDs saved along with use count, then later load items in the game in the same order to access them by that same ID? Would people in the industry employ a similar approach ? \$\endgroup\$ – Triforcer Jun 15 '15 at 18:14
  • \$\begingroup\$ Well it's hard to say without more knowledge about your specific usage cases, and details like whether or not you need your IDs to remain the same between game saves. When talking about saving and loading preplaced objects, people in the industry would lean towards having a contiguous array at map save time (no gaps) and doing a single file read to read the entire chunk of data into memory with little or no "fixup" after loading. Also, if these preplaced objects can never be destroyed, you may store them in a separate array that never gets resized, treating them differently than dynamic ones \$\endgroup\$ – Alan Wolfe Jun 15 '15 at 18:59
5
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for the helpful info and interesting article Sean. It didn't seem fair to accept one answer over another as they're both really useful. I ultimately chose Alan's as he was the first to provide a solution. \$\endgroup\$ – Triforcer Jun 14 '15 at 15:07
  • \$\begingroup\$ Our answers can actually be used in conjunction. If you use 16 bits for object index and 16 bits for use count, that could be used as a 32 bit opaque handle. What's nice about the things Sean is talking about is its impossible for someone to misuse you system and store off a pointer in a member variable which could then go stale. When its impossible to do the wrong thing, you've engineered a good solution (: \$\endgroup\$ – Alan Wolfe Jun 14 '15 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.