Sign in to follow this  

Fast GUID generator

This topic is 1360 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on getting a better object ID system setup in my engine. I've got a basic counter that just keeps generating an ID one greater than the last one already, but what I need is some way of making sure that IDs are usable after being loaded from a file. I have a scene loader, and a prefab loader/object instantiater that both need to be able to generate globally unique IDs for all objects in their local hierarchies, but also retain their local links within the hierarchy. The reason for this is that my animation/cutscene system is going to have keyframes stored by ID. If anyone has experience with a system that works for this I'd be really happy if they could provide some advice.

Thanks.

Share this post


Link to post
Share on other sites

Unless you need IDs that are unique even across computers generating them at the same time, why not just use the incrementing ID, but save the last used ID to file? A 32 bit integer is 4 billion IDs.

 

GUIDs are typically 128 bits. That are designed so that, if I'm generating a GUID on my computer for whatever I use GUIDs for, and you're generating GUIDs for an unrelated purpose a thousand miles away from me on your computer, our two IDs are still guaranteed* to be unique from each other. But that's probably overkill for what you are actually needing. You just need it unique within that same program - not unique across the entire world.

 

*Within a ridiculously small margin of error.

Share this post


Link to post
Share on other sites

If you're worried about "wasting" IDs, you could keep an uint counter and a stack. Every time you destroy/unload a game object, you grab its ID and push it on a stack, so when the next game object is created, it queries first if there is an available ID on the stack, if there is, it just pops it and uses that one, if there isn't, increment the counter and use that instead.

 

When saving to a file then I'm not so sure. Since I doubt you'll save every single thing that has an ID, you might have gaps in between the game IDs you store and those you don't. You could "flatten" the IDs of all serialized game objects, so when you load them up, there is a max ID number and no gaps between that max ID and zero. That way you can just assign the max ID to the counter and for new game objects you start to count from there.

 

But I can see its kinda annoying since you'd have to update the ID and all the places were is being referred from...

Share this post


Link to post
Share on other sites
Generating a v4 UUID (just random numbers) is very quick, and with a good RNG is still globally unique for all practical purposes. A 128-bit RNG like SFMT can generate swaths of UUID source data quite cheaply. After generating the bits you just set a few of them to specific values to make the UUID RFC-compliant if you care about such things.

The problem with 32-bit IDs in some cases (they work wonderfully in others) is that sometimes you don't have a single authority generating the numbers. If you need to generate a unique ID in two separate tools without any cooperation then UUIDs are a fantastic option that have incredibly low likelihood of collision and aren't as prone to human error as string names.

For things like in-game unique IDs that are generated by the engine and consumed only by that single game instance, a 32-bit (or smaller!) ID is just fine. Smaller IDs are actually preferable in some cases since you can use them as indices into arrays or at least have them be keys to sorted maps or hash tables.

You can even generate perfect hashes for static sets of data like entries in a packed resource file (by altering your hash seed and hashing all items until you get no collisions, then saving both the chosen seed and all the hash results; usually only takes a few iterations unless you're using a bad hashing algorithm, an especially small hash size, or an especially large number of values).

For save games, it can still be valuable to use something like UUIDs. Sometimes you need to be able to generate unique IDs without loading up an entire save game file to check for duplicates or determine a best "next" value (say, for large open world games where only a portion of the world state is loaded into memory at any given time). There are many solutions; UUIDs are one of them and an easy one at that.

If you need smaller values, a 64-bit random UID may still give you no collisions in practice; I've never seen or done the analysis. I've yet to see any actual performance problems with UUIDs when used correctly and with discretion, though, even when used for every resource and every game object and every component.

Share this post


Link to post
Share on other sites


If you need smaller values, a 64-bit random UID may still give you no collisions in practice; I've never seen or done the analysis. I've yet to see any actual performance problems with UUIDs when used correctly and with discretion, though, even when used for every resource and every game object and every component.

 

A 32-bit UUID selected at random will encounter one collision after on average a few dozen thousand UUID's. A 64-bit UUID will encounter one after a few billion UUID's, so you're probably safe. (see birthday paradox).

Share this post


Link to post
Share on other sites

I always considered GUIDs to be pretty overkill for runtime purposes in a gaming environments.

I find myself much more comfortable with [pool, slot] pairs which give up some control and require some more attention but are much, much easier to debug in my opinion, as well as intrinsically better defined.

In particular, generating GUIDs for objects in a hierarchy as OP wants to do is overkill by several orders of magnitude. I have a similar need and I just identify objects by their sequential creation index. I cannot see any problem in the foreseeable future so I would encourage in elaborating the specific needs.

Share this post


Link to post
Share on other sites

Thanks for the advice. I'm thinking so far that I'll probably avoid GUIDs. I thought that was how most engines did things, but if it's overkill for realtime I'm not gonna bother. What the IDs will be used most for is querying game objects by their ID. If an prefab file is loaded with internal ID links then I want to retain those links while also being able to reference objects globally. I also want to have the ability to use the IDs to refer to objects across the network. Would it be a good idea to just have the ID generator reserve IDs in blocks and then "patch" local hierarchies of object IDs at load time? So lets say I load a prefab with local IDs starting from one that are only unique local to the prefab. Then I take the root object of that prefab and generate the next global ID for it, and then just increment the local IDs further down the prefab's hierarchy so that they retain their offset from the prefab root. Are there any inherent problems with a method like that?

Share this post


Link to post
Share on other sites

Did you thought about hash of objects name? In all games I work on, we are using names hash for distinguish objects.

Names can be automatic eg. prefab name "sword", objects names: "sword 1", "sword 2" itd.

Share this post


Link to post
Share on other sites

I thought about that, but object names aren't guaranteed to be unique. It's possible for two guns that have children named "foregrip" or "clip" for example. I ended up settling on patching local IDs based on an offset from the root of the hierarchy. That way my local ID links are still meaningful as long as I know the ID of the hierarchy's root.

Share this post


Link to post
Share on other sites

I thought about that, but object names aren't guaranteed to be unique. It's possible for two guns that have children named "foregrip" or "clip" for example. I ended up settling on patching local IDs based on an offset from the root of the hierarchy. That way my local ID links are still meaningful as long as I know the ID of the hierarchy's root.

 

You can hash the whole hierarchy string eg.

prefab: "starship/wing/leftgun"

object: "starship 1/wing/leftgun", "starship 2/wing/leftgun", "starship 3/wing/leftgun"

Share this post


Link to post
Share on other sites

Oh... That's a good idea. It's so simple too... It's actually quite brilliant, I'll have to try that.

Share this post


Link to post
Share on other sites

This topic is 1360 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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