0
\$\begingroup\$

I am wondering how games generate IDs/GUIDs for their entities (along these lines), and which entities specifically get them. To narrow the scope of the question down, I am just focusing on FPS games such as Halo. This was an earlier question that helps explain how state is synced across clients in an FPS:

The state that is synced when a window is broken in a FPS game

The goal with that question was to learn what kinds of data is sent around to sync clients. The piece that is still missing for me is what entities in the game actually get an ID of some sort (either a GUID, or a scoped ID such as some incremented integer or something).

Some of the game "entities" I am considering are:

  • Particles of light, individual pixels, physical forces, etc. (the lowest level vectors/points for calculating light or physics stuff).
  • Topology (mountains, roads, etc.).
  • Landscape features (grass, bushes, trees, rocks, water, rain drops, etc.).
  • City features (cars, signs, buildings, windows, shards of glass from a broken window, etc.).
  • Tools / items (weapons, potions, etc.).
  • Other players.

It seems that some of these "entities" you can interact with (e.g. destroying a car in GTA, or the other players in the game), some you can to some degree (i.e. bushes might sway when you walk by, but you can't shoot them for example), and some you cannot (like the sun in a skybox).

I am thinking in terms of state syncing, it seems like there must be IDs somewhere in the picture so you can map a game entity from computer A to the same game entity in computer B. Even without syncing, it seems like you might want some sort of IDs on objects to allow for easier handling of events and tracking objects. But at the same time I don't really see "IDs" in simple "game engines" like these JavaScript game engines, so that is why I'm asking the question.

The question is, for large games like Halo, what the entities are that have IDs (or some of the main ones), and if the IDs are GUIDs (or generally what kind of ID they are: incremented integers, random numbers, UUIDs, etc.).

Like I'm wondering, maybe bushes have IDs. Maybe the individual leaves on the bushes have IDs. Maybe every single triangle in the graphics has an ID. That's what I'm wondering. Maybe the shards of glass have IDs because you can pick them up. Maybe only the players have IDs for some reason. Etc.

I am interested because (a) it seems like IDs are necessary in different ways (for state syncing, for tracking player behavior with different entity types to improve the game experience, etc.), and (b) there is a lot of variation in performance when it comes to using IDs. For example, I just tried generating 1 million particles like this and got these results:

  1. crypto.getRandomValues: 5.7 seconds to generate 1 million IDs.
  2. Math.random(): 18ms to generate 1 million IDs.
  3. i++: 5ms to generate 1 million IDs.

In addition, there is the space constraint, so by using i++ you can use fewer bits for the ID until it gets very large, but they don't work as GUIDs so you need to do extra work to create ID "scopes" or things like that. Anyways, I would like to figure out how to deal with IDs in games, and looking to FPS as an example to demonstrate where the IDs might be used. Any help would be appreciated. Thank you.

If it is a complicated topic (I'm not sure), then just knowing roughly an outline of how it is typically done, or even a place to look for more information, would be helpful. Also, just saw how Unity is a good example of a Component/Entity system, so maybe instead of FPS a better example is how generic game engines do it. Either way, whatever helps explain how it works.

\$\endgroup\$
1
\$\begingroup\$

Generally entity IDs are simply generated by incrementing an integer starting at some base value (0, or 1 if you want 0 to mean "no entity"). In other words, your ++i approach. Some games may "bucket" the integer space by type, for example by saying that "characters will use IDs 100 to 999, bullets will use IDs 1000 though 1999" and so on. This kind of grouping may or may not be necessary, it all depends on how the game works.

This approach is fast and easy, fits well with the typical desire to store objects in big, contiguous arrays indexed by ID, and is deterministic as long as the call order is also deterministic.

When you need actual, full-on GUIDs, version 4 GUIDs are generally used are produced by appropriate standard or third-party APIs (such as C#'s Guid.NewGuid() function). You may want these if you need to generate IDs that are keys in a database, or unique across gameplay sessions, et cetera.

Random generation of integer IDs is rarely useful, and often very problematic.


As for what gets an ID? That depends on the game. An ID is really only needed if the object will need to be referred to on its own, independently of any kind of parent/child hierarchy or whatever. Something like leaves on a bush will probably not be separate entities with their own ID -- they probably won't exist as anything but random vertices on a bush static mesh that has an entity ID. But maybe in a game where splitting individual leaves off a bush is a critical aspect of gameplay, they'll get IDs and be first-class entities.

It really depends on the needs of the game.

\$\endgroup\$
  • \$\begingroup\$ Thank you, good to know. Wondering if you could explain more of the GUID usage case. If you have a game like WoW then it seems the whole world is "unique across gameplay sessions" (I've never played so I don't know if that's true). But since the players are people from around the world, at least the players, and maybe the realms and "items" you get in the game have GUIDs. Would like to know more about that, that's where I start getting confused. Because then ++i no longer seems to apply. \$\endgroup\$ – Lance Pollard Aug 21 '18 at 20:09
  • \$\begingroup\$ GUIDs are big and slow and you don't really need them everywhere you'd assume you might. A player's account might be identified by a GUID, but item definitions within the game probably won't, nor would individual instances of items in the world. \$\endgroup\$ – Josh Aug 21 '18 at 20:12
0
\$\begingroup\$

GUIDs and IDs (using integer iterators) have the same purpose, but are generated differently. GUIDs, consisting generally of alphanumeric characters, might present collisions on the same client (not good!). While GUIDs might present collisions on the same client, they usually prevent collisions on different clients:

  • Client A generate a random GUID using multiple paramenters such as time, some info from hardware, the time the game was open, etc.
  • Client B generate a random GUID using the same parameters, but since they (probably) have a different hardware, and didn't open the game at exactly same time, they will have a different GUID!

IDs from integer iterators are much more safe in the case of preventing collisions in the same client, since a collision will only happen during integer overflow (the integer reached the maximum value, and will start from 0 again).

On the other hand, IDs from integer iterators need to be sanitized in multiplayer cases, otherwise the clients will have IDs that collide since both are starting from 0. Solutions for this:

  • Only one client will generate IDs, and will send a new ID when other client asks.
  • Each client use their own ID iterator, but they use another information to avoid the collisions. This information could be the IP address from the other client.

Particles of light, individual pixels, physical forces, etc. (the lowest level vectors/points for calculating light or physics stuff).

There's (almost) no reason to sync visual effects between two clients.

Topology (mountains, roads, etc.). Landscape features (grass, bushes, trees, rocks, water, rain drops, etc.). City features (cars, signs, buildings, windows, shards of glass from a broken window, etc.).

Maps, in general, are not synchronized, unless they are destructible. If the maps are pre-made, and exists in both clients, one client just send to the name of the map they are going to play. If the map is procedurally generated, then it's sent at the beginning of the round.

If some parts of the map are destructible, then you will need an ID for them, to inform the other client which part was destroyed and that should be synchronized. If in client A, a wall of ID 3 was destroyed and generated 10 pieces of rock flying around (with their own ID) and a smoke effect, a message will be sent to client B informing that wall of ID 10 was destroyed, and to generate the 10 pieces of rock with those IDs sent. There will be no message informing to create a smoke effect, because they are not gameplay-critical, the smoke, without ID and synchronization, will be created in client B when the wall is destroyed. The rocks flying around are objects that can be interacted with: if the player is hit by a rock, the player loses HP, or the player could pick a rock to throw in another player, for example. Therefore, the rocks have IDs and are synchronized, because they are gameplay-critical objects.

Tools / items (weapons, potions, etc.).

Most of the time, these objects have their own ID, and are synchronized between clients.

Other players.

Definitely have IDs.

In other words, entities that are both "interactible" and have gameplay importance, should have an ID.

In addition, there is the space constraint, so by using i++ you can use fewer bits for the ID until it gets very large, but they don't work as GUIDs so you need to do extra work to create ID "scopes" or things like that. Anyways, I would like to figure out how to deal with IDs in games, and looking to FPS as an example to demonstrate where the IDs might be used. Any help would be appreciated. Thank you.

If you are using a 64-bits unsigned integer, the maximum value you can have is 18.446.744.073.709.551.615. If you create 1000 objects per frame, and each second has 60 frames, it will take 3.0744573456×10¹⁴ years to reach the maximum number of IDs. In most cases, it's a number to big that you could use the same iterator for every object, no matter the type, in the world.

\$\endgroup\$
  • \$\begingroup\$ Thank you. I understand these things, what I would like to know more about is the "unless they are destructible" case, and when to use "64-bit unsigned integers". \$\endgroup\$ – Lance Pollard Aug 21 '18 at 20:16
  • 1
    \$\begingroup\$ Added an example for the case of destructible maps, and the pros-cons of IDs with 64-bit unsigned integers and GUIDs. \$\endgroup\$ – Ferreira da Selva Aug 21 '18 at 20:39

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.