Hey, A Message Board - Networking, Lag Compensation, and Hit Detection

Hey, A Message Board
« Networking, Lag Compensation, and Hit Detection »

Welcome Guest. Please Login or Register.
May 26, 2013, 3:33am

Hey, A Message Board :: Call of Duty :: Hey, Den :: Networking, Lag Compensation, and Hit Detection

Page 1 of 6 » Jump to page Go

Author

Topic: Networking, Lag Compensation, and Hit Detection (Read 9,332 times)

Mousey
True Bro
member is offline

[avatar]

estrogen high

Joined: Dec 2010
Gender: Female

Posts: 9,980
Location: aroo

Networking, Lag Compensation, and Hit Detection
« Thread Started on Feb 4, 2013, 3:59pm »

Because Mousey shitposts a lot and you all deserve better from her

In not so recent developments, lag has taken the number one spot as a scapegoat for the average dickweed's death. So much so that people completely made up explanations as to how "lag comp screws you over" or whatever. On top of that, this bullshit is actually considered common knowledge in some places (gamefaqs, reddit, official forums, youtube, the list goes on). I'm sure that most of you have seen Den's quick post on lag compensation/anti-lag, but I'm going to expand upon that. I'm just trying to dispel some of the stuff surrounding that for the sake of this forum since I'm sure a good number of our users come from those sites i mentioned. Now keep in mind that I do not have any networking source code. This is going over the basics of a listen server alongside more gameplay related issues such as hit detection. It's important to note that while Treyarch and IW split off from each other at CoD4 (as in, both MW2 and W@W were modded from CoD4 and they've been modding their own game since then) there isn't really any evidence of them having changed the core networking mechanics beyond deciding hosts and organizing matches (there's a lot of speculation that black ops 2 has changed certain elements but no proof for now so I'll leave it at that). THAT BEING SAID, this is a fairly long read. The important points of each section will be printed in gold and key terms will be in green* for those of you who don't really care all that much.

*I apologize to the colorblind people who may have some trouble skimming because I picked green for keywords

Table of Contents
[1.0] How does networking work?

[1.1] Network Structure
[1.2] Transferring Data

[2.0] How does lag affect me?

[2.1] Latency, Jitter, Three bars, etc.
[2.2] Input Prediction
[2.3] Hit Detection and Lag Compensation
[2.4] Interpolation and Artificial Delays

[3.0] How does this come into play?
[*][2.5] Packet Loss

[3.1] Connection Discrepancies pt.1
[3.2] Connection Discrepancies pt.2
[3.3] Killcams

[4.0] Matchmaking

[4.1] Sorting players
[4.2] Hosts and Migrations

[1.0] How does networking work?

[1.1] Network Structure
[image]

Obviously multiplayer games need a system that is capable of transferring data between the players. Virtually all modern multiplayer videogames utilize Client-Server networking or Peer-to-peer networking. In the case of Call of Duty, it uses a certain type of Client-Server based network called a Listen Server. This differs from the standard Dedicated Server (The PC versions of BO2, CoD4, and W@W use this) in that a listen server hosts both the server and client in the same location. Listen servers are generally inferior to dedicated servers in every way except for price, because it is more stressful on a single system and is limited by the host's internet connection. To simply put it, Clients send data to the server, which then organizes it and sends it out to all of the clients simultaneously, which then use that data to generate the world. Here's a slightly closer look using the Quake 3 networking model:*

[image]

*The IW engine is based off of the Quake 3 engine along with countless other shooters. They have their distinctions but the basics are pretty standard.

THE SYSTEM WORKS AS SUCH:
So the Server or Host has a Master Gamestate. This is the "official" state of the game at any given time. The host will attach a sequence number and a timestamp onto it and send it out to the clients. This is called a Snapshot. When the client receives this data. It makes a copy of the master gamestate and saves it in its memory. The client will then compare the snapshots in memory to generate a game state. If the client doesn't have any "valid" snapshots in history (either the last timestamp was too long ago due to lag issues or it just has connected and hasn't received data yet) the client will compare the snapshot with the dummy snapshot, which has every value equal to zero. The client will at the same time send inputs from the player or game (movement, hit detection, etc.) to the Server. The client will also acknowledge that it has received the previous snapshot and tell that to the server. When the server receives this data from the clients it utilizes it to create a new master gamestate, and acknowledges each client that it received the data. Lather, rinse, repeat. *

[1.2] Transferring Data
The biggest setback of online gaming is that it has to obey the laws of physics. That being, data does not travel instantly. This causes major discrepancies in the actual game, but we'll get to that later (or skip to 2.1 if you don't give a fuck about how it works).

Now all games can choose to use TCP or UDP for data transfer. In short, TCP is very reliable at getting the information in its entirety and order from one location to another. However, the manner in which it does this is slow for various reasons. This is far too slow of a process in multiplayer games but it is perfectly fine for organizing matches, stat tracking, or pretty much anything that can afford to take more than half a second. UDP basically send the packet out with a destination stamped onto it and hopes it gets there; and it does that pretty well. The main issues with UDP is that packets tend to arrive out of order and it's quite prone to packet loss (around 1-5% of the data likely won't arrive). A good layman's comparison of the two can be found here (and it goes into more detail in the following articles).

So the game needs to use UDP for speed reasons. So developers have to find ways to get past its faults. Now for the first issue, which is packets arriving in the wrong order, the server assigns a sequence number to outgoing data. On the client side, if any data received has a sequence number less than that of the current sequence number, the data is trashed. This effectively keeps things in order. Packet Loss is handled by each packet containing an ACK or acknowledgement. The client and server use ACKs to tell one another that they have received each other's data. Obviously any important data that wasn't sent (and needs to be) is resent.

[2.0] How does lag affect me?

[2.1] Latency, Jitter, Three bars, etc.
Alright, back to a more macro-scale of networking. So we know that the main limit to online gaming is the sheer fact that data takes time to get from point A to point B. Latency is the time delay between these points. One way latency is the time taken to get from source to destination, while round trip latency is of course the time taken for data to go from the source, to the destination, back to the source. Jitter or Packet Delay Variation is the standard deviation in latency from the mean latency. Ping is a network utility for accurate determining latency, in which either a client or server sends a message to the other and awaits a response. The Latency Bars (or ping bars, whatever) display the results from one's most recent ping test to the host. It's a really simple system, really:

4 Bars = less than 100 ms of latency
3 bars = 100-200 ms of latency
2 bars = 200-300 ms of latency
1 bar = over 300 ms of latency

Now in a game like CoD, 100 ms of ping is a lot. When combined with interpolation (discussed in 2.4) and short kill times yields a significant delay in what a person does. Now that's not to say it isn't still accurate, (as far as hit detection goes, CoD is fucking fantastic for the shooter) just that poor connection has a huge influence on one's performance. I'm not going to be referring to connections as "four bars" throughout this because bars are fucking stupid and really only exist because a number is too complicated for some people.

[2.2] Input Prediction
Alright imagine the following scenario: You press the button that makes you move forward. Notice how your character instantly responds and moves forward himself. But how? After all, that data hasn't reached the server yet. This is the effect of Input Prediction. Input prediction realizes what the player will do before the information reaches the server and back to the client, and applies it instantly in order to smooth gameplay. Basically, Input prediction executes local commands instantaneously. The alternative here is for one to input a forward move, send that info to the server, which would send it back in the next snapshot, and then you would move. You'd be a clear split second behind everything you tried to do. This system allows the game to run fluidly for every individual client while having the side effect of one's commands being asynchronous with what the server is sending out in snapshots* (which will be more obvious in a bit).

*Of course you wouldn't be synchronized with the server anyway due to latency; however, without prediction you would receive your own inputs in the same manner that everyone else is getting them.

[2.3] Hit Detection and Lag Compensation
So, we know that input prediction makes the client asynchronous with the server, but how does that effect gameplay? Well the first major issue is with hit detection. Hit detection or hit authentication is the game's way of telling whether or not you've managed to actually hit your enemy. There are two main forms of doing this: Client Side Hit Authentication and Server Side Hit Authentication.

Client Side Hit Authentication means that each individual client keeps track of when it hits an enemy, and simply send the data of it being a hit to the server. The primary benefit of Client Side hit detection is that it is 100% accurate for the player shooting. The downside is that it's incredibly weak to lagswitches and hacking. It's entirely possible for a player to use a third party program to send a "hit" to the host without seeing a player or even firing your gun. Any player would be capable of using a lagswitch to its fullest extent.*

*at the moment, only the host can truly utilize a lagswitch because they are the ones sending data to the clients. If you're platinum or higher in league then you've likely seen this in action.

Server Side Hit Authentication is far more complicated. Let's take the following scenario:
[image]

You shoot at the guy on the left, because that's what you see. However the target is moving to the right. You aim, and shoot. Your console/PC sends your position, direction, and the fact that you shot to the server. Now lets say that you have a latency of something nuts like 200 ms. By the time that your command reaches the host/server, the target has moved to the spot on the right. But if the game utilizes the data exactly as you sent it, then it would register as a miss because there's no player there now. This is where Lag Compensation comes into play. Lag compensation effectively "rewinds time." It digs through its memory for a game state that matches the client's information and implements it under those conditions. This accounts for latency, interpolation, and anything else that creates a time delay that the game can manage to quantify. The benefits of Server side lag compensation are that it is virtually immune to things such as lagswitches and various hacks (however things such as god mode hacks and aimbotting would still work). The downside of course is that it's flat out not perfect. Modern day lag compensation is very accurate for what it's worth, but CoD sends data from each client at 30 states a second all the while running at close (or more in the PC version's case) to 60 FPS on each client. Small precision errors can still occur and have very unfavorable results.

It is fairly safe to assume that CoD uses either the above rewind-time system, or calculate player positions using sequence numbers. Sequence numbers are mainly used to keep packets in order, due to a flaw in UDP which can cause them to arrive scrambled. In terms of using them for synchronization, however, the host will create a snapshot 20 times a second and stamp a number on it (AKA "sequence Number"). That is sent out to every player, interpolated after a few, and used to generate their world. When your client sends out information back (done 30 times a second) it will put a sequence number on its own packet that matches the one used to generate the world. When the host/server receives this, then it will compare the sequence number on the packet received to a matching one in memory (which would obviously have everyone in the same locations accurately). This system is accurate as far as confirming hits goes, however it is obviously vulnerable to packet loss. if the packet being sent contains information of a hit, and is lost along the way, then there will inevitably be a delay before that information is re-sent.

On the server side, hit detection is accurate and lenient. Rest assured that if you shoot someone, then it will register as a hit. There are two exceptions to this rule, however. If the host receives information at any time that a player has been killed, then any more data it receives from that presumably dead player will not be sent to the other clients. Of course, due to latency, the server will realize that you are dead before you do. And if you were shooting someone, you are sending that information to the host. You can continue sending that information until that you receive notice from the host that you are, in fact, dead. This means that you can effectively tell the server that you have shot the enemy after the server knows that you've been killed. In order to stifle the inevitable BS that would come of that, the server will cut off all input that it receives from you until you respawn again. If someone plays halo online then they're probably familiar with two players killing each other simultaneously. However do to the quick-dying nature of cod, this would happen in nearly every head on encounter. This will be visualized later in 3.2. The second exception to the rule involves packet loss, which will be discussed in 2.5.

[2.4] Interpolation and Artificial Delays
One thing many players will notice when looking closer at connection issues is that players have artificial delays applied to them.*This is caused by interpolation. Interpolation stores snapshots and renders them a split second later in order to keep movement fluid. Take a look at the following graph:

[image]

The line represents the timeline of the game, with each segment depicting the time delay between snapshots. It is important to know that Real Time (Server), Real time (Client), and Current Rendering Time are all occurring simultaneously, but are all at different spots on the game's timeline. Starting from the right the server sends out a snapshot. As we know, there is a delay between when it is sent and when it is received by the client. When the client receives the snapshot, it stores it in memory. It does not render the snapshot instantly. More specifically it does not render that snapshot until it has another snapshot to compare it to. However then we have to remember that we are using UDP to transfer data. If we are only using the past two snapshots, then any packet loss whatsoever would cause choppy movement as the game would need to predict where enemies are heading in order to maintain a moving picture. Thus it is standard to have interpolation span at least three snapshots, or a 100ms "lerp" it is often called. The server sends data to the clients at about about 20 snapshots/second (and 30 packets/second from client to server), which means this creates an artificial delay of roughly 100 ms.

There is another artificial delay added to the host. Since CoD4 there has always been a (reported) 20-40ms artificial delay added to the host and clients*. If 51% of the clients have a ping higher than 110ms, then the average ping of all players will be added to the host.* Robert Bowling said that this was changed so that the host's latency was equal to that of the next lowest latency player, so take that as you will.

*going off toysrme's word here and don't have any variables/dvars/values for that. However testing in CoD4 showed this to be true.

There's another mechanic called extrapolation which predicts how the game will flow in a situation where too many snapshots were missed in a row to render a fluid scene. This is much less reliable for fluid movement and is rarely used for more than a fraction of a second in any game (if you have to extrapolate for over 250 ms then your connection's out of whack and there's no point).

[2.5] Packet Loss
Since a real time shooter like CoD is forced to use UDP, it is inherantly prone to packet loss. Now, as said earlier, data is sent from the server to the client 20 times each second and 30 times a second from client to server. Due to interpolation, missing one of these packets won't cause issues when rendering your in-game world. However, issues arrive when the exact packet containing information of a hit is dropped.

Now as said in 1.2, in order to compensate for potential packet loss, each packet sent contains an "ACK" or acknowledgement. Upon recieving information, the client or server will send out a response to the ACK to confirm that the information reached them. If the ACK is not responded to within a certain period of time, then the important information from that lost packet is added onto the new one. While this system does a good job of making sure missing information goes through, it is unfortunately not very fast. It will take at least the length of one's round trip latency before the client/server knows that a packet did not get through, and in most shooters, that is often too late.

While it is certainly possible for data to get lost on the way to its destination, bandwith can be a major factor in packet loss (and is also the only factor that you can do anything about). When there is not enough room for an incoming packet to be stored or transmitted, that packet will be dropped. While CoD doesn't use too much bandwith, having multiple appliances on the same internet connection can ovwerwhelm and stifle connection from your videogame, especially if those applications primarily use a TCP connection.

[3.0] How does this come into play?

[3.1] Connection Discrepancies pt.1
Input prediction and lag will cause players to be out of sync with each other. More specifically, each client will see the other players significantly behind themselves. The difference will basically be Time it takes for the data to reach the server + Time taken from snapshot to reach another client + The time delay caused by interpolation. This stacks up to make a pretty big difference. When mixed with the fact that hit detection is designed to work properly from the shooter's perspective, this causes some wacky effects. The first major one comes from coming in and out of cover. In both these pictures: You are Red (your perspective), the enemy is Blue (his perspective), and the place where you see the enemy is on your end is a blue shadow.

Running into cover
[image]

In this situation, we have an enemy who is running away from you as you are shooting him. On his end, he has turned the corner, safe from your view. However, due to lag, the last snapshot to be rendered on your system was when he was a split second behind. due to the fact that you can act instantly and that hit detection is client side, your shots will register shooting him even though in real time on his client, he is out of your view. If you've been on the bad end of this (and you almost certainly have) you'd notice that you can actually travel a fair distance behind cover. This isn't as "bullshit" as it seems simply because for half of this time, you were already dead, your client just hadn't gotten word of it and thus input prediction allowed you to move because as far as it was concerned, you were still alive.* In actuality the difference is more reasonable and it just looks worse because the information had to get back to you.

It's important to note that this is simply dependent on a connection discrepancy. It doesn't matter who has the better connection on either side because the latencies of the players involved stack together. You do need to acknowledge the fact that in CoD, if either you or the opponent is lagging, then they have a window of opportunity after you take cover to kill you.

*it ends up being the time to send your location at time of death to server + latency between server and client + interpolation + sending it back to server + sending it back to you. Long time. Very silly. Looks weird. will visualize in 3.2

Coming out from cover
[image]

In this scenario, you are camping. Enemy comes around the corner and starts shooting you. On your end of the spectrum, he hasn't come around the corner yet. Basically, he sees you before you see him simply because he is moving into the room and you're already there. Once again, hit detection favors the attacker in this engagement; and once again, the significance is a result of the two players' combined latencies. When playing, especially on a poor connection, it's important to remember that you can manipulate this fault in networking to your advantage. However it's not consistent or reliable so it's not some be-all end-all trick either.

[3.2] Connection Discrepancies pt.2
Now I'm going to show what happens in a head on engagement, not involving cover. Let's assume that me, aidsaidsaids, and kirbyderby are all playing a free for all match; and for the sake of this, we're going to assume that there is no interpolation and that the following values are realistic (interpolation would obviously be present, but it would add more frames to the scenario and the point gets across without it).
[image]

Alright, so Kirb is the Host. Aids has a latency of 100ms and Mousey has a latency of 200ms. For all practical purposes this is one way latency. Review the following silly drawing:
[image]

In this, Mousey and Aids have come across one another. Mousey has started to attack aids a little earlier than vice versa, and the server has recognized this.

[image]

In this you can see that Aids and Kirb and responding fairly quickly to one another. The host has recognized that Aids started to aim and aids has acknowledged Mousey beginning to knife.

[image]

Now let's assume that both Mousey and Aids killed one another simultaneously in real time. On both of their screens they have gotten a killing blow, but neither of that information has reached the host yet, so they will still be seeing (and executing commands) that they receive from the other players until the host has acknowledged this. Input prediction does not predict another player's death (obviously) so the server must confirm it. Also, neither players would receive a hitmarker on these hits until the server confirms it; Mousey would hear the sound of the knife stabbing, however.

[image]

Kirb receives the information from Aids saying that Mousey is dead. His system would immediately stop sending any information it receives from Mousey (including the upcoming knife) until she respawns. Neither Mouse nor Aids has received this confirmation that Mousey is dead and thus they are still alive on each other's clients.

[image]

Aids receives information that Mousey is dead and he stops shooting. Kirb is still receiving information from Aids that he is shooting (as he was until the death was confirmed). Mousey is just now receiving information that aids is shooting, which looks silly and weird after he has been knifed.

[image]

Mousey now receives the info that Aids has killed her. She immediately warps back to the place of death as it was on the server. The death would have seemed instantaneous and silly. If she had been shooting, then there would have been a period of where it appeared that bullets were hitting Aids but without hitmarkers to confirm them, simply because of how significant the delay is. The host would stop confirming that information the moment it acknowledges someone having killed her. Mousey would also have never received a hitmarker from the knife, as the host would never have confirmed the hit. Being on the bad end of a laggy connection will give you a serious disadvantage in all head on fights (but I'm sure you already knew that

).

[3.3] Killcams
Alright, so we saw that little frame by frame silliness that would show how it would appear from each player's perspective. Now let's see that in motion.

[image]

*this is probably how choppy your game would look if you didn't have interpolation

The killcam that Mousey would see would be from the host's perspective of what happened. You may notice that while it doesn't seem like much of a laggy mess as Mousey's perspective, it seems fairly quick for what it's worth because it doesn't have the delay that aids really saw due to latency. Killcams also do not show precise readings of where people shot or were looking at. They are shown at most 20 states per second and thus are being rendered on your client on a fraction of the information present from the shooter's perspective. Any video you see that is using killcams as an example for anything is worthless information (unless of course, they are trying to show that killcams are inaccurate).

[4.0] Matchmaking
[4.1] Sorting players
The matchmaking and hosting systems are the two networking elements that IW and Treyarch has actually put some serious effort into making better. As far as finding games, it's supposedly been really simple in the past (starting with mw2, when it comes to cod4 nobody knows how the hell it decided hosts and such).

Starting in MW2, a client searches for available games that reveal a ping of under 50ms. Your system then searches those games and deems if you're suitable to join or not (through whatever criteria are in place). If no suitable games were found, then it would increase the threshold by 10ms and search again. It has a cap so that you'll never be put into a game that reads 800ms, but that's pretty high up there. It seems to work this way up through MW3 but I'm unsure.

Not too long ago, Activision released an article on how public matchmaking puts players into games. The system basically boils down to:

1. Find "suitable" games within a certain proximity
2. Eliminate games that are outside the player's skill bracket
3. Choose the one with the lowest ping.

According to the article, the game puts a lower priority in getting you into a game with the best connection than previous titles did. Take that as you will (or read the article at least).

Black Ops 2 includes search preferences as well. I do not know what the specifics of each option are (though "Best," "Normal," and "Any" are pretty straightforward) Vond has mentioned in a tweet that sorting by "best" places an upper cap on what the matchmaking system will find to be an acceptable latency for you (though the context tweet no longer exists).

[4.2] Hosts and Migrations
The hosting system is the other thing that the devs actually put some effort into regarding networking.

According to posts by toysrme (the default values for many variables are present in these), CoD4 and World at War use an unknown system to determine host. Since then, the systems works as such:

Cod4 and onward:
The host will constantly be pinging its clients. A player is "unhappy" if their ping shows to be above 400ms. In order for a host to change, at least three players must be in a game, and more than 51% of the clients need to show that they need to be unhappy. If this yields true for 300 network frames (at 20 snapshots/second this means for 15 seconds), then the game will be dropped (Cod4/W@W) or the host will be migrated* (MW2 and onward).

*if someone is lagswitching and a migration occurs, then they suck at lagswitching

MW2:
MW2 introduced host migrations. The first host is chosen with a bandwidth race (see toys's post for specifics). This is done every time the host changes, which is done every time the old host leaves, a lobby merges, or if the host is not "suitable" for the game. Any time that the game would be dropped in CoD4, MW2 forces a host migration. If a migration takes longer than 40 seconds, the game is ended.

Black Ops:
Black Ops is nearly the same as MW2, however it runs the bandwidth test every time you sign into matchmaking to save time.

Could not find anything on MW3 or BO2. Feel free to shed some light if you know.

It's important to have realistic expectations. CoD runs on an old engine with network rates that became obsolete a decade ago. People die quickly. Lag is erratic and unreliable. She'll tell you she loves you and then kick your dog. It will help you and it will hurt you. It's gonna be there and there is nothing you can do to change that. Of course there are things you can do to mitigate connection issues, and it's particularly easy in the earlier PC versions, but that's a whole different topic. I'm not gonna tell you how to build a lagswitch or anything either. You're all big girls, you can figure that one out.

EDIT: Thread with commentary from an ex-developer on the subject

« Last Edit: May 6, 2013, 4:55pm by Mousey »