Sign in to follow this  
Brendon Chung

Getting unique object IDs in peer-to-peer

Recommended Posts

I'm creating a lockstep multiplayer game, and I'm having trouble creating unique IDs for my newly-spawned objects (for example, when a new tank is spawned in an RTS game). All clients would then use this ID number to refer to the object.

I'm using a peer-to-peer model, so I don't have a central server keeping track of every object. How does one approach generating a series of unique object IDs in a peer-to-peer model? Basically, I'd like to assign a unique ID number to every object I spawn. At first I kept a running "LastID" counter across the clients that increments every time an object is created, but it seems there should be a better way to do this locally.

Share this post


Link to post
Share on other sites
The first thing that comes to mind is to encode the "creating client" ID in the high-byte of the object ID.[code]static int last_id = 0;
int this_client_id = 42;

int new_id = ++last_id;
new_id = (new_id & 0x00FFFFFF) | (this_client_id&0xFF)<<24;[/code]

Share this post


Link to post
Share on other sites
[quote name='Brendon Chung' timestamp='1302576375' post='4797357']
I'm creating a lockstep multiplayer game, and I'm having trouble creating unique IDs for my newly-spawned objects (for example, when a new tank is spawned in an RTS game). All clients would then use this ID number to refer to the object.

I'm using a peer-to-peer model, so I don't have a central server keeping track of every object. How does one approach generating a series of unique object IDs in a peer-to-peer model? Basically, I'd like to assign a unique ID number to every object I spawn. At first I kept a running "LastID" counter across the clients that increments every time an object is created, but it seems there should be a better way to do this locally.
[/quote]

If you're using lock-step, then all the peers will create the same unit with the same ID, so there should be no problem. Use whatever method you want (such as a running counter of number of units spawned in game).

Share this post


Link to post
Share on other sites
@hodgman - I think this is exactly what I was looking for! The clientID + local counter generates a unique ID number for every new object.

@hplus0603 - I was under the impression that if clients created new unit IDs via "New unit ID = total unit count + 1", it opened the possibility for multiple units getting the same ID number. Such as, if two clients both created units during the same lockstep "turn" -- during that turn, wouldn't both clients generate the exact same "total unit count + 1" value?

Maybe I'm misunderstanding how lockstep works?

Share this post


Link to post
Share on other sites
[quote name='Brendon Chung' timestamp='1302585174' post='4797385']
@hodgman - I think this is exactly what I was looking for! The clientID + local counter generates a unique ID number for every new object.

@hplus0603 - I was under the impression that if clients created new unit IDs via "New unit ID = total unit count + 1", it opened the possibility for multiple units getting the same ID number. Such as, if two clients both created units during the same lockstep "turn" -- during that turn, wouldn't both clients generate the exact same "total unit count + 1" value?

Maybe I'm misunderstanding how lockstep works?
[/quote]

It sounds like you're misunderstanding how lockstep works, yes. In lockstep execution, UI to give commands is separated from the command queue to execute commands.
On turn N, users will issue commands through the UI. These commands will be queued for turn N+M, where M is the maximum transmission latency.
On turn N+M, all users will have gotten all the commands from other users, and sorted them in the same order, and then executes all those commands.
If, at turn N+M, you haven't gotten a "done with turn N" message from all the peers, then there is a disconnect/lag event, and you have to stall simulation until you resolve it.
Because everybody is executing the same commands in the same order, the simulation will be exactly the same, and thus the IDs will be allocated exactly the same.
If this is not how your simulation works, then it's not a lock-step simulation.

Share this post


Link to post
Share on other sites
[quote name='hplus0603' timestamp='1302631539' post='4797602']
[quote name='Brendon Chung' timestamp='1302585174' post='4797385']
@hodgman - I think this is exactly what I was looking for! The clientID + local counter generates a unique ID number for every new object.

@hplus0603 - I was under the impression that if clients created new unit IDs via "New unit ID = total unit count + 1", it opened the possibility for multiple units getting the same ID number. Such as, if two clients both created units during the same lockstep "turn" -- during that turn, wouldn't both clients generate the exact same "total unit count + 1" value?

Maybe I'm misunderstanding how lockstep works?
[/quote]

It sounds like you're misunderstanding how lockstep works, yes. In lockstep execution, UI to give commands is separated from the command queue to execute commands.
On turn N, users will issue commands through the UI. These commands will be queued for turn N+M, where M is the maximum transmission latency.
On turn N+M, all users will have gotten all the commands from other users, and sorted them in the same order, and then executes all those commands.
If, at turn N+M, you haven't gotten a "done with turn N" message from all the peers, then there is a disconnect/lag event, and you have to stall simulation until you resolve it.
Because everybody is executing the same commands in the same order, the simulation will be exactly the same, and thus the IDs will be allocated exactly the same.
If this is not how your simulation works, then it's not a lock-step simulation.
[/quote]

What if, on Turn N, two users create a Tank Unit. The Programs assign each Tank an ID = X, and they happen to be the same. When the Synch time comes, they notify the others they created a Tank of ID X, but it's the same.

That may be the situation he's talking about, not a case of only 1 user can act during a turn. Just a guess though.

However, when you create any Unit, you should have, besides a unique ID, who created/Owns it. For example, have a structure:
[source]
struct
{
int Owner;
int ID;
} tTankUnitId;

[/source]

That's guaranteed to be Unique, and you only need a local ID counter.

Share this post


Link to post
Share on other sites
A note about lockstep: It tends to be very slow, and performance is based on the worst-case communications patterns through your mesh.


For lockstep, you have to wait until everybody gets the data, and everybody has confirmed it to everyone, then all simulations do the same single processing step. Then you again have to wait until everybody gets the data, everybody confirms, etc., repeating.

The worst case of peer-to-peer is that everybody is connected in a single line. Now you have to wait for data to propagate from client 1, to 2, to 3, to 4, ... to N, and then back to 1.


Combining the two: In a lockstep P2P, you can potentially need to wait the sum of EVERYBODY's communications time at least twice. So with 8 players you might need to wait 2 seconds or more before you can advance a single step.


This may work perfect in a small turn-based game with few players. Lockstep P2P will probably fail spectacularly in a larger RTS.

Share this post


Link to post
Share on other sites
@BeerNutts - Yes, that's the situation I was trying to describe. Similar to what you & Hodgman suggested, I'm now creating new unit IDs based off the client ID & local running counter.

@Frob - thanks for the tip. The game is running well now, but I do get the feeling I may have to investigate other models once I expand it further.

Share this post


Link to post
Share on other sites
[quote name='Brendon Chung' timestamp='1302656218' post='4797729']
@BeerNutts - Yes, that's the situation I was trying to describe. Similar to what you & Hodgman suggested, I'm now creating new unit IDs based off the client ID & local running counter.

@Frob - thanks for the tip. The game is running well now, but I do get the feeling I may have to investigate other models once I expand it further.
[/quote]

You do not create a tank locally on a particular turn. You enqueue the command to create a tank. When the time comes to execute the enqueued command, everybody executes it at the same time, and thus allocate the same ID for the tank. If you do it any other way, your system is not lock-step, and you will de-sync.

Lock-step systems are not slow at all. You can create and update thousands of units per player in a lock-step system -- try that with a state-based system, I dare you :-)
However, lock-step systems do require you to hide latency -- the "M" parameter in my original explanation. In most RTS games, the "yes sir!" animation that plays once a command is issued is enough to hide the latency of transmitting the command to all other users, so that it can actually be executed.
There exist lock-step systems for FPS networking. The "C4" game engine multiplayer demo, for example, is lockstep in nature. When playing between Europe and the US, the latency is annoying; when playing within the same state, the latency is hardly noticeable.

Share this post


Link to post
Share on other sites
@hplus0603 - I think I understand what you're getting at now.

Right now, here's how my system works:
[list][*]Client sends a queued command ("spawn a unit during lockstep turn #52") to all the other clients.[*]Locally, the client queues up the same command on the local machine.[*]Once everyone reaches lockstep turn #52, that spawn order is executed.[/list]
If I understand you correctly, the local client should not queue up commands locally?

Share this post


Link to post
Share on other sites
The command needs to be queued on every peer, so the local machine needs to enqueue the command to. You still need to ensure that commands in each peer's queue will be executed in the exact same order as the remote queues.

For example, you could sort your local command queue by the peer identifier (e.g. the IP, or a peer id # known to all peers). Don't forget to use an algorithm/data structure that maintains the relative ordering (e.g. C++ std::stable_sort() over std::sort()), so that commands by a given peer aren't reordered relative to one another.

Share this post


Link to post
Share on other sites
[quote name='Brendon Chung' timestamp='1302662931' post='4797758']
If I understand you correctly, the local client should not queue up commands locally?
[/quote]

The local client can queue the command locally as an optimization instead of "sending it to itself." The main thing that matters is that the id of the tank to create is not in the command, but instead is derived at the point where you execute the create command in the command stream. That, and making sure that all peers execute all commands in the exact same order.

Share this post


Link to post
Share on other sites

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