Sign in to follow this  
leiavoia

References to other objects: Pointers or ID's?

Recommended Posts

Game objects need to know about other game objects or lists of game objects. I tend to store those as pointers (C++) for ease of use. HOWEVER, i've been doing a lot more webdev and database work professionally than i do gamedev work at home. In a database-heavy environment (like a web app), you tend to store everything as an ID number or some other lookup identifyer. The nice thing about ID's is that you don't have to worry about memory issues or about directly possesing a reference to the object. You just need a way to find it (an ID number). Does this ID-lookup approach work well for games? In particular, I'm thinking about a networked TBS game. There would naturally be a lot of game objects to pass around and different machines need a way to address these objects in a way that doesn't involve memory addresses. Does anybody else tend to use this approach? Anything positive or negative to say about it? Thanks for your input. Much appreciated!

Share this post


Link to post
Share on other sites
The only time ive ever used an ID approach is with OpenGL when binding a texture. Or some awful hack to get the player you know is stored at X position in a vector. I prefer storing pointers and references but i can't really see a downside to your method.

Share this post


Link to post
Share on other sites
Quote:
Original post by leiavoia
HOWEVER, i've been doing a lot more webdev and database work professionally than i do gamedev work at home. In a database-heavy environment (like a web app), you tend to store everything as an ID number or some other lookup identifyer.

Yes. In order that SQL work with a wide range of technologies, it's important that entities be referred to by integers, rather than by more low-level identifiers.
Quote:
The nice thing about ID's is that you don't have to worry about memory issues or about directly possesing a reference to the object.
IDs work better than pointers at identifying objects that may move in memory or may not always be present in memory. This situation is almost assured when you're pulling data off a disk-backed database. It is less usual in C++, though by no means rare.
Quote:
Does this ID-lookup approach work well for games?

On some occasions it is useful to have a handle class which allows the referencing of objects. This allows you to track visibility of objects, as well as to abstract away the process of locating (and possibly loading) them. shared_ptr is an example of this, as is HMODULE. Using integers for this purpose tends to confuse things, though it is quite common.

Share this post


Link to post
Share on other sites
An alternative approach would be to use boost::shared_ptr and boost::weak_ptr (or other smart pointers); keep the master copy as a boost::shared_ptr, and pass copies of it as boost::weak_ptrs. As soon as the shared_ptr is destructed, the weak_ptrs will return a NULL pointer on an attempt to access the actual object (technically it returns an empty boost::shared_ptr, but it's basically the same thing). However, compared to the ID-lookup approach, serializing those pointers to disk may prove to be a challenge.

Share this post


Link to post
Share on other sites
use both perhaps?
I always use IDs (for the reasons u mentioned) but if the ID is accessed very often I also store a pointer as well as the ID.

Share this post


Link to post
Share on other sites
Sure, there are valid reasons why you might want to use integer identifiers rather direct pointers, design 'cleanness' just isn't one of them.

The ability to move objects in memory is one, serialization is another, and handling references to dead objects a third. However I would suggest that you only use indirect identifiers locally where such features are needed, not as a global abstraction layer for a core game component. Because the costs *will* add up.
Consider the cost of not being able to follow object pointers in the debugger, of having to pass around or reference a global object table whenever dereferencing an actor, of actually doing that (hash) table lookup to dereference an object, and so on. Seemingly insignificant things, like being able to eyeball pointers in a crash dump, can make a big difference when talking about a design choice that would affect half your code base.

Share this post


Link to post
Share on other sites
ID"s every time.

- you can defrag your resource memory, and not worry about who's still holding what address
- you can, at runtime, change what data resides at what ID, allowing things such as re-skinning game elements to be seamless.
- it makes it easier to serialise
- it makes it easier to deal with multiprocessing, as you can generate multiple copies of resource data on a per thread basis.

yes, there is some performance penalty for looking up ID's, but on the whole, its makes for a much more flexable solution.
another alternative is to use a weak pointer, which has the same advantages but less lookup overhead. (and you can store both the ID, and the pointer, in the weak pointer object).

Share this post


Link to post
Share on other sites
Quote:
Original post by Matt_D
ID"s every time.

- you can defrag your resource memory, and not worry about who's still holding what address
- you can, at runtime, change what data resides at what ID, allowing things such as re-skinning game elements to be seamless.
- it makes it easier to serialise
- it makes it easier to deal with multiprocessing, as you can generate multiple copies of resource data on a per thread basis.

yes, there is some performance penalty for looking up ID's, but on the whole, its makes for a much more flexable solution.
another alternative is to use a weak pointer, which has the same advantages but less lookup overhead. (and you can store both the ID, and the pointer, in the weak pointer object).


You can also use IDs that specify the object's position in an object list, so there is no performance hit. Player ID 3 is the Player object at playerList[3]. You have to pre-allocate space for the max number of each type of game object though.

Share this post


Link to post
Share on other sites
Quote:
Original post by EJH
You can also use IDs that specify the object's position in an object list, so there is no performance hit. Player ID 3 is the Player object at playerList[3]. You have to pre-allocate space for the max number of each type of game object though.


i think its worth noting that IMHO ID's should never be treat as indexes. ever. :)
use a lookup, and/or a hashing function, otherwise youll get into trouble :)

Share this post


Link to post
Share on other sites
IDs are nearly necessary in lock free multithreading as stated. They are also useful when you want to store entities in a variety of data structures. For example you may want entities organized in one fashion for quick render culling, and then in a different data structure for quick collision culling. These two data structures must have an ID system for them to communicate.

Share this post


Link to post
Share on other sites
I use 'em all. Different levels of encapsulation for different situations. At high levels of abstraction, pointers to opaque types, or hash keys. Lower levels, pointers to interfaces or abstract base classes.

As soon as you're going across a memory or network boundary, that's about as high level of an abstraction as you can get.

Share this post


Link to post
Share on other sites
As has been mentioned above, I typically use actual pointers for game level objects. However, for resources I almost exclusively use handles. For example, render targets, textures, buffers, fonts, etc... get handles. This allows for easy identification of the resource type (by storing an object ID in several of the bits of the handle), and you can reuse array locations for the O(1) lookup by adding a 'usage' count in several other bits of the handle.

So like everyone else said, it depends [grin]!

Share this post


Link to post
Share on other sites
Quote:
Original post by Matt_D
Quote:
Original post by EJH
You can also use IDs that specify the object's position in an object list, so there is no performance hit. Player ID 3 is the Player object at playerList[3]. You have to pre-allocate space for the max number of each type of game object though.


i think its worth noting that IMHO ID's should never be treat as indexes. ever. :)
use a lookup, and/or a hashing function, otherwise youll get into trouble :)


Pointers are essentially index IDs themselves though, right?. They are offsets from memory locations. cout a pointer gives you a number.

"Player ID 3" == playerList[3] is equivalent to ptrPlayer = &player[3]. Player ID is more human readable though and is valid across networked applications.

Clearly though, both are useful, or better, in different situations.

Share this post


Link to post
Share on other sites
Quote:
Original post by EJH
Pointers are essentially index IDs themselves though, right?. They are offsets from memory locations. cout a pointer gives you a number.

"Player ID 3" == playerList[3] is equivalent to ptrPlayer = &player[3]. Player ID is more human readable though and is valid across networked applications.

Clearly though, both are useful, or better, in different situations.


im not quite sure what your point is.

pointers are direct locations in memory (or pointers to another pointer, which will hopefully at some point, point to the address of some sort of data ). looking at them as offsets is, IMHO slightly incorrect. they are offsets from 0x000000, sure, but what exactly does that mean?

consider a resource system, which has memory pools, which hold objects. and that resource system is able to defragment the memory pools as, and when it sees fit. holding a pointer to an object in one of those pools would obviously be a bad idea(tm).

The main reason i dislike using indexes, as direct array indexes is that it makes maintenance a headache, especially when people start making assumptions about data. for example, writing code which assumes the indexes are sequential, without gaps (eg: iterating an array based on incrementing indexes), which may not hold true if an ID is removed.

Using hashing function generated ID's is always a better option (and you can always store the string along with the hash in debug if you really need to).

as long as you have a good hashing function :D


Share this post


Link to post
Share on other sites
Pointers are a very specialized form of IDs.

The ID concept has been in use for a very long time under a more general name of Handle.

A handle is some opaque key that has meaning in some known context. A database key is valid within a given table of a given database. A (typical C++) pointer is a key within memory space of a process.

Pointers are convenient because they are managed by compiler and run-time. This also imposes certain constraints.
- Pointers are randomized handles, which means they cannot be guessed. You can assume that foo will be allocated at 0xaabb1234, and it may often be, but it's up to too many factors for this to be viable
- Since pointer allocations are handled by third-party, and subject to memory addressing rules, they cannot be relocated without changing their "key".
- Pointers cannot be reliably shared between memory spaces. SHM is one way, remote synchronization another, but due to previous two issues, these methods are not reliable. If one process crashes, all such pointers are invalidated with no means of verifying them


Custom handle implementations can solve all of these problems and introduce a few more:
- Handles can decouple key from location (DNS, URL, Database keys, smart pointers, managed language references)
- They can be used to express relations in a persistent and reliable manner (linked list implemented using cursors can be memory dumped to disk and restored without side-effects)
- Handles are needed to work beyond shared memory systems. They might be needed in concurrent (multi-threaded or distributed) systems to avoid allocation issues (for example, message is passed to an object which has in mean-time ceased to exist)

- "Guessing" is a common and well-known problem. Since handle allocation schemes are often trivial, and since it's customary to provide "well-known" handles, they get hard-coded.
- While handle should be opaque and typeless, languages most often do not provide such features, so they end up as ints. This carries mis-leading information, which can and will be abused.
- Handles (contrary to pointers) are double-sized. One parameter is handle, the other context. Context may be implicit (static/global state, true for pointers), or explicitly handled. This is an issue when handles point to small objects.
- Resolving a handle (contrary to pointers) may have non-trivial cost in addition to memory access cost (which exists with pointers as well)

But as said, pointers are just a special case of handles with certain implied behavior that exist within context of process' memory space.

Share this post


Link to post
Share on other sites
having an identifier for the object can be very useful in situations where you dont actually have the object on your client. Like in a multiplayer environment where character with id 1234 fired a rocket at you, but the object does not exist on your client.

I would advise passing the object around as long as you have it, and only (if possible) lookup the object from the map/hash at the top calling function.

Or else you'll get lots of functions like:

void DoStuff(uint32 objectID)
{
Object *theObject = Object::Get(objectID); // lookup in map/hash/whatever
if (!theObject) return;
// real code here
}



But if you already have the object when calling DoStuff you should use that as parameter

Share this post


Link to post
Share on other sites
Quote:
Original post by _Kami_
having an identifier for the object can be very useful in situations where you dont actually have the object on your client. Like in a multiplayer environment where character with id 1234 fired a rocket at you, but the object does not exist on your client.

I would advise passing the object around as long as you have it, and only (if possible) lookup the object from the map/hash at the top calling function.


i wouldnt :)

lets take the multithreaded example, at best case you want a thread safe way of accessing the data (ie, not a pointer), at worst case, you may want to take a const copy of the data and either have pointers, or indexes, to that.

Also means you cant use ref counted resources ( unless your using something like intrusive_ptr, which generates a weak pointer to something. ) i use inrusive_ptr's for ref counting in my engine, (the object requests a resource by name when required (usually on load, as i know my memory wont be modified at runtime)).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this