Jump to content

  • Log In with Google      Sign In   
  • Create Account

Getting unique object IDs in peer-to-peer


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
11 replies to this topic

#1 Brendon Chung   Members   -  Reputation: 100

Like
0Likes
Like

Posted 11 April 2011 - 08:46 PM

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.

Sponsor:

#2 Hodgman   Moderators   -  Reputation: 31984

Like
1Likes
Like

Posted 11 April 2011 - 09:42 PM

The first thing that comes to mind is to encode the "creating client" ID in the high-byte of the object ID.
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;


#3 hplus0603   Moderators   -  Reputation: 5730

Like
1Likes
Like

Posted 11 April 2011 - 10:38 PM

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.


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).
enum Bool { True, False, FileNotFound };

#4 Brendon Chung   Members   -  Reputation: 100

Like
0Likes
Like

Posted 11 April 2011 - 11:12 PM

@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?

#5 hplus0603   Moderators   -  Reputation: 5730

Like
2Likes
Like

Posted 12 April 2011 - 12:05 PM

@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?


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.
enum Bool { True, False, FileNotFound };

#6 BeerNutts   Crossbones+   -  Reputation: 3018

Like
1Likes
Like

Posted 12 April 2011 - 03:12 PM


@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?


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.


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:
struct
{
    int Owner;
    int ID;
} tTankUnitId;



That's guaranteed to be Unique, and you only need a local ID counter.
My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#7 frob   Moderators   -  Reputation: 22792

Like
0Likes
Like

Posted 12 April 2011 - 04:21 PM

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.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#8 Brendon Chung   Members   -  Reputation: 100

Like
0Likes
Like

Posted 12 April 2011 - 06:56 PM

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

#9 hplus0603   Moderators   -  Reputation: 5730

Like
0Likes
Like

Posted 12 April 2011 - 07:51 PM

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


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.
enum Bool { True, False, FileNotFound };

#10 Brendon Chung   Members   -  Reputation: 100

Like
0Likes
Like

Posted 12 April 2011 - 08:48 PM

@hplus0603 - I think I understand what you're getting at now.

Right now, here's how my system works:
  • 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.
If I understand you correctly, the local client should not queue up commands locally?

#11 rip-off   Moderators   -  Reputation: 8764

Like
0Likes
Like

Posted 13 April 2011 - 05:31 AM

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.

#12 hplus0603   Moderators   -  Reputation: 5730

Like
0Likes
Like

Posted 13 April 2011 - 01:09 PM

If I understand you correctly, the local client should not queue up commands locally?


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.
enum Bool { True, False, FileNotFound };




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