Using a physics engine on the server

You're not using full 3D and are only playing the game on XZ plane so do you really need a full physics implementation?

Can you simply translate the few equations you need into something simpler, bypassing the need for a heavyweight physics library which won't scale as the number of players in your game grows...

@braindigitalis: While 3D physics have a constant factor higher cost in simulation than 2D, the main scalability limitation in simulation is that N actors may potentially interact with N other actors, leading to N-squared scalability. Thus, the end-term scalability is not primarily drive by 2D vs 3D math costs, but by how many object pairs need to interact, and what your broad-phase pair determination algorithm looks like. 3D actually gives more opportunities for culling pairs than 2D, because there are three dimensions instead of two to separate pairs among.
The "constant cost" of simulation in 2D is likely smaller, and thus in absolute numbers on a single, constrained, CPU, you may get more 2D entities than 3D entities, as long as they all have room to spread out reasonably in the world. That's kind-of a special case, though -- not the determining factor of how something "scales."

@sheep19: You probably want to number each game simulation tick. Make sure you use the same, fixed, tick rate on all nodes! The player would then enqueue commands "for the future" for the server. This would include both "spawn bullet" as well as "move" or whatnot. The server applies the appropriate input at the appropriate simulation tick.
You'll then end up with latency, which means that the local client may be displaying tick 100, but the server is currently simulating tick 105, and the data won't get there until tick 110, which in turn won't get back to you until tick 115. (Assuming a 5 tick one-way delay.) This causes a 15 tick delay between "command" and "effect." You can then display the local player in an "accelerated" time frame -- display local player as if the tick was 115, which means all the commands have been applied. The problem then is that you'll see others at a 15 tick delay, which leads to "being shot around a corner" type lag in the experience. That's often better than "taking a long time for controls to affect the player character" kind of lag.

I'm not really equipped to give low-level advice on the topic, but from a higher level, I find it useful to think of the client as a kind of "smart terminal" into the game as the server sees it -- the client is neither the game, nor is it a "dumb terminal" which only sends keystrokes and renders what the server last told it to.

The client is a "smart terminal" because it handles on its own the things that either don't matter for simulation consistency between player clients, or which can be initialized once by the server and then left to run in a way that will remain consistent -- for example, debris/decals/particle effects can fall into either of these categories depending on whether they are purely cosmetic or have an affect on gameplay. Another reason is that the client must make it's best-guess about the current state of the simulation between messages from the server, as a basic example, you might render at 60 frames per second, but you might only get network updates at 10, 15, or 20 times per second (and each of which might have between one-half and several frames of latency by the time you receive it) -- So when a projectile or player is last known to be moving in a given direction, the client has to assume it keeps doing so, but also smoothly interpolate back inline with what the server says to be true when it receives the next relevant message. Similarly, for things like collision detection, the client can know that its impossible to walk through a wall and so should not permit the player to do so while waiting for the server to reprimand it, nor should it even ask the server whether its possible. In short, the client should be smart enough to give its best estimate of what the server will say to be true, based on its imperfect information, and be able to get back in line by smoothly integrating the latest authoritative information from the server.

The client is a "smart terminal" because it handles on its own the things that either don't matter for simulation consistency between player clients, or which can be initialized once by the server and then left to run in a way that will remain consistent

This reminds me of a statement i once read in an internet RFC (request for comments) document:

Be permissive in what you accept, but strict in what you send.

This statement holds true in any protocol including games.

This reminds me of a statement i once read in an internet RFC (request for comments) document:

Quote:
Be permissive in what you accept, but strict in what you send.

This statement holds true in any protocol including games.

Sure -- actually, a good application of that mantra would be something like "Clients and servers should be able to deal with bad data (corrupted, maliciously crafted), and send only good data". For example, when I said earlier that the client shouldn't ask the server to move through a wall, the server should never trust a client not to do so -- lots of hacks for different games involve sending messages to the server that are deliberately misleading -- the server needs to validate what the client attempts to do. On the flip side, non-compromised clients -- and especially the server -- should be very strict about what they send and how its sent (for example, don't just let unused bits/bytes in a message be sent out uninitialized).

[Edited to add] Defending against malicious packets is super important. If you recall the Heartbleed security vulnerability from a couple years ago or so, that was a maliciously-crafted packet where the client requested a response longer than it knew the data to be, and the server simply trusted the client to be honest, though I don't believe it was intentional -- more of a logic bug. Bad idea in any event, this compromised tons of services of all sizes -- webmail, banking, Facebook even, IIRC... I remember changing basically all of my passwords because of it.

Be permissive in what you accept, but strict in what you send.

I have read that too, but I think it is actually wrong.

Because of that approach ("permissive in what you accept,") the HTML language, to this day, 25 years later, has a "tag soup" mode to stay compatible with all kinds of terrible things that "happened to work" on Mosaic version 0.6 or whatever.

"Be strict in what you accept, and stricter in what you send" would be better. And if you're going to go ahead and accept something that's outside of spec, make the user (and developer!) aware that this is going on with something angry and red that can be clicked on to see what's actually wrong, so it can be fixed.

Another anti-pattern: Taking out assertions in release.

The problem is that, if you assert in debug/development/test, then the code doesn't get any further than that.
If you then, in release, suddenly accept that code path, then who knows what will happen? You're executing code in situations it's never seen before.
So, either make it so that assertions don't actually stop the program, just collect all kinds of useful information and report it (somewhere where it will actually be cared about,) or make it so that assertions stop the in release mode, too (typically with a crash dump and program restart.)

Now, if you're running some debug asserts that cut your frame rate in half even when all optimizations are on, that debug code should probably be ifdeffed out for release. Or, more reasonably, only turned on with some kind of runtime flag that defaults to off, even in development, but is turned on in some automated qualification build/test environment.

Maybe I should blog about this...

Hello again. I have come up with a solution:

// update the world
    WorldState worldState;
    for(std::size_t i = 0; i < _entities.size(); ++i)
    {
        auto& entity = _entities[i];
        auto client = _clients[i];

        entity.rigidBody->applyCentralForce(-GRAVITY);
       
        float dirX = 0.0f;
        float dirZ = 0.0f;
        bool movingForward = false;
       
        for(auto& inputState : newInputs[client->id()])
        {
            for(auto& input : inputState.inputs)
            {
                if (input.movingForward)
                {
                    movingForward = true;
                   
                    dirX += input.dir.x;
                    dirZ += input.dir.y;
                }
               
                entity.dir = input.dir;
            }
           
            _lastInputIds[client->id()] = inputState.id; // this can be optimized
        }
       
        if (movingForward)
            entity.rigidBody->setLinearVelocity(btVector3(dirX * cfg.playerSpeed(), entity.rigidBody->getLinearVelocity().y(), dirZ * cfg.playerSpeed()));
        else
            entity.rigidBody->setLinearVelocity(btVector3(0.0f, entity.rigidBody->getLinearVelocity().y(), 0.0f));
       
        worldState.addEntityData(client->id(), entity);
    }
   
    _world->stepSimulation(dt);

Essentially what I am doing is to calculate the sum of the direction vectors for all input packets and set the velocity (for that frame) based on those.

Example:

Let's say the player's speed is 20.

Two inputs arrive with vectors (1, 0) and (0, 1).

So:

dirX = 1 (1 + 0)

dirZ = 1 (0 + 1)

Speed will be set to Vector3(1, 0, 1).

In other words, instead of moving the player gradually, I am setting a larger velocity which has the same effect.

The other solution is to manually translate the player. But I don't like this because if many input packets are sent together, collisions may be skipped...

@sheep19: It sounds like you're not using a fixed simulation step rate. I believe you will, in the end, have real trouble with this. I suggest you decide on a fixed number of simulation steps per second (30? 60? 182? whatever.) Then, run the input-and-simulation at that rate on all clients and on the server. However, rendering will be run at whatever rate the client computer can keep up with. You should also send the user inputs in a given group size -- say, 60 Hz simulation, two inputs per packet, means 30 packets per second. This way, there is no difference in "how many inputs are there in a second" or "how does a player move for a particular network packet."

For more on this, check out this article: http://www.mindcontrol.org/~hplus/graphics/game_loop.html

@sheep19: It sounds like you're not using a fixed simulation step rate. I believe you will, in the end, have real trouble with this. I suggest you decide on a fixed number of simulation steps per second (30? 60? 182? whatever.) Then, run the input-and-simulation at that rate on all clients and on the server. However, rendering will be run at whatever rate the client computer can keep up with. You should also send the user inputs in a given group size -- say, 60 Hz simulation, two inputs per packet, means 30 packets per second. This way, there is no difference in "how many inputs are there in a second" or "how does a player move for a particular network packet."

For more on this, check out this article: http://www.mindcontrol.org/~hplus/graphics/game_loop.html

At the end of update() on the server, I do

std::this_thread::sleep_for(16ms);

And then update the physics engine using the delta time from the previous frame.

Doesn't this guarantee a 60Hz simulation step rate?

About the inputs, I don't this I can do this easily. This is because if packets are lost, the client resends them. This would complicate things a lot. I believe what I did above is sufficient (setting the velocity based on the inputs received for that single frame).

At the end of update() on the server, I do
std::this_thread::sleep_for(16ms);
And then update the physics engine using the delta time from the previous frame.
Doesn't this guarantee a 60Hz simulation step rate?

This will only be a 60hz step rate if you subtract the time taken to run update() from the 16ms. Also if your update takes more than 16ms then, you can end up in a "spiral of death".

The links provided about how to fix your time step are the correct approach for these reasons and more :)

At the end of update() on the server, I do
std::this_thread::sleep_for(16ms);
And then update the physics engine using the delta time from the previous frame.
Doesn't this guarantee a 60Hz simulation step rate?

This will only be a 60hz step rate if you subtract the time taken to run update() from the 16ms. Also if your update takes more than 16ms then, you can end up in a "spiral of death".

The links provided about how to fix your time step are the correct approach for these reasons and more

I didn't understand much from that article... But I found this one: http://gafferongames.com/game-physics/fix-your-timestep/

I'll work on it tomorrow.

At the end of update() on the server, I do
std::this_thread::sleep_for(16ms);
And then update the physics engine using the delta time from the previous frame.
Doesn't this guarantee a 60Hz simulation step rate?

Not really, for two reasons:

1) Simulation takes some time, so you really want to be using a monotonic clock to calculate "sleep until" time, rather than assume 16 ms per step.
2) This does not synchronize the clients with the servers in any way. The clients need to run the simulation at the same rate (although graphics may be faster or slower.)

Separately:

About the inputs, I don't this I can do this easily. This is because if packets are lost, the client resends them.

What does the server do, then? Wait for the input? That means any player can pause the server by simply delaying packets a bit.

In general, you don't want to stop, block, or delay anything in a smooth networked simulation. If you're worried about single packet losses, you can include the commands for the last N steps in each packet -- so, if you send packets at 30 Hz, and simulate at 60 Hz, you may include input for the last 8 steps in the packet. This will use some additional upstream bandwidth, but that's generally not noticeable, and it generally RLE compresses really well.

Being able to use the same step numbers on client and server to know "what time" you're talking about is crucial. Until you get to the same logical step rate on client and server, you'll keep having problems with physics sync.

Gaffer's article is almost exactly like the canonical game loop article; using either is fine.

At the end of update() on the server, I do
std::this_thread::sleep_for(16ms);
And then update the physics engine using the delta time from the previous frame.
Doesn't this guarantee a 60Hz simulation step rate?

Not really, for two reasons:

1) Simulation takes some time, so you really want to be using a monotonic clock to calculate "sleep until" time, rather than assume 16 ms per step.
2) This does not synchronize the clients with the servers in any way. The clients need to run the simulation at the same rate (although graphics may be faster or slower.)

Separately:

About the inputs, I don't this I can do this easily. This is because if packets are lost, the client resends them.

What does the server do, then? Wait for the input? That means any player can pause the server by simply delaying packets a bit.

In general, you don't want to stop, block, or delay anything in a smooth networked simulation. If you're worried about single packet losses, you can include the commands for the last N steps in each packet -- so, if you send packets at 30 Hz, and simulate at 60 Hz, you may include input for the last 8 steps in the packet. This will use some additional upstream bandwidth, but that's generally not noticeable, and it generally RLE compresses really well.

Being able to use the same step numbers on client and server to know "what time" you're talking about is crucial. Until you get to the same logical step rate on client and server, you'll keep having problems with physics sync.

Gaffer's article is almost exactly like the canonical game loop article; using either is fine.

1) I understand. I can subtract the time of the update() function like braindigitalis suggested.

But let's say the whole update() function took more than 16 ms. The result would be negative, so the thread wouldn't sleep at all.

Is this ok? (I don't think this will happen, as now it takes ~0.4 ms. But things might change in the future, so...)

Can I assume that the server's update function won't take more than 16ms?

If it takes longer, is it okay that the thread won't sleep at all?

2) Yes, this does not synchronize the clients. I will have to implement this on the client side as well.

No, the server's game loop does not wait for inputs. There is a separate thread that listens for inputs and when they are received they are passed to it.

By the way, the clients gather inputs every frame and send them every 33ms.

Can I assume that the server's update function won't take more than 16ms?

If it takes longer, is it okay that the thread won't sleep at all?

1: No.

2: Yes, but. Really check that gaffer articles, especially the last part and the use of the accumulator - that'll keep the server ticking nice and smooth even with a few slow frames.

If too many frames take longer, you will have to reduce frequency - it would mean your computer just cannot calculate that many update()s that fast.

however, try to simulate some lag early on in your development - it will make obvious a lot of problems you might otherwise miss and safes you a lot of rewriting later on.

maybe i have missed something, but do you run physics/collision-detection only on the server, and not on the clients as well?

maybe i have missed something, but do you run physics/collision-detection only on the server, and not on the clients as well?

You are correct. The physics / collision-detection is only on the server. Clients buffer 2 states from the server and interpolate between them.

But this temporary, I will implement it on the client as well, after I'm done with this.

After reading (and hopefully understanding the article), I've modified my code to look like:

// === THIS CODE IS RUN ON THE SERVER ===

const float TIME_STEP = 0.016f;

auto t0 = std::chrono::steady_clock::now();
auto t1 = t0;

float accumulator = 0.0f;

while (game->isRunning())
{
auto t1 = std::chrono::steady_clock::now();
auto frameTime = ((float)std::chrono::duration_cast(t1 - t0).count()) / 1'000'000.0f; // in seconds
t0 = t1;

accumulator += frameTime;

while (accumulator >= TIME_STEP)
{
game->update(TIME_STEP); // read client inputs and update physics accordingly
accumulator -= TIME_STEP;
}
}

This is Game::update(float):

1) read inputs for each client
2) if the player is moving set his velocity towards his looking direction, else set it to 0
3) update the (physics) world
4) sleep(TIME_STEP)

Is it correct this time?

Thanks to everyone for the help.

let's say the whole update() function took more than 16 ms.

Then your game is broken on that server.
An occasional timestep that takes longer might be OK, but if this happens with any frequency, then your hardware spec and software meeds mis-match.
You should at that point detect the problem, show a clear error message to the user, and end the game.

The sleep more like

sleep(TIME_STEP - accumulator);

And after the accum's while loop.
Rest looks good.

let's say the whole update() function took more than 16 ms.

Then your game is broken on that server.
An occasional timestep that takes longer might be OK, but if this happens with any frequency, then your hardware spec and software meeds mis-match.
You should at that point detect the problem, show a clear error message to the user, and end the game.

Alright. So, yes, I can assume that update() takes less than 16. If not, I'll need new hardware :)

So I've added this after the accumulator loop:

std::this_thread::sleep_for(std::chrono::microseconds(static_cast((TIME_STEP - accumulator) * 1'000'0000.0f)));

If not, I'll need new hardware

Or profile/optimize the software! :-)