Networked Physics

As my specialization project I chose to make a small demo where people can join a server, control a rigid body and bounce into each other, all perfectly synchronized.

I wanted to accomplish this using as little bandwidth as possible.

I had previously written both the graphics and physics engine used in this project.

Results

A client will handle the following traffic:

about 3 kB to sync everything at join
24 bytes per input-change made by other clients
48 bytes per input-change made by itself

Apart from the occasional ping, that's it.

In a real world scenario where everyone is moving around, a client will handle about 120 B/s per user.

How Its Made

Rollback - The theory

Since I wanted to keep the bandwidth usage on the low side I chose to go with rollback.

So what is rollback? It is a system where you continuously save the games state in a buffer containing the games past. This means that, if a client receives an input that happened a couple of frames ago, it simply rolls back the simulation to the frame of the new input, applies it, and re-simulates up to current frame.

In order for this to work your game, or in my case physics, needs to be deterministic. If you begin from a certain state, the game has to play out the same way every time.

Transform, momentum and angular momentum (the state of the game) are only synced at join. Inputs, that break the deterministic nature of the game, are the only things that needs to be synchronized thereafter.

Rollback - In practice

The first step to implementing rollback is making your game deterministic. Allthough programs are deterministic by nature my program wasn't due to different delta times yielding different results. Simulating one frame with one second of delta time did not give the same result as simulating two frames with half a second of delta time each. I solved this by fixing my timestep.

From:

To:

This worked like a charm and the physics played out exactly the same way every time I ran the program.

Next up is to make a buffer containing information about previous ticks. All relevant data for every rigid body is gathered in a container called a snapshot. Now I couldn't just save every tick ever simulated or I would eventually run out of memory. No, when the end of the buffer is reached I'll simply start from the beginning again and overwrite the old data. 2 seconds worth of backtracking should be enough and since I'm running the program at a fixed 200 fps the buffer was given a size of 400.

The current state of all rigid bodies will be written to this buffer every time a tick is simulated.

Now, what happens if I receive an input over the network that occurred on a tick that's already been simulated? Well the program will have to know that its supposed to rollback before the next simulation.

And when its time to simulate its checks if the past has been altered.

The function "SimulateOneTick" takes the tick it's supposed to simulate as an argument in order to know what user inputs to apply.

Now obviously there was a bunch of problems I had to solve making this work properly but that's the gist of it. As long as all inputs are synced within the 2 second buffer, the simulation will play out the same for every user.

Problems encountered

NATs and ports

I came into this project no real understanding of how messages navigated the internet, but, I had made a small UDP based network class earlier. It used two sockets. One for sending and one for receiving. This worked just fine testing on a local network but when I began testing this project over the internet I ran into trouble.

At first nothing would happen. I then realized that my servers router had no way of knowing which computer to send the clients handshake message to. This answered an old question for me, namely, 'why do I have to port forward this stupid game?' It suddenly made a lot of sense. After having port forwarded my servers listening port, and its router knew which computer to redirect messages designated to that port, I had some success. The server would now receive the clients handshake but the client never received a response. This was a quite obscure problem for me and I spend several hours searching the web for answers. I came across things like hole punching and read about NATs and PATs, but the more I read the more It seemed that my solution should simply work. The server can receive messages since I port forwarded and the client was apparently temporarily port forwarded automatically when it sent a message. If the client was behind a PAT it would be forwarded there as well, the message would have a different port coming out of the PAT but that didn't matter since the server sends its response to the port of the received message, not the clients actual local port. Well. I then remembered that the server didn't respond to the port of the received message. Since I used two sockets, it created another address to respond to, copying the address of the received message but overwriting its port, using a port number included in the handshake instead. When the server sent a message to this address it had created, the NATs and PATs would not know what to do with it. I then removed one of the sockets and used a singel one to send and receive from and it simply worked.

This was an ascending experience for me and I came out on the other side feeling like some network guru. I obviously only scratched the surface here but I gained a new understanding of how the internet works, when things like hole punching is necessary and how I would go about creating it.