[Tutorial] Waiting for GUID(ot)

[EmilyStrange]

A brief overview of GUIDs for those that are only just discovering them.

What is a GUID? It is a Globally Unique IDentifier that is guaranteed to be unique for its usage. If you run Microsoft Windows, Linux or Mac OS X, you may have encountered GUIDs before when looking through the registry, installing device drivers, or accessing web services. GUIDs in an oprating system are used to identify device drivers, applications, users, physical hardware devices such as motherboards and graphics cards, even the keyboard you are typing on.

On Microsoft Windows GUIDs are 16 bytes long, and are based on hardware characteristics of the computer that is used to generate the GUID, e.g. your computer, the network address, time of day, and a random number. The chance of a collision, i.e. you and I generating two GUIDs that are identical, is miniscule. Really miniscule. Listen, you might think the odds of you ever getting laid are exceptionally small but that’s nothing compared to... And son on.

In the World of Warcraft game, GUIDs are 8 bytes long, and because they only need to be unique within the context of the game, 8 bytes is more than enough. What algorithm is employed to generate the GUIDs is unknown, but it is most likely a similar technique to how the game server operating system does it, or it may even use the host operating system GUID generation system.

How are GUIDs used within World of Warcraft? Every object you interact with, from the totem that a shaman drops on the ground, to the monster you just killed, to your player character, to the chair your player character can sit on, and yes, even that vein of ore you just mined, all of them have a unique GUID.

GUIDs are unique, never re-used (as far as anyone knows) and identify every object within the game world. When you kill a mob and the corpse finally disappears, the GUID associated with it is thrown away, never to be used again. A short while later, when the monster in the area re-spawns, it might look like the same monster, but it is actually a completely new monster, with a completely new GUID.

GUIDs are unique to a game server, and may even be unique across all game servers, or all game servers within a geographical region. However, GUIDs are not unique to a particular game client. If you run two game clients on the same game server, e.g. Darkiron, and both player characters on two different computers target the same monster, both game clients will report the same GUID for the same monster. This is actually quite useful if you are writing a party bot or multiboxing aid.

Are GUIDs persistent? Some GUIDs are, some GUIDs are not. GUIDs not only uniquely identify all game objects within the game world but many of them also persist across server restarts because they are stored in the SQL database. Much of the game world, i.e. anything that is transitory such as monsters and NPCs,,i.e. a “Unit”, ore veins, and non-bound world items, i.e. stuff you aren’t carrying, does not appear to be persistent in that it is not serialized back to the database (ever had a dungeon instance crash while you are in it? Many parts of course, actually are, your player character, items in your inventory, your backpacks, your bank, your guild vault, a daily dungeon or time-locked RAID dungeon and many other things too.

As far as I can ascertain, the items you carry on your character are uniquely your items, each with its own GUID. It may look like you have the exact same sword as another player, but both swords have a unique identifier that marks it as two separate instances of the same game object.

Side Note: As a side-note, I do not know if general world objects are persisted in the SQL database or regenerated every time the game server is restarted. This could be verified by dumping out all of the GUIDs of objects that are not players that are around your player character just before a game server restart, and then doing the same thing again once the game server is back up and comparing the two lists. This exercise is purely an academic pursuit as it would have no bearing on developing an effective bot nor give you any in-game advantage.

Hunting the GUID. If you know the GUID of an object, you can search the World of Warcraft, game client, memory space for those 8-bytes. If you grab the GUID of your player character and store it somewhere safe, when a new patch is released, it is trivial to find the player’s local GUID again, just plug in your known GUID to a memory search routine and hunt it down.

Multiboxing GUIDs: Multibox? You can log in a character on two separate accounts, scan the memory space of one game client for the GUIDs of both characters, from that you receive the LocalPlayer GUID, and consequently, the local player game object structure, and you receive an entry in to the object manager linked list.

Inferring Object Linked List Structure by Triangulating on Three GUIDs. Obviously, if you have three or more accounts you can scan one game client memory space for as many player character GUIDs as you have available to log in simultaneously. Searching for the multiple GUIDs and calculating the distance between the GUIDs in bytes will give you the offsets necessary to calculate how far apart in memory each game object is. You can use the same technique for determining the memory address of the player name cache.

Personal Anecdote. When I first started developing an out-of-process memory-reading application for World of Warcraft this was the first technique I used until I found enough information through the work of Apoc and other developers on this forum to actually figure out how the memory structures of World of Warcraft were laid out.

These short GUIDs are sufficient to uniquely identify every instance of every object in the game world and each time a new game object is created, a new GUID is created to go along with it. When you mine an ore vein, the GUID representing that vein is “used up” and when the vein spawns again in the exact same spot, that new vein will have a new GUID to go along with it, even though it looks like the exact same ore vein.

[Apoc]

GUIDs are completely unique. There will never be 2 of the same GUIDs on any one server. (The same GUID can appear on two different servers however)

Think of it as the GUID being the 'id' and primary key field in an SQL DB. It's guaranteed to be unique, and static.

[EmilyStrange]

re: "GUIDs are completely unique"
Theoretically, yes, but there is still a probability, however small, that a collision could occur within a 64-bit search space. The birthday paradox applies even here, it is just lessened.

re: "never"
"Never" is a very long time. Even the Microsoft UUID/GUID generation algorithm (now RFC 4122) is only guaranteed until 3400 A.D. Which by my reckoning means we will be running Microsoft Windows v354 assuming an operating system release every three years or so when we encounter a higher probability of collisions.

re: "Same GUID on two servers"
Possibly. It depends on the algorithm, which I suspect is MD5 or SHA-1 (most likely the former given the GUID address space of 64-bits), to generate the GUID. My suspicion is that Blizzard are using a RFC-esque UUID algorithm which would ensure that certain bits of the GUID are never replicated given two identically configured pieces of hardware used to generate the GUID. This would ensure that their account database server, character database server, and transactional replication servers do not need to worry about address space collisions when logging or combining or dividing server populations. It would also simplify a lot of their database architectural considerations. It is the logical solution to the problem, but Blizzard may have chosen something different just to be contrary. Game developers are renowned for NIH syndrome.

re: "GUID being the primary key in the DB"
It almost assuredly is in many data tables. Not utilising this benefit would require a thunking layer and table lookup (or database access) to translate from primary key ID (most likely an int) to the 8-byte GUID. No sense in it.

Also, a GUID stuck in to a Map/Dictionary/Hash in the game server memory would ensure reasonably even distribution to the various buckets conferring the benefit of a very fast look up algorithm.

-- Emily (who wrote a very long analysis on this subject as part of her dissertation)

[Tanaris4]

Great post, I was always curious about this when I started in this scene

[bballer12]

You can get such information from the UDB wiki which is a DataBase for private Servers. Here you can learn how things are treated in wow.
UDB_Wiki
(it is not 100% like the real blizzard db is structured)

[Apoc]

re: "GUIDs are completely unique"
Theoretically, yes, but there is still a probability, however small, that a collision could occur within a 64-bit search space. The birthday paradox applies even here, it is just lessened.

re: "never"
"Never" is a very long time. Even the Microsoft UUID/GUID generation algorithm (now RFC 4122) is only guaranteed until 3400 A.D. Which by my reckoning means we will be running Microsoft Windows v354 assuming an operating system release every three years or so when we encounter a higher probability of collisions.

re: "Same GUID on two servers"
Possibly. It depends on the algorithm, which I suspect is MD5 or SHA-1 (most likely the former given the GUID address space of 64-bits), to generate the GUID. My suspicion is that Blizzard are using a RFC-esque UUID algorithm which would ensure that certain bits of the GUID are never replicated given two identically configured pieces of hardware used to generate the GUID. This would ensure that their account database server, character database server, and transactional replication servers do not need to worry about address space collisions when logging or combining or dividing server populations. It would also simplify a lot of their database architectural considerations. It is the logical solution to the problem, but Blizzard may have chosen something different just to be contrary. Game developers are renowned for NIH syndrome.

re: "GUID being the primary key in the DB"
It almost assuredly is in many data tables. Not utilising this benefit would require a thunking layer and table lookup (or database access) to translate from primary key ID (most likely an int) to the 8-byte GUID. No sense in it.

Also, a GUID stuck in to a Map/Dictionary/Hash in the game server memory would ensure reasonably even distribution to the various buckets conferring the benefit of a very fast look up algorithm.

-- Emily (who wrote a very long analysis on this subject as part of her dissertation)

To quote from WoWWiki (which is actually 100% correct)

GUIDs are represented in WoW as hexadecimal strings beginning with '0x' -- this prefix is not part of the data, but merely signifies that what follows is a hexadecimal number. GUIDs are intended to provide a unique way to identify units; the following general rules apply: [1]

• A monster has a single GUID from spawn until death (or despawn). When it respawns it gets a new GUID.
• Pets get a new GUID each time they are summoned.
• Monster and pet GUIDs can be recycled after server (or instance) restart.
• Players keep their GUID forever, and are unique even in cross-server battlegrounds.
• However, units that "transform" into other units may not switch GUID immediately.

A GUID can be thought of as being composed of multiple pieces of data. Consider "0xAABCCCDDDDEEEEEE", where:

AA unknown.
B unit type, mask with 0x7 to get: 0 for players, 1 for world objects, 3 for NPCs, 4 for pets, 5 for vehicles.
CCC If the unit is a pet, CCCDDDD forms a unique ID for the pet based on creation order; if a world object, CCCDDDD is the object ID; otherwise unknown.
DDDD If the unit is an NPC, this is the hexadecimal representation of the NPC id.
EEEEEEE If the unit is a player, this is a unique identifier based on creation order. Otherwise, this is a spawn counter based on spawn order.

So yea; each GUID are completely unique so long as the server/instance isn't restarted. There is no RC4 or any other sort of cryptography involved.

If you wrote your analysis (and dissertation) without even doing some research... I feel sad for your level of competence in your field of study.

[EmilyStrange]

As a point, I never mentioned RC4 or any kind of cryptography. MD5 or SHA-1 is used in more places that pure cryptographic systems and is a useful algorithm for generating distinct keys from a known data set.

WoWWiki is very incomplete and I was not attempting to copy & paste information that is readily available in other areas. I see a lot of confusion on these forums over GUIDs and what they are and attempted to present this information in a clear and concise manner.

How very judgemental of you to make such an assertion about my competence with knowing nothing about me or my dissertation. Seeing as how it passed the peer review committee with the highest accolades and honours they could give I value your opinion of it, sight unseen, about as much as I value the pile of dog shit I stepped over this morning on the way to the office.

What part of my analysis was wrong?

What parts of my original post contradicted anything in WoWWiki?

My only oversight that I can see was stating that "GUIDs are thrown away, never to be used again" which I should perhaps have clarified with "never to be used again until the server restarts, dependent on the base object type, at which point they may be used if the sequence generator seed, which is held in game server memory, for that particularly object type, and not backed by the database, or is backed by the database but is also reset, which rarely occurs."

A simple linear sequence generator for NPCs/Players/Monsters would generate too many collisions in any dictionaries or hash maps so a keying function, such as MD5 or SHA-1, is the optimum solution. I know this to be a fact because I have written these algorithms for other games and many of those games I worked on with the programmers who eventually went on to work on Everquest, Star Wars Galaxies, World of Warcraft, Warhammer, and so on.

You seem to argue for arguments sake most days and seem intent on turning this thread into a flame fest for your own ego. You are a very fine contributor to these boards (with moderator powers I may add) but rather than biting your tongue you seem to want to turn every thread in to a personal fight and overcompensate for other areas of your life (now who is being judgemental about someone I know nothing about?)

So be it. I will go back to lurking. If your aim is to drive away anyone who wants to contribute to the forums, you've done a stellar job, and I leave you with the endless and tireless questions from the uneducated and unwilling.

-- Emily (ex-Activision/ex-VU (when they still owned Blizzard)/ex-LucasArts/ex-SONY programmer on projects you think you know so much about who didn't write the object ID generator on Warcraft because she was too busy coding up other areas of the game.)

In essence you are reverse engineering the games I helped write, so yeah, I think my level of competence in my field of study is up to scratch, even if you do not.

[Apoc]

In the World of Warcraft game, GUIDs are 8 bytes long, and because they only need to be unique within the context of the game, 8 bytes is more than enough. What algorithm is employed to generate the GUIDs is unknown, but it is most likely a similar technique to how the game server operating system does it, or it may even use the host operating system GUID generation system.

Failed research. (As proven, and yes, Blizzard HAS confirmed their GUID layout (Except for the 2 first digits in the hex representation [the only one that matters to Lua programmers]) I'll find you a link in a bit (once my net stops being retarded...)

I take back my note about RC4 (I was cross reading 2 threads at the time; one mentioning RC4 encryption, my bad!). However, no form of encryption is used at all. (And yes, SHA-1/MD5 fall in that category)

The reason I 'argue' with you (which I'm not) is because people post false information on these boards constantly. And bad info leads to many many more mistakes that could have been avoided had the poster (you) done even 10 minutes of research on the subject. I'm not questioning your ability to code (nor do I care where/what you have done). I don't want bad information put on this board. Period.

We *never* intend to drive away people who know what they're talking about. However; those that can't do the PROPER research on a subject they're writing about (especially an 'informational' post such as yours) should not be posting in the first place.

Oh right; had you searched, you would have found a thread detailing the GUIDs and how to quickly determine certain characteristics of each object in memory. But again, you failed to do your research before commenting on an enclosed system.

Lastly; my comment about your dissertation still stands. If you're paper passed peer review, I certainly feel sorry for whoever those peers were.

P.S; Me being a mod has nothing to do with anything. I don't abuse my powers, nor do I 'push' people around. I'm always up for an intelligent conversation or debate. (It's not often we get that in this section, sadly) My job here is to keep this site clean, nothing more. I'm not here to quell free speech. (I'm very.... very lenient in this section about what is discussed, and how.)

[amadmonk]

BTW, collisions aside, it would be fairly silly for the 'GU' to be part of 'GUID' if they weren't (by design) "globally unique."

Collisions can occur with the best-designed GUID algo (sometimes intentionally for fun things like MITM and decryption stuff), but IIRC the WoW GUID algo is reasonably pat.

[jt12852]

This is meant only as constructive criticism of the original post, in its aspiration to serve as a "tutorial".

While the title of your post is a clever pun, it is likely to be completely unintelligble to readers who are not native speakers of English (or possibly French), and misleading to those who are native speakers but not well versed in 20th century dramatic literature.

The first 9 paragraphs appear to presume your audience knows absolutely nothing about what a GUID might be. Those paragraphs vastly overcomplicate what should be a simple description of a n-bit integer with a uniqueness constraint.

Meanwhile, your last 5 paragraphs presume that your audience knows enough about scanning process memory space to do so without any explanation. You suggest that the audience scan for known GUIDs, yet you make absolutely no mention of how the GUIDs could be determined in the first place.

These two presumptions about your audience appear contradictory. I'm left wondering, "What lesson am I intended to learn from this tutuorial?"

[Cypher]

You weren't supposed to learn anything. It was a failed show-off attempt.

[[-gvd-]]

worked hehe