I’ve always wondered 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 one-shot-kills bullets 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), the game server cannot simply trust the received data. How are these life or death decisions made?

I posed the question to Quora and only received unhelpful answers. Elsewhere, however, I was provided two good sources that each answered the question. First, from The Valve Developer Community – Source Multiplayer Networking page:

Multiplayer games based on the Source Engine use a Client-Server networking architecture. Usually a server is a dedicated host that runs the game and is authoritative about world simulation, game rules, and player input processing. A client is a player’s computer connected to a game server. The client and server communicate with each other by sending small data packets at a high frequency (usually 20 to 30 packets per second).

A client receives the current world state from the server and generates video and audio output based on these updates. The client also samples data from input devices (keyboard, mouse, microphone, etc.) and sends these input samples back to the server for further processing. Clients only communicate with the game server and not between each other (like in a peer-to-peer application). In contrast with a single player game, a multiplayer game has to deal with a variety of new problems caused by packet-based communication.

…

Basic Networking

The server simulates the game in discrete time steps called ticks. By default, the timestep is 15ms, so 66.666… ticks per second are simulated, but mods can specify their own tickrate. During each tick, the server processes incoming user commands, runs a physical simulation step, checks the game rules, and updates all object states. If the game is large or the servers busy dealing with a roblox hack, this may interfere with gameplay.

After simulating a tick, the server decides if any client needs a world update and takes a snapshot of the current world state if necessary. A higher tickrate increases the simulation precision, but also requires more CPU power and available bandwidth on both server and client.

…

Lag Compensation

Let’s say a player shoots at a target at client time 10.5. The firing information is packed into a user command and sent to the server. While the packet is on its way through the network, the server continues to simulate the world, and the target might have moved to a different position. The user command arrives at server time 10.6 and the server wouldn’t detect the hit, even though the player has aimed exactly at the target. This error is corrected by the server-side lag compensation)

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.

Client and server hitboxes don’t exactly match because of small precision errors in time measurement. Even a small difference of a few milliseconds can cause an error of several inches for fast-moving objects. Multiplayer hit detection is not pixel perfect and has known precision limitations based on the tickrate and the speed of moving objects. Increasing the tickrate does improve the precision of hit detection, but also requires more CPU, memory, and bandwidth capacity for server and clients.

The question arises, why is hit detection so complicated on the server? Doing the back tracking of player positions and dealing with precision errors while hit detection could be done client-side way easier and with pixel precision. The client would just tell the server with a “hit” message what player has been hit and where.

We can’t allow that simply because a game server can’t trust the clients on such important decisions. Even if the client is “clean” and protected by Valve Anti-Cheat, the packets could be still modified on a 3rd machine while routed to the game server. These “cheat proxies” could inject “hit” messages into the network packet without being detected by VAC (a “man-in-the-middle” attack).

Another great article on the subject is Gamasutra – 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond, which talks about the same subject from the perspective of a RTS game and in the age of dial up.