Jump to content

  • Log In with Google      Sign In   
  • Create Account

Fast GUID generator


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 3DModelerMan   Members   -  Reputation: 1003

Like
0Likes
Like

Posted 16 April 2014 - 07:15 PM

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.



Sponsor:

#2 Servant of the Lord   Crossbones+   -  Reputation: 19547

Like
4Likes
Like

Posted 16 April 2014 - 07:56 PM

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.


It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#3 TheChubu   Crossbones+   -  Reputation: 4352

Like
3Likes
Like

Posted 16 April 2014 - 08:39 PM

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


"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator


#4 SeanMiddleditch   Members   -  Reputation: 5822

Like
4Likes
Like

Posted 16 April 2014 - 09:14 PM

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.

#5 Bacterius   Crossbones+   -  Reputation: 8874

Like
3Likes
Like

Posted 16 April 2014 - 10:00 PM


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


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#6 Krohm   Crossbones+   -  Reputation: 3119

Like
4Likes
Like

Posted 17 April 2014 - 12:01 AM

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.



#7 3DModelerMan   Members   -  Reputation: 1003

Like
2Likes
Like

Posted 17 April 2014 - 08:47 AM

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?



#8 Ocelot   Members   -  Reputation: 336

Like
2Likes
Like

Posted 25 April 2014 - 04:29 PM

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.



#9 3DModelerMan   Members   -  Reputation: 1003

Like
0Likes
Like

Posted 26 April 2014 - 07:12 AM

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.



#10 Ocelot   Members   -  Reputation: 336

Like
1Likes
Like

Posted 27 April 2014 - 11:56 AM

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"



#11 3DModelerMan   Members   -  Reputation: 1003

Like
0Likes
Like

Posted 27 April 2014 - 01:37 PM

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






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS