Math Q: How do Internet video games solve the "shot at same time" dilemma?

[yllus]

I've wondered for some time how multiplayer video games - that is, those involving players distributed across a network - decide upon a winner in this typical situation:

Player A and Player B fire a one-shot-kills bullet at each other at nearly the same time - Player A's fires 1/1000th of a second first. Being that each player is on their own machine across a network and that the time on their machines is not necessarily correct (a bit fast or a bit slow), you can't trust that data. How is the who shot first decision made?

I thought that Lamport timestamps might be the solution, but after thinking about it while doing dishes this morning I'm not so sure - that seems to solve the issue only when A and B talk to each other first, and then each try to contact C. I'm starting to suspect that the only solution is to start each game session with a "synchronize!" command to all machines, and then further synchronize commands at regular intervals during the match (plus tracking of what machines fall behind and built-in compensation for it). I keep thinking I might be missing a simpler solution, though. Anyone have any ideas?

 

[nick1985]

In BFBC2 you both die. If I had a nickel for all the times that's happened to me in that game I could retire.

 

[yllus]

Yeah, in the Halo games you also both die - and that's not a bad solution considering that the alternative is one player consistently winning because the who-wins algorithm just happens to be in his Xbox's favour for that match (my Xbox's local time is 1/100th of a second before you, thus I always win). There's got to be an overall strategy for this sort of thing that I'm curious about.

 

[DayLaPaul]

I remember only one instance of a double death (not including nades) in Counterstrike but that was in early beta. Now whoever fires first always gets the kill. In the event that you both fired at the *exact* same time, I believe he who does the most damage past 0 HP gets the kill.

 

[CZroe]

The same way offline 2p+ simultaneous games do.

 

[Malak]

In CoD you both die. Has happened to me on several occassions. Back in the day when bullets were instant hits this couldn't occur.

 

[DrPizza]

Quake 3, both die as the bullets actually take time to travel.

 

[GodlessAstronomer]

Heh I went through a whole computer science degree without coming across Lamport timestamps. Interesting article.

As for your question OP, I'm not really sure but I'm interested to hear the answer.

 

[jlee]

In BFBC2 you both die. If I had a nickel for all the times that's happened to me in that game I could retire.

I came in here to post this.

 

[yhelothar]

What about if player A and player B are on the same team, and they both one shot kill player C at the exact same time.

Who gets the kill?

 

[JS80]

I wonder what CS would be like if both parties could die.

 

[biggestmuff]

Bungie used to blog about this type of stuff. Should be easy to find. I can't think of any other developer that has written about it.

 

[0roo0roo]

very rare, i'm not sure what it involves when adding lag compensation. only remember it once.

 

[yllus]

The same way offline 2p+ simultaneous games do.

Unless I'm missing something, the process of having multiple machines involved make it much more complicated than the offline scenario.

Quake 3, both die as the bullets actually take time to travel.

You were my #1 hope to know of a mathematical approach for this problem!

Bungie used to blog about this type of stuff. Should be easy to find. I can't think of any other developer that has written about it.

I thought so too, but I can't find anything. I posted this question on Quora hoping it comes to someone's attention...

 

[mpo]

The Source Engine's multiplayer networking page deals with this:
http://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

A relevant quote:

The lag compensation system keeps a history of all recent player positions for one second. If a user command is executed, the server estimates at what time the command was created as follows:

Command Execution Time = Current Server Time - Packet Round-Trip-Time - Client View Interpolation​

Then the server moves all other players - only players - back to where they were at the command execution time. The user command is executed and the hit is detected correctly. After the user command has been processed, the players revert to their original positions.

 

[CZroe]

Unless I'm missing something, the process of having multiple machines involved make it much more complicated than the offline scenario.


You were my #1 hope to know of a mathematical approach for this problem!


I thought so too, but I can't find anything. I posted this question on Quora hoping it comes to someone's attention...

No. The logic of deciding is the same. The compensations considered do but, as anyone knows, the compensations aren't always fair. Your rail shots in Quake III Arena connect immediately if you are the host, but your opponents have to "lead" you by varying amounts according to their latency.

Quake 3, both die as the bullets actually take time to travel.

Rail shots don't.

 

[yllus]

The Source Engine's multiplayer networking page deals with this:
http://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Excellent, thanks! This is what I was looking for.

No. The logic of deciding is the same. The compensations considered do but, as anyone knows, the compensations aren't always fair. Your rail shots in Quake III Arena connect immediately if you are the host, but your opponents have to "lead" you by varying amounts according to their latency.

If you introduce trust logic, lag compensation logic and interpolation logic, then, no, in a networked game your logic is different than that of a game played on a single machine.

 

[0roo0roo]

http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_288_network_.php
just for the lols

 

[somethingsketchy]

I thought that Lamport timestamps might be the solution, but after thinking about it while doing dishes this morning I'm not so sure - that seems to solve the issue only when A and B talk to each other first, and then each try to contact C. I'm starting to suspect that the only solution is to start each game session with a "synchronize!" command to all machines, and then further synchronize commands at regular intervals during the match (plus tracking of what machines fall behind and built-in compensation for it). I keep thinking I might be missing a simpler solution, though. Anyone have any ideas?

The only question I would have at this point, with all of the "sync" commands, is how much extra overhead would be introduced into the current game. It would be all right if this command was done every 15 seconds, but I would think at 60 times a minute, you would start to introduce more "lag" into the game.

 

[CycloWizard]

Quake 3, both die as the bullets actually take time to travel.

It depends on the weapon. The railgun, machinegun, and shotgun are all "direct fire," meaning that their shot hits instantly when you shoot. The way Q3 handles the problem is by splitting server/client communications into discrete time events (sv_fps is the console command for setting steps per second, IIRC). As long as two shots are fired within this time step, they will be treated as simultaneous by the server. This works very well in a low-ping environment when the server has access to all of the information for every player within that time increment, but it starts to break down when pings approach the time interval of a single interval. I'm actually not sure what happens in that case, though it may depend on a number of other settings.

 

[Malak]

Quake 3, both die as the bullets actually take time to travel.

Quake 3 didn't have bullet travel time.

 

[SSSnail]

I don't think it cares. They calculate it based on the HP and the damage done per hit, once the damage factor leaves, it couldn't care less when it gets there, but when it gets there if the DMG > HP then the person dies (and lag be damned).

 

[CZroe]

Quake 3 didn't have bullet travel time.

Not for machine or rail guns, but the rocket launcher, BFG, grenade, and plasma certainly did. There was obviously some slack in the calculations because I can't tell you how many times I and my opponent have both died together when facing off with insta-kill weapons.