How can I assign entity IDs in a robust way in a network game?

Question

I'm working on an entity system for a networked game and I'm assigning each entity a unique 32-bit integer id that I can use to serialize references to entities and the entities themselves.

Currently I'm just incrementing a counter every time an entity is created. I guess the ids will eventually run out but I don't really expect to have 4 billion entities. Also this avoids the problem if entity #5 is destroyed and we get an id of 5. Is it meant to refer to the new #5 or the old deleted #5?

The problem is that I'm not sure how to handle/avoid collisions. Currently if a client receives an update for an entity with an id higher than it's current "free id" it just bumps it's free id up to past that. But that doesn't seem very robust.

I thought about maybe assigning ranges to each client so they can allocate entities without conflicting (say the top n bits are the player number) but I'm worried about what happens if ranges began to overlap over time.

Is there a better way of handling this? Should I even care about ids overflowing or going past the end of the allowed range? I could add code to detect these cases but what would it do if they happen other than crash.

Another option is to use something with a higher chance of being unique like a 128-bit GUID but that seems really heavyweight for a game that's trying to minimize network traffic. Also, realistically I would never need more entities at one time then would fit into a 32-bit or even 24 bit integer.

Thanks!

Answer 1

What I have done is make the server do everything. The client(s) can merely ask the server to do something but can't do anything themselves. In this case, the server will always be the one assigning IDs and problem solved.

I have not dealt with client-side prediction while waiting for the server to approve actions like: "Shoot a rocket" or "Make a solar station here". These actions will want to create entities, and entities have IDs. So far, I'm just sitting on my thumb waiting for the server, but I believe what needs to be done is create a temporary entity while you wait for server approval. When you receive server approval, the server will assign an ID and you can either update or overwrite the temporary object.

I also have not dealt with an ID overflow, but if the server is in full control and it detects an overflow, it could do whatever handling you deem necessary (restart at 0, pick from a free stack, crash, etc) and all of the clients won't even know or care. The clients will just accept the IDs handed out by the server.

Answer 2

When I did this for a commercial multiplayer game, I did exactly what you propose: use a 32-bit GUID integer, where the top eight bits are the player number, and the bottom twenty-four bits contain a locally unique number.

If/when the local number overflows (in my case, it would almost never happen; under normal usage, it would have taken four to five days of continuous playtime in a single network session to cause it to happen), the owner would send a "Resetting all my objects" message, and renumber all still-existing objects starting from zero ago. The message told all peers to discard objects they had received and to query for them again.

A more fancy approach would be a "Object with GUID 'n' is now Object with GUID 'm'" message for every existing object. But in my case, it was unlikely to ever actually happen, and I didn't think people would really mind remote objects vanishing from the world for half a second, after five days nonstop play in a single network session. ;)

Answer 3

If your clients can spawn their own entities, I'm guessing you have a peer-to-peer multiplayer game.

If that's the case, you probably don't have too many clients. Certainly not more than 256. And your entity id is guaranteed to fit into 24 bits (16000000+ entities is enough for everyone!). So, just make the highest byte of your id equal to client's id:

entityId = clientId<<24 + (maxEntityIn++)

or something.

And if I'm wrong and you have an authoritative server, just never create new entities on clients.

Answer 4

I'm using the 'most naive' method (just increment an integer for each new ID) in my persistent multiplayer game and it works fine because I don't let the client create new ID:s.

If you let the client decide (by using a sort of GUID technique explained), the client can also introduce various bugs by assigning an Old ID to a new item (that is just what I thought up on top of my head thinking like 5 seconds, there might be loads of other loopholes).

As usual, to prevent cheating, the server should do ALL creation and validating.