Rollback Performance

I simulated what game performance would be like in a rollback-networked online multiplayer world, and the answer was "Terrible".

So I made it a lot less terrible!

And I incorporated some feedback on last week's Lightning spell too.

Stunning Changes

After last week's update, the Discord brain trust told me it felt wrong to have zapped enemies still run towards you and attack.

I agreed - so I fixed it!

The new visual zapping effect is hand drawn per character,¹ which I think makes this the first "animation" in the whole game.

Multiple Players and Game Design

It's arguably a little premature to think about networked multiplayer when the game isn't particularly fun to play yet.

But I've been kicking around designs for how the larger game should be structured, and some of those designs work much better with other players. ²

And it's much easier to play with other players if you don't have to convince them to leave their own cave home.

So, "can we do online multiplayer" influences not just marketability, but also significantly affects the design of the game; therefore, I spent some time investigating that question.

Online Multiplayer Feasibility

The tentative plan for online multiplayer is this:

1. Each game sends their player's input (e.g. buttons pressed) for a simulation-step to all other connected players.
2. Once the game on one computer has input for all players, it "ticks" (runs for one simulation-step) the game simulation & snapshots (saves) the result.
   1. If the game didn't get an input from a remote player in time, it predicts what their input would have been, and uses that instead.
   2. If the game later receives a previously-missing input that differs from an old predicted input, after say 3 ticks of further simulation, the game rolls back (restores) its game state to the state 3 simulation steps ago, re-ticks those 3 simulation steps with the corrected input, then continues again.
3. (Repeat from step 1, until someone rage quits.)

This approach is so cool!

It uses very little network bandwidth, it resists cheating, and it doesn't result in multiplayer-only game-breaking glitches from lag or temporary packet loss.

But... always saving the world state, doing a rollback and then re-simulating the world N times takes a whole lot of processing power - in a game design that's already very heavily using the CPU.

Is it too much?

Prediction Accuracy

I was tempted to performance test immediately, but if you paid attention you've probably realized that you only need to resimulate the world when:

• Remote players' input doesn't arrive (packet loss³)
  AND
• The predicted input didn't match what the remote player actually input.

We don't have control over packet loss, but what about input prediction?

Well, input prediction is super simple:

If a player was pressing a button, assume they'll keep pressing that button.

Apparently even the fastest players only press 5 buttons per second, so it works.

But what about analog inputs, such as thumb-stick position on a gamepad?

I was worried that even the slightest movement would cause a mis-prediction...

And I was right! Here's a little visualization I built:

You can see even tiny changes in thumb-stick movement cause mispredictions, and over 50% of inputs end up mispredicted (& hence would cause world resimulation) - not good!

So I tried snapping⁴ those analog inputs:

• I snap the movement input to one of 8 directions with 10 possible magnitudes.
• I snap the aim input to either⁵ 2 or 256 possible directions with only 2 possible magnitudes.

That drastically reduces mispredictions, at least for normal inputs: ⁶

Okay, 20% is much better than 50%, but in a 4 player game there are a total of 3 other players who can each cause rollbacks.

So we're going to have to deal with a fair few rollbacks - what does that mean?

Performance Matters

Well, if we want to support playing with anyone anywhere in the world,⁷ the game must support rollback and re-simulations of up to 7 ticks. ⁸

To see what that felt like right now, I added a debug option to do an extra 7 world-clones and re-simulations each frame:

My performance immediately dropped from 60 FPS (frames per second) to an eye-watering 30 FPS, with sustained dips to 20 FPS. Ouch.

To get back to 60 FPS, the game must simulate the whole game world 8 times in ~16ms. That's ~2ms per tick, on average.

Only 2ms to simulate the whole game world?! Geez, how long are we taking right now?

Starting point: it takes 3.6ms on average to simulate the game world for one tick.
Graph shows two peaks; #1 is steady state, and #2 is barrels falling and exploding.
(Graph's x-axis is 'time taken' and y-axis is 'count of times it took that long'.)

And that's from a special benchmark where I wasn't even moving or casting spells at enemies! (Just standing still, with a couple barrels exploding in the background.)

Let's try improving performance to cut that time in half.

Moving Body Atom Writes

A while back I optimized the "time to clone the world" performance by breaking the world into copy-on-write chunks of atoms: each chunk would be shared with the "saved" versions of past ticks' game worlds, right up until the chunk needed to be written to by the current game world, at which point it would get copied.

That worked really well in my initial benchmarking, but in a level with lots of moving bodies, it performed quite badly - even if the bodies lay still!

Why?

Each moving body is composed of atoms, and each tick a moving body would remove its atoms, simulate its rigid body physics to find where it moves to, then put its atoms back into the new positions dictated by its new position. Those writes would cause whole chunks of atoms to be copied each simulation tick, even if the body wasn't even moving.

I optimized that by only removing and re-placing the atoms if the moving body, you know, actually moved. Duh. ⁹

Terrain Collider Reuse

Each moving body is only able to collide with the world because each chunk of atoms is processed into a physics "collider".

Even after earlier optimizations to skip chunks devoid of moving bodies, over half of each tick was being spent on collider creation!

Each vertical bar is a frame; light white is time spent on creating those colliders; dark white is everything else.

After some moderately successful attempts to optimize the processing itself, I hit on the obvious approach: if the atoms that contribute to colliders¹⁰ haven't changed, then keep the old collider around.

That lead to another small win: physics engines normally put moving bodies "to sleep" if they haven't moved in a while, which reduces physics simulation costs.

With the world's colliders previously being recreated each tick, moving bodies weren't ever able to sleep - but now they can!

And that lead to an even better optimization: I realized that if a chunk only contained sleeping moving bodies, then it could be skipped entirely!

End Result

Finally, after all that plus a few less interesting tweaks, let's see how we did:

End point: simulating one tick dropped from 3.6ms to 0.9ms (on average). That's a 4X speedup!

Yay, 0.9ms is under our 2ms goal!

There are three big caveats to this performance test result though:

• I'm benchmarking on a pretty fast computer. ¹¹
• This test level is 4-8 times smaller than I want levels to be.
• There wasn't much happening in it; a few explosions, but no spells or other combat.
  • If I actually play the game with the 7-extra-world-simulations debug option, I see 50-60 FPS with occasional brief dips to 30 FPS - so further work is required!

I have some other tricks up my sleeve,¹² but we'll have to see if they're enough.

Still, even if rollback-based online multiplayer doesn't work out, these changes will still make the game perform better for everyone!

Playable web build‎

You can try out the tweaked lightning spell below!

The rollback simulation is available in the web build too; press F2 then scroll down to the Rollback section and set Logic Repeat to (say) 7. Performance on the web build is a bit worse than on desktop, mind.