Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 02/21/18 01:26 AM

    The Poor Man's Netcode

    Networking and Multiplayer

    evanofsky

    The more you know about a given topic, the more you realize that no one knows anything.

    For some reason (why God, why?) my topic of choice is game development. Everyone in that field agrees: don't add networked multiplayer to an existing game, you drunken clown.

    Well, I did it anyway because I hate myself. Somehow it turned out great. None of us know anything.

    Problem #1: assets

    My first question was: how do I tell a client to use such-and-such mesh to render an object? Serialize the whole mesh? Nah, they already have it on disk. Send its filename? Nah, that's inefficient and insecure. Okay, just a string identifier then?

    Fortunately, before I had time to implement any of my own terrible ideas, I watched a talk from Mike Acton where he mentions the danger of "lazy decision-making". One of his points was: strings let you lazily ignore decisions until runtime, when it's too late to fix.

    If I rename a texture, I don't want to get a bug report from a player with a screenshot like this:

    https://i.imgur.com/TppRYdOl.jpg

    I had never thought about how powerful and complex strings are. Half the field of computer science deals with strings and what they can do. They usually require a heap allocation, or something even more complex like ropes and interning. I usually don't bother to limit their length, so a single string expands the possibility space to infinity, destroying whatever limited ability I had to predict runtime behavior.

    And here I am using these complex beasts to identify objects. Heck, I've even used strings to access object properties. What madness!

    Long story short, I cultivated a firm conviction to avoid strings where possible. I wrote a pre-processor that outputs header files like this at build time:

    namespace Asset
    {
        namespace Mesh
        {
            const int count = 3;
            const AssetID player = 0;
            const AssetID enemy = 1;
            const AssetID projectile = 2;
        }
    }

    So I can reference meshes like this:

    renderer->mesh = Asset::Mesh::player;

    If I rename a mesh, the compiler makes it my problem instead of some poor player's problem. That's good!

    The bad news is, I still have to interact with the file system, which requires the use of strings. The good news is the pre-processor can save the day.

    const char* Asset::Mesh::filenames[] =
    {
        "assets/player.msh",
        "assets/enemy.msh",
        "assets/projectile.msh",
        0,
    };

    With all this in place, I can easily send assets across the network. They're just numbers! I can even verify them.

    if (mesh < 0 || mesh >= Asset::Mesh::count)
        net_error(); // just what are you trying to pull, buddy?

    Problem #2: object references

    My next question was: how do I tell a client to please move/delete/frobnicate "that one object from before, you know the one". Once again, I was lucky enough to hear from smart people before I could shoot myself in the foot.

    From the start, I knew I needed a bunch of lists of different kinds of objects, like this:

    Array<Turret> Turret::list;
    Array<Projectile> Projectile::list;
    Array<Avatar> Avatar::list;

    Let's say I want to reference the first object in the Avatar list, even without networking, just on our local machine. My first idea is to just use a pointer:
     

    Avatar* avatar;
    
    avatar = &Avatar::list[0];

    This introduces a ton of non-obvious problems. First, I'm compiling for a 64 bit architecture, which means that pointer takes up 8 whole bytes of memory, even though most of it is probably zeroes. And memory is the number one performance bottleneck in games.

    Second, if I add enough objects to the array, it will get reallocated to a different place in memory, and the pointer will point to garbage.

    Okay, fine. I'll use an ID instead.

    template<typename Type> struct Ref
    {
        short id;
        inline Type* ref()
        {
            return &Type::list[id];
        }
    
        // overloaded "=" operator omitted
    };
    
    Ref<Avatar> avatar = &Avatar::list[0];
    
    avatar.ref()->frobnicate();

    Second problem: if I remove that Avatar from the list, some other Avatar will get moved into its place without me knowing. The program will continue, blissfully and silently screwing things up, until some player sends a bug report that the game is "acting weird". I much prefer the program to explode instantly so I at least get a crash dump with a line number.

    Okay, fine. Instead of actually removing the avatar, I'll put a revision number on it:

    struct Avatar
    {
        short revision;
    };
    
    template<typename Type> struct Ref
    {
        short id;
        short revision;
        inline Type* ref()
        {
            Type* t = &Type::list[id];
            return t->revision == revision ? t : nullptr;
        }
    };

    Instead of actually deleting the avatar, I'll mark it dead and increment the revision number. Now anything trying to access it will give a null pointer exception. And serializing a reference across the network is just a matter of sending two easily verifiable numbers.

    Problem #3: delta compression

    If I had to cut this article down to one line, it would just be a link to Glenn Fiedler's blog.

    Which by the way is here: gafferongames.com

    As I set out to implement my own version of Glenn's netcode, I read this article, which details one of the biggest challenges of multiplayer games. Namely, if you just blast the entire world state across the network 60 times a second, you could gobble up 17 mbps of bandwidth. Per client.

    Delta compression is one of the best ways to cut down bandwidth usage. If a client already knows where an object is, and it hasn't moved, then I don't need to send its position again.

    This can be tricky to get right.

    https://i.imgur.com/e31avw2.gif

    The first part is the trickiest: does the client really know where the object is? Just because I sent the position doesn't mean the client actually received it. The client might send an acknowledgement back that says "hey I received packet #218, but that was 0.5 seconds ago and I haven't gotten anything since."

    So to send a new packet to that client, I have to remember what the world looked like when I sent out packet #218, and delta compress the new packet against that. Another client might have received everything up to packet #224, so I can delta compress the new packet differently for them. Point is, we need to store a whole bunch of separate copies of the entire world.

    Someone on Reddit asked "isn't that a huge memory hog"?

    No, it is not.

    Actually I store 255 world copies in memory. All in a single giant array. Not only that, but each copy has enough room for the maximum number of objects (2048) even if only 2 objects are active.

    If you store an object's state as a position and orientation, that's 7 floats. 3 for XYZ coordinates and 4 for a quaternion. Each float takes 4 bytes. My game supports up to 2048 objects. 7 floats * 4 bytes * 2048 objects * 255 copies = ...

    14 MB. That's like, half of one texture these days.

    I can see myself writing this system five years ago in C#. I would start off immediately worried about memory usage, just like that Redditor, without stopping to think about the actual data involved. I would write some unnecessary, crazy fancy, bug-ridden compression system.

    Taking a second to stop and think about actual data like this is called Data-Oriented Design. When I talk to people about DOD, many immediately say, "Woah, that's really low-level. I guess you want to wring out every last bit of performance. I don't have time for that. Anyway, my code runs fine." Let's break down the assumptions in this statement.

    Assumption 1: "That's really low-level".

    Look, I multiplied four numbers together. It's not rocket science.

    Assumption 2: "You sacrifice readability and simplicity for performance."

    Let's picture two different solutions to this netcode problem. For clarity, let's pretend we only need 3 world copies, each containing up to 2 objects.

    Here's the solution I just described. Everything is statically allocated in the .bss segment. It never moves around. Everything is the same size. No pointers at all.

    https://i.imgur.com/4tFFSN7.png

    Here's the idiomatic C# solution. Everything is scattered randomly throughout the heap. Things can get reallocated or moved right in the middle of a frame. The array is jagged. 64-bit pointers all over the place.

    https://i.imgur.com/lRVCA0q.png

    Which is simpler?

    The second diagram is actually far from exhaustive. C#-land is a lot more complex in reality. Check the comments and you'll probably find someone correcting me about how C# actually works.

    But that's my point. With my solution, I can easily construct a "good enough" mental model to understand what's actually happening on the machine. I've barely scratched the surface with the C# solution. I have no idea how it will behave at runtime.

    Assumption 3: "Performance is the only reason you would code like this."

    To me, performance is a nice side benefit of data-oriented design. The main benefit is clarity of thought. Five years ago, when I sat down to solve a problem, my first thought was not about the problem itself, but how to shoehorn it into classes and interfaces.

    I witnessed this analysis paralysis first-hand at a game jam recently. My friend got stuck designing a grid for a 2048-like game. He couldn't figure out if each number was an object, or if each grid cell was an object, or both. I said, "the grid is an array of numbers. Each operation is a function that mutates the grid." Suddenly everything became crystal clear to him.

    Assumption 4: "My code runs fine".

    Again, performance is not the main concern, but it's important. The whole world switched from Firefox to Chrome because of it.

    Try this experiment: open up calc.exe. Now copy a 100 MB file from one folder to another.

    https://i.imgur.com/G6xbn52.png

    I don't know what calc.exe is doing during that 300ms eternity, but you can draw your own conclusions from my two minutes of research: calc.exe actually launches a process called Calculator.exe, and one of the command line arguments is called "-ServerName".

    Does calc.exe "run fine"? Did throwing a server in simplify things at all, or is it just slower and more complex?

    I don't want to get side-tracked. The point is, I want to think about the actual problem and the data involved, not about classes and interfaces. Most of the arguments against this mindset amount to "it's different than what I know".

    Problem #4: lag

    I now hand-wave us through to the part of the story where the netcode is somewhat operational.

    Right off the bat I ran into problems dealing with network lag. Games need to respond to players immediately, even if it takes 150ms to get a packet from the server. Projectiles were particularly useless under laggy network conditions. They were impossible to aim.

    I decided to re-use those 14 MB of world copies. When the server receives a command to fire a projectile, it steps the world back 150ms to the way the world appeared to the player when they hit the fire button. Then it simulates the projectile and steps the world forward until it's up to date with the present. That's where it creates the projectile.

    I ended up having the client create a fake projectile immediately, then as soon as it hears back from the server that the projectile was created, it deletes the fake and replaces it with the real thing. If all goes well, they should be in the same place due to the server's timey-wimey magic.

    Here it is in action. The fake projectile appears immediately but goes right through the wall. The server receives the message and fast-forwards the projectile straight to the part where it hits the wall. 150ms later the client gets the packet and sees the impact particle effect.

    https://i.imgur.com/5jbF8PA.gif

    The problem with netcode is, each mechanic requires a different approach to lag compensation. For example, my game has an "active armor" ability. If players react quick enough, they can reflect damage back at enemies.

    https://i.imgur.com/vfbs0J9.gif

    This breaks down in high lag scenarios. By the time the player sees the projectile hitting their character, the server has already registered the hit 100ms ago. The packet just hasn't made it to the client yet. This means you have to anticipate incoming damage and react long before it hits. Notice in the gif above how early I had to hit the button.

    To correct this, the server implements something I call "damage buffering". Instead of applying damage instantly, the server puts the damage into a buffer for 100ms, or whatever the round-trip time is to the client. At the end of that time, it either applies the damage, or if the player reacted, reflects it back.

    Here it is in action. You can see the 200ms delay between the projectile hitting me and the damage actually being applied.

    https://i.imgur.com/JQ3WgIt.gif

    Here's another example. In my game, players can launch themselves at enemies. Enemies die instantly to perfect shots, but they deflect glancing blows and send you flying like this:

    https://i.imgur.com/oTh4dFj.gif

    Which direction should the player bounce? The client has to simulate the bounce before the server knows about it. The server and client need to agree which direction to bounce or they'll get out of sync, and they have no time to communicate beforehand.

    At first I tried quantizing the collision vector so that there were only six possible directions. This made it more likely that the client and server would choose the same direction, but it didn't guarantee anything.

    Finally I implemented another buffer system. Both client and server, when they detect a hit, enter a "buffer" state where the player sits and waits for the remote host to confirm the hit. To minimize jankiness, the server always defers to the client as to which direction to bounce. If the client never acknowledges the hit, the server acts like nothing happened and continues the player on their original course, fast-forwarding them to make up for the time they sat still waiting for confirmation.

    Problem #5: jitter

    My server sends out packets 60 times per second. What about players whose computers run faster than that? They'll see jittery animation.

    Interpolation is the industry-standard solution. Instead of immediately applying position data received from the server, you buffer it a little bit, then you blend smoothly between whatever data that you have.

    In my previous attempt at networked multiplayer, I tried to have each object keep track of its position data and smooth itself out. I ended up getting confused and it never worked well.

    This time, since I could already easily store the entire world state in a struct, I was able to write just two functions to make it work. One function takes two world states and blends them together. Another function takes a world state and applies it to the game.

    How big should the buffer delay be? I originally used a constant until I watched a video from the Overwatch devs where they mention adaptive interpolation delay. The buffer delay should smooth out not only the framerate from the server, but also any variance in packet delivery time.

    This was an easy win. Clients start out with a short interpolation delay, and any time they're missing a packet to interpolate toward, they increase their "lag score". Once it crosses a certain threshold, they tell the server to switch them to a higher interpolation delay.

    Of course, automated systems like this often act against the user's wishes, so it's important to add switches and knobs to the algorithm!

    https://i.imgur.com/XPrJP0I.gif

    Problem #6: joining servers mid-match

    Wait, I already have a way to serialize the entire game state. What's the hold up?

    Turns out, it takes more than one packet to serialize a fresh game state from scratch. And each packet may take multiple attempts to make it to the client. It may take a few hundred milliseconds to get the full state, and as we've seen already, that's an eternity. If the game is already in progress, that's enough time to send 20 packets' worth of new messages, which the client is not ready to process because it hasn't loaded yet.

    The solution is—you guessed it—another buffer.

    I changed the messaging system to support two separate streams of messages in the same packet. The first stream contains the map data, which is processed as soon as it comes in.

    The second stream is just the usual fire-hose of game messages that come in while the client is loading. The client buffers these messages until it's done loading, then processes them all until it's caught up.

    Problem #7: cross-cutting concerns

    This next part may be the most controversial.

    Remember that bit of gamedev wisdom from the beginning? "don't add networked multiplayer to an existing game"?

    Well, most of the netcode in this game is literally tacked on. It lives in its own 5000-line source file. It reaches into the game, pokes stuff into memory, and the game renders it.

    Just listen a second before stoning me. Is it better to group all network code in one place, or spread it out inside each game object?

    I think both approaches have advantages and disadvantages. In fact, I use both approaches in different parts of the game, for various reasons human and technical.

    But some design paradigms (*cough* OOP) leave no room for you to make this decision. Of course you put the netcode inside the object! Its data is private, so you'll have to write an interface to access it anyway. Might as well put all the smarts in there too.

    Conclusion

    I'm not saying you should write netcode like I do; only that this approach has worked for me so far. Read the code and judge for yourself.

    There is an objectively optimal approach for each use case, although people may disagree on which one it is. You should be free to choose based on actual constraints rather than arbitrary ones set forth by some paradigm.

    Thanks for reading. DECEIVER is launching on Kickstarter soon. Sign up to play the demo here!



      Report Article


    User Feedback


    There are no comments to display.



    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Popular Now

  • Similar Content

    • By dandoherty94
      Hi all,
      I'm looking for a career change as the job that i currently do is neither a passion or something that i really want to be doing for the rest of my life. I would ideally like to begin a career in the gaming industry as like most others i have a strong passion for gaming and all things related. I have been looking into a junior test analyst QA job and was wondering if this is the correct place to start. I'm a dedicated worker so don't mind working my way up and I love being hands on with things. I was wondering if anyone had any advice regarding this or how i can go about gaining experience in this field to give myself the best chance. I'm more than willing to do either weekend work or free work to get my foot in the door so if there is any advice or help anyone could give me that would be great. 
      Thanks for reading,
      Dan 
    • By FedGuard
      Hello all,
       
      I would like to start off with thanking you all for this community. Without fora like these to assist people the already hard journey to making an own game would be exponentially more difficult. Next I would like to apologize for the long post, in advance...
      I am contemplating making a game. There, now that's out of the way, maybe some further details might be handy.
      I am not some youngster (no offence) with dreams of breaking into the industry, I am 38, have a full-time job, a wife, kid and dog so I think I am not even considered indie? However I recently found myself with additional time on my hands and decided I would try my hand at making a game.Why? Well mostly because I would like to contribute something, also because I think I have a project worth making (and of course some extra income wouldn't hurt either to be honest). The first thing I realized was, I have absolutely no relevant skill or experience. Hmm; ok, never mind, we can overcome that, right?
      I have spent a few months "researching",meaning looking at YouTube channels, reading articles and fora. Needless to say, I am more confused now than when I started. I also bought some courses (Blender, Unity, C#) and set out to make my ideas more concrete.
      I quickly discovered, I am definitely not an artist... So I decided, though I do plan to continue learning the art side eventually, I would focus on the design and development phase first. The idea being, if it takes me a year or more solely learning stuff and taking courses without actually working on my game, I would become demoralized and the risk of quitting would increase.
      So I thought I would:
      1: Keep following the courses Unity and C# while starting on the actual game development as the courses and my knowledge progress.
      2: Acquire some artwork to help me get a connection with the game and main character, and have something to helm keep me motivated. (I already did some contacting and realized this will not be cheap...). Also try to have the main character model so I can use it to start testing the initial character and game mechanics. For this I have my first concrete question. I already learned that outsourcing this will easily run up in the high hundreds or thousands of dollars... (lowest offer so far being 220 USD) I am therefore playing with the idea of purchasing https://assetstore.unity.com/packages/3d/animations/medieval-animations-mega-pack-12141 with the intention of then have an artist alter and/or add to the animations (it is for a Roman character so some shield animations are not going to work the same way.). This way I could start  with the basic character mechanics. Is this a good idea, waste of money,...? Any suggestions? I then have a related but separate question. Is it a good idea to buy Playmaker (or some other similar software I haven't yet heard of like RPGAIO), and using this for initial build, then changing/adding code as the need arises?
      3.Get a playable initial level ready as a rough demo and then starting to look for artist for level design and character/prop creation.
      ...
       
      I would really appreciate some input from more experienced people, and especially answers to my questions. Of course any advice is extremely welcome.
    • By Shaarigan
      Hey,
      I'm currently starting next iteration on my engine project and have some points I'm completely fine with and some other points and/or code parts that need refactoring so this is a refactoring step before starting to add new features. As I want my code to be modular to have features optional installed for certain projects while others have to stay out of sight, I designed a framework that starting from a core component or module, spreads features to several project files that are merged together to a single project solution (in Visual Studio) by our tooling.
      This works great for some parts of the code, naming the Crypto or Input module for example but other parts seem to be at the wrong place and need to be moved. Some features are in the core component that may belong into an own module while I feel uncomfortable splitting those parts and determine what stays in core and what should get it's own module. An example is Math stuff. When using the framework to write a game (engine), I need access to algebra like Vector, Quaternion and Matrix objects but when writing some kind of match-making server, I wouldn't need it so put it into an own module with own directory, build script and package description or just stay in core and take the size and ammount of files as a treat in this case?
      What about naimng? When cleaning the folder structure I want to collect some files together that stay seperated currently. This files are foir example basic type definitions, utility macros and parts of my Reflection/RTTI/Meta system (which is intended to get ipartially t's own module as well because I just need it for editor code currently but supports conditional building to some kind of C# like attributes also).
      I already looked at several projects and they seem to don't care that much about that but growing the code means also grow breaking changes when refactoring in the future. So what are your suggestions/ oppinions to this topic? Do I overcomplicate things and overengeneer modularity or could it even be more modular? Where is the line between usefull and chaotic?
      Thanks in advance!
    • By PlanetExp
      I've been trying to organise a small-medium sized toy game project to supports macOS, iOS and Windows simultaneously in a clean way. But I always get stuck when I cross over to the target platform. I'll try to explain,
      I have organised my project in modules like so:
       
      1. core c++ engine, platform agnostic, has a public c++ api
      2. c api bindings for the c++ api, also platform agnostic, this is actually part of 1 because its such a small project
      3. target platform bindings, on iOS and macOS this is in swift. Basically wraps the c api
      4. target platform code. This part just calls the api. Also in swift.
       
      So in all I have 4 modules going simultaneously, all compiled into a separate static libraries and imported into the next phase/layer. Am I even remotely close to something functional? I seem to getting stuck somewhere between 2 and 3 when I cross over to the target platform. In theory I would just need to call the game loop, but I always end up writing some logic up there anyway.
       
    • By trapazza
      A few years ago I started creating a procedural planet engine/renderer for a game in Unity, which after a couple of years I had to stop developing due to lack of time. At the time i didn't know too much about shaders so I did everything on the CPU. Now that I have plenty of time and am more aware of what shaders can do I'd like to resume development with the GPU in mind.
      For the terrain mesh I'm using a cubed-sphere and chunked LODs. The way I calculate heights is rather complex since it's based on a noise tree, where leaf nodes would be noise generators like Simplex, Value, Sine, Voronoi, etc. and branch nodes would be filters and modifiers (FBM, abs, neg, sum, ridged, billow, blender, selectors, etc). To calculate the heights for a mesh you'd call void CalcHeights( Vector3[] meshVertices, out float[] heights ) on the noise's root node, somewhere in a Unity's script. This approach offers a lot of flexibility but also introduces a lot of load in the CPU. The first obvious thing to do would be (I guess) to move all generators to the GPU via compute shaders, then do the same for the rest of the filters. But, depending on the complexity of the noise tree, a single call to CalcHeights could potentially cause dozens of calls back and forth between the CPU and GPU, which I'm not sure it's a good thing.
      How should I go about this?
      Thanks.
       
       
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!