How to shoot a shooter

[ Armin Ronacher article on the principles for calculating collisions in online shooters. It is more likely a review and research than a technical one. Here and hereafter, in brackets, the translator’s note ]

Today I want to look out of my window and share my knowledge on a very complex topic, in which I literally did not understand a couple of months ago. What for? Well, it seems to me that it is just great to understand this. And it can also give someone a reason to dive into this topic.
')
And yet - despite all my research, I did not find out enough to clearly understand the mechanics of very dynamic games, like Battlefield, so I don’t express any claims to being the ultimate truth. And yet, a lot of it was really difficult to dig out.

A bit of context

I have to admit, after Bad Company 2 came out and, now, Battlefield 3, I let down a horrendous amount of time on this series. And whenever I realize that I spend time on useless nonsense, I try to get at least something from this nonsense that I could use in the future.

And it’s very cool that DICE developers are active and available on the forums, on Twitter and reddit, and you can always get a lot of information about how it was all developed. In addition, these games are quite popular and many people try to sort through executable files in order to see what is done there and what is bad.

As for Battlefield, I wondered how the network part worked. Mainly due to the fact that this game does one thing completely differently than all of what I have played before - every bullet fired here has acceleration and is completely subject to the effects of gravity. Of course, the concept of shells is not new in itself, but a very rare game tries to introduce compensation for response time for projectiles. Actually, I can’t remember a single game other than Bad Company 2 and Battlefield 3 that would do it, but it may very well be the lack of my knowledge in this area.

Fucking physics.

Problem number one - the speed of information transfer. Our theoretical limit is, of course, the speed of light, but the actual limit is much lower. To transmit the signal, we use copper and fibers, and above them stands our network equipment and probably something else. And all this, of course, adds to the delay.

There are three ways to get out of this situation. The first is that your game will be played only over a local (local) network, where delays are negligible, the second is that you can simply ignore this problem and allow players to deal with their “lags” on their own. The third solution is to use some tricky tricks to compensate for the delay.

Of course, the response time has greatly decreased lately, however, we are now approaching purely physical constraints, but the problem still has not gone away. After all, we are now interacting with people all over the world, despite the fact that earlier we were more isolated.

So everything that the games do is actually just tricks that make the players believe that there are no lags. For most games, you will not even notice a delay of 150 ms (after all, this is nothing compared to the total time spent in the game). Perhaps you will feel how performance decreases with an increase in response time, but you can only tie this drop in performance to network delays if you have some experience.

The basics

Modern network shooters (as a rule) consist of two parts. From the client and server. The host models the game with a hard-coded speed (for example, 20 recalculations of the game situation per second) and informs all clients that changes have occurred on the server, sending them updates to the game world at a hard-coded update rate. And the client simply receives this information and draws on the screen everything that happens on the server.

If the server recounts the game situation only 20 times per second, then the simplest solution would be to tie the client to the same 20 hertz. Well, if you suddenly need to somehow raise the FPS, they usually resort to interpolation.

Suppose a server is running at 20 hertz and a packet is sent to the client for each recalculation. And the client needs to render three frames for each incoming packet. The whole thing with interpolation is that it can operate only with already existing data. So assuming the client has 60 hertz, we get about 16 milliseconds per frame, and if the client interpolates the situation between server recalculations, then with each packet we will have 48 ms of the elapsed time for interpolation.

[I understand it means that during interpolation there is a post-processing. A packet arrives and on its basis three frames that are actually past are being built, i.e. in the example above, ALWAYS there will be a lag in those 48 ms.]

The theoretical alternative is an extrapolation from the current (known) point to the future, but it is highly conducive to the appearance of errors and much more difficult to develop than ordinary linear interpolation.

With all this, we have an excellent basis for modeling the repetitive movements of other players. But what to do with a local player? If a local player wants to start moving, then sends his intentions to the server and waits until his team at the beginning of movement (confirmed) comes back, before actually starting to move, there will be a very big lag. The solution to this is a kind of "predictiveness" on the client side. In computer games, the term Dead Reckoning is often referred to as this concept. In a static world, where there is nothing but the changes of the player himself, it is safe to say that the client can simply ignore the server to calculate their own movements and imitate the beginning of the movement at the very moment when the key was pressed.

And if the simulation on the client and server ceases to match, you will receive artifacts, such as player’s short teleportation. Why can it stop coinciding? This usually happens when something happens to a player (on the server) that the client simply could not predict. For example, a player may encounter another player. Or stand on top of a vehicle that is not controlled by him.

Time Machine.

The above basic methods are well suited for games like Quake or Counter-Strike, where only players and rockets are dynamic. If the client predicts something wrong, the server will simply continue to send out new information about the players' positions. And if the client notices that the data from the server is too much at variance with his own predictions, he simply makes minor adjustments.

And if, from the point of view of the current simulation, the data coming from the server will be from the past, the game will simply roll back the changes. It usually stores the last few messages from the server in a local buffer, so the game can only find the message that is closest to the received data, roll back the simulation and apply the current update to the already adjusted state.

They got me?

Everything is clear with movements, but with shooting so far not at all. In Quakeworld, for example, delays in the movement of players were remarkably compensated for by “predictability”, but the player had to shoot ahead of the curve in order to compensate for the delay on shooting. Look - if the shooter has a 100 millisecond lag and he wants to shoot at another player moving at a speed of 100 conventional units per second, the player must aim at a point on the ground ten conditional units before running, in order to get into it. Annoying.

If you are playing a modern shooter, this is no longer a problem. So how does it work? In principle - almost the same. In order to determine that the player hit something with a shot, the client sends to the server the very goal and intention of the player to shoot. The server considers the time difference, “returns to the past” for the already counted time and checks whether the shooter has fallen into anything. If hit, then damage is “applied” to the target.

However, this method has two “buts”. First of all, this method works only with infinitely fast weapons (hitscan), because in this case it is not really created and does not begin to plow time and space, in fact, a bullet. The second but - if the shooter had a lag of, say, 200 milliseconds, then the person who was supposed to get this shot, could well have run for cover during those 200 milliseconds. And due to the fact that the shooter, as it were, shoots from the future into the past, who has already run in, the player suddenly dies for cover, because at the time of the shot the arrow was clearly visible.

You cannot get rid of the lag; you can only move it to some other place. And modern games decided to take advantage of this mantra and give shooters the opportunity not to feel the consequences of lag at all. But this illusion of an absolutely synchronous game, of course, is falling apart into pieces as soon as something extraordinary happens (players from different “times” run together, or someone gets a bullet while being in hiding, etc.).

Real bullets.

The first problem of Battlefield is that it creates bullets. About 16 players participate in Quake and other games in the match. Every time you try to find out if someone got a bullet, the server simply returns all players to the correct (in terms of client delay) positions, interpolates time and observes if someone got the bullet or not. Even with a very "multi-bullet" weapon, this does not create any special problems, especially if you can cheat a little and stuff a few bullets into one network packet. Of course, there used to be games that exchanged good old hitscan for projectiles, but they did not introduce any compensation for the delay and made projectiles relatively slow. And this made it very difficult to play with a large ping. Try to play Team Fortress 2 with a medical cannon on a far-away server with a big ping. Let's see how you will succeed =).

However, in Battlefield, shooting, you create these bullets. The life of each bullet is about 1.5 seconds, and for a bullet fired from a sniper rifle - as much as five seconds. Considering that most of the weapons are assault rifles, we get about 700 rounds per minute with a very large number of possible misses. Moreover: the cards here are so huge that most of the bullets will fly the entire period allotted to them (and this, as we remember, 1.5 seconds) before they are removed from the scene. And the most terrible thing is that with all this you have to deal with a maximum of 64 players and a bunch of military equipment.
This is a huge number of dynamic objects, each step of each of which must be checked for collision with anything. And with each such check, the game needs to move everything back in time to the own time of each checked bullet, which was recorded as the shot time. And this is every step of the simulation. Not only when shots.

Technique and destructible.

Another big battlefield issue - destructible environments are part of game design. Buildings and equipment here can receive damage, as well as players. And if, in order to check whether something was “shot”, you need to travel in time, then you need to move back not only the players, but all the equipment and all the buildings from the battlefield. True, I do not think that the same should be done for the destruction of [ buildings ], because the destruction does not create new obstacles for bullets. Crushed stone can be easily shot through, and if a new obstacle suddenly appears as a result of destruction, it will most likely not be noticed due to the smoke caused by this destruction.

Another thing - the destruction of the earth. In this game you can make real holes in the ground. And the real holes that appear unexpectedly on the field have a very destructive effect on any kind of prediction or interpolation. You can recall the tons of players who sent reports about the soldiers who fell under the map during the beta test of Battlefield 3. There is nothing surprising in the significant "softening" of the destructible land in the game for release.

We stretch the protocol.

64 players on the battlefield, dozens of pieces of equipment, tons of destruction, missiles, bullets, weapons, shooting in different directions and the devil knows what else - a huge amount of data to transmit. However, if you suddenly look at the traffic generated by Battlefield 3, you will see that it is not so high. I believe that it uses something similar to the network model used in Halo, which, in turn, is based on the Tribes model. Halo added to it such a thing as different degrees of priorities for all objects transmitted over the network. Objects that are far from the player are updated (on the client) much less frequently than objects near.

On my computer when playing on a server with 64 players, the game transmits about 16kb / s in both directions. And this is quite a bit.

Halo's ragdoll trick

There are a lot of physical objects on the battlefield and I do not think that all of them are transmitted over the network. For example, in most cases a ragdoll will occupy a channel only at the stage of initial synchronization of physics between customers, and these are trifles. You can shoot through dead bodies anyway, so the biggest problem is no longer a problem. But there is another problem - Battlefield allows you to revive fallen comrades.
Here is one example. Some people do not quite honestly use the mechanism of rebirth. At least if the truth is written down.

According to information from some sites (even if they remain unnamed), the position of the player after revival is controlled by reviving. This, in general, makes sense, because the person being animated in any case does not know where his body is and what is happening to him, because when he died, the camera began to show him completely different things. And from the point of view of the animating, it would be strange to see how a just lively man suddenly resurrected in some other place (read: where he died), and not where he was animated.

But regardless of whether or not the Battlefield Ragdoll is broadcasting over the network, this is simply a private and interesting case of how game design can affect a network message and how a network message can affect game design. This method definitely works great in Halo, where bodies serve no purpose, unlike Battlefield, where they can be revived.

Collision Detection in Battlefield 3

So in Battlefield 3 there are real bullets and these bullets have a correctly compensated response time. If you see yourself falling into something, you really fall into it. What is even more interesting is getting very close to pixel perfect. It is difficult to say for sure, because even the first shot does not give 100% accuracy. But it seems damn close.

The fact is that the definition of collisions in Battlefield 3 deals with the client, not the server. Almost like ZeroPing mod for UT99. If we take into account the difficulties created by all the guns in Battlefield 3, then all this makes sense. The advantages of client-side collision detection are obvious: cheap, 100% accurate, automatic delay compensation for nothing. However, these advantages come with a big disadvantage. Such a recount is easy to fool.

According to Alan Curtz, DICE compensates for the consequences of collision detection by the client by performing a simple check on the server, which clearly responds to whether there could be a “reported” collision or not. I suppose they are really doing something, since the video with the "card killings" ceased to appear immediately after the end of beta testing. Yes, and the main problem on the PC is the eymots and ESP hacks, so I’m not at all sure if there is a serious security loss in practice, not in words.

How can you make sure that the collision was in fact? You can create a cone that diverges from the player. Since you have gravity, a cone is not an ideal solution, but it is close enough to.

[apparently the author had in mind - and check - whether the target falls into this cone]

We write our own network game

What do you need to know in order to write your online game? There are several useful things on the Internet that will help you play around with it.
- Glenn Fiedler game development articles at Networking for Game Programmers and Networked Game Physics
- On Gamasutra there is an article from 1997 about Dead Reckoning. She is a great introduction.
- Quake engine code review from Fabien Sanglard covers the predictive and network parts. In general, the Quake engine is a great place to start.
- Valve's developer wiki is a terrific information resource. There are articles about delay compensation, predictions, interpolation and a very useful article by Yahn Bernier about the network part of the game engine, among others.
- Presentation of “ I shot you first ” in the GDC repository
- Presentation of Ben Garney's Robust Efficient Networking .

This is all that I managed to see. And I am sure that there is a lot of literature on this topic, but so far I can not recommend anything.

[ Translation published with permission of the author. Mistakes found, problems with punctuation and translation flaws, please send to lichku ]