Rollback Prediction Management

I'm guessing you're doing something like a fighting game, where frame data is based on a 60hz sim? If not, a first step would be to drop the sim to 30.

What all are you having to replay, state-wise? Are you in an engine where you're stuck recalculating a complex physics sim? Have you instrumented your rollback/replay code and figured out what's taking the most time?

Net_ said:

I'm guessing you're doing something like a fighting game, where frame data is based on a 60hz sim? If not, a first step would be to drop the sim to 30.

What all are you having to replay, state-wise? Are you in an engine where you're stuck recalculating a complex physics sim? Have you instrumented your rollback/replay code and figured out what's taking the most time?

Fps

Mostly movement, shooting, abilities.

Right now it's just expensive to run multiple update ticks in a frame. Even if there's no input, just executing so much logic multiple times a frame is heavy on device.

Does anyone have a particular resource that describes or demonstrates their rollback and reprediction technique for reference?

have u seen this SDK: https://www.ggpo.net/​

he's got an opensource c++ github project, might be worth having a look…

That's it… all the best ?

@undefined

max5 said:

60hz , i dont think so..)

Sorry I don't think I understand

max5 was a spammer.

Even if there's no input, just executing so much logic multiple times a frame is heavy on device.

Why? What are you doing that is expensive in your simulation? Where does the profiler say you're spending your CPU cycles (and thus your battery)?

@undefined

hplus0603 said:

max5 was a spammer.

Even if there's no input, just executing so much logic multiple times a frame is heavy on device.

Why? What are you doing that is expensive in your simulation? Where does the profiler say you're spending your CPU cycles (and thus your battery)?

It's mobile. Plus using some experimental tech/engine that isn't meant to do operations like this unfortunately. My devices end up running less than 30 fps even with optimizations, and rendering is already as low as it can go. The prediction ticks just take up so much frame time. And a misprediction and rollback will lead to a 16 up to 32 ticks of reprediction. It destroys the frame and subsequent frames because the device falls behind.

I feel the best next steps until I can get over those hurdles is to reduce tick rate to 30hz for now and try to push 60 for when the game goes public.

Right now, I have a hack in that has clients simulating only 1 prediction tick regardless of performance. Obviously this isn't good for prediction, movement input with a frame time of 32ms can/will be different from movement with a frame time of 16ms x 2. It's fine for testing and demos for now but it won't hold up under scrutiny. My slowest phone ends up being caught in a lot of rollbacks. But the performance is much better than doing multiple ticks for now ?

I've been trying to bar at the folks who make the engine and that experimental tech to see what we can do. Because when I don't use that engine I can get much better times thankfully.

ddlox said:

Does anyone have a particular resource that describes or demonstrates their rollback and reprediction technique for reference?

have u seen this SDK: https://www.ggpo.net/​

he's got an opensource c++ github project, might be worth having a look…

That's it… all the best ?

I've tried looking into ggpo several times and didn't see it fitting my shooting game, but I gave it another shot and I guess the implementation is a bit fuzzy to me because of my understanding of how it works at a high level. I kind of understand it, but I don't understand it in contexts outside of Street Fighter or, say, Mortal Kombat for example.

It predicts the input from other players, but a lot of games wouldn't want that - like my own. Something like a shooter for example: the local player wouldn't care what other players' inputs, they only care about the results of their inputs (ie result world state). Other players are just “ghosts” to the local player.

Because it's not p2p, the server has lag compensation and stuff to help the local player's inputs against the ghost remote players to compensate for the delay. Whereas with ggpo, instead it does something like sync the player's input delays to the best compromise for an optimal experience. This doesn't really translate over I think? Not sure. I wouldnt want one person's bad connection having a direct impact on the experience/other players in a game of 5 up to 100 and more people.

However, the rollback itself (whether it's consisting of 2 p2p players or 1 player connected to a server) seems to be the same idea. If the predicted state mismatches, rollback and repredict inputs. Here's the rub I'm not sure I follow:

When you repredict after a rollback, is everything just rollback and let the simulation run as normal? Or in 1 frame (resimulate multiple ticks for pending inputs)?

GGPO, according to an image on their site, shows it as the former. The rollback occurs when the verify fails, but that's only on frame 1. Frame 2 predicts with the input on different frames (2, 3, 4).

In the latter (resimulate in same frame) which is what my model uses, we'd loop in frame 1 until all pending inputs sent to the server that have not bee ack'd are simmed before continuing to frame 2. That's where my performance problem lies. Maybe I should try not blocking in frame 1 and just letting the simulation continue as normal, see how it behaves?

In my experience, you only need to rollback if there is a /mis/ prediction, i.e. you know that you've done something locally that cannot be correct because the assumptions you based it on were false. Normally this is a rare event. The fact that you seem to be doing one every single frame implies… well, it's a weird setup. My fix for that would be “don't do that”.

As for rollbacks when you get lag, that's a bit odd. The point of the ‘predicted’ input is that the system is accepting that lag exists. If nothing else interacts with the object being predicted, then you should be able to cope with any amount of lag - 100ms, 1 second, 1 hour, anything. It's only when the simulations diverge - usually due to interaction caused by some other object - that you need to rollback and replay. And that should happen rarely.

But does it only happen rarely? The implication here is that it happens a lot when you have lag, which implies something else is wrong. This is where relying on comparing state hashes is also a bit of a red flag. That sounds like a useful optimisation when the system is working perfectly, but at this stage it's an unnecessary barrier stopping you from easily seeing why the simulations have diverged. Maybe you just have a bug that is causing more rollbacks than necessary?

Kylotan said:

In my experience, you only need to rollback if there is a /mis/ prediction, i.e. you know that you've done something locally that cannot be correct because the assumptions you based it on were false. Normally this is a rare event. The fact that you seem to be doing one every single frame implies… well, it's a weird setup. My fix for that would be “don't do that”.

As for rollbacks when you get lag, that's a bit odd. The point of the ‘predicted’ input is that the system is accepting that lag exists. If nothing else interacts with the object being predicted, then you should be able to cope with any amount of lag - 100ms, 1 second, 1 hour, anything. It's only when the simulations diverge - usually due to interaction caused by some other object - that you need to rollback and replay. And that should happen rarely.

But does it only happen rarely? The implication here is that it happens a lot when you have lag, which implies something else is wrong. This is where relying on comparing state hashes is also a bit of a red flag. That sounds like a useful optimisation when the system is working perfectly, but at this stage it's an unnecessary barrier stopping you from easily seeing why the simulations have diverged. Maybe you just have a bug that is causing more rollbacks than necessary?

I'm not having rollbacks every frame, but I am having issues where rollbacks have to happen because I inevitably mispredicts. Because device performance is so low due to having to sim multiple ticks a frame. ?

Don't sim multiple predictions in 1 frame -i could hear my gran'ma screaming-

You want to simulate them from the rollback frame (the one that failed) to the current frame. Then grab local inputs again and predict from the current frame on. Look at the diagram u posted of ggpo, it shows you that failure between frame 3 and frame 4, right?, but u rollback to frame 1 and u sim to frame 4 ( the reason u roll back to frame 1 is because remote inputs have arrived and are informing u that your prediction is wrong and these remote inputs are still on frame 1. So u rollback to frame 1 (or whatever that failed frame will be in your case))

So you rollback to the frame of which the remote inputs (when they have arrived) indicate that those players are at! And then you simulate to the current frame 4 (which means you will be repredicting in some of these frames) and then finally you can gather local input data again from frame 5 and predict (and so on and the cycle goes on etc…)

That's kind of what ggpo does when it rolls back (in a nutshell). Also, that's why ggpo gathers all inputs from all players BEFORE the next frame is executed, this gives the best predictions (it's not about sharing network performance or load), it's about giving your system the best chance of predicting correctly (but yes unfortunately when prediction fails then u rollback as mentioned)

I hope this makes more sense now, I predict that u understand it better now ?

Have fun ?

ddlox said:

Don't sim multiple predictions in 1 frame -i could hear my gran'ma screaming-

You want to simulate them from the rollback frame (the one that failed) to the current frame. Then grab local inputs again and predict from the current frame on. Look at the diagram u posted of ggpo, it shows you that failure between frame 3 and frame 4, right?, but u rollback to frame 1 and u sim to frame 4 ( the reason u roll back to frame 1 is because remote inputs have arrived and are informing u that your prediction is wrong and these remote inputs are still on frame 1. So u rollback to frame 1 (or whatever that failed frame will be in your case))

So you rollback to the frame of which the remote inputs (when they have arrived) indicate that those players are at! And then you simulate to the current frame 4 (which means you will be repredicting in some of these frames) and then finally you can gather local input data again from frame 5 and predict (and so on and the cycle goes on etc…)

That's kind of what ggpo does when it rolls back (in a nutshell). Also, that's why ggpo gathers all inputs from all players BEFORE the next frame is executed, this gives the best predictions (it's not about sharing network performance or load), it's about giving your system the best chance of predicting correctly (but yes unfortunately when prediction fails then u rollback as mentioned)

I hope this makes more sense now, I predict that u understand it better now ?

Have fun ?

Thanks but that was what I was saying before. Ggpo doesn't seem to apply to my model. That's like lockstep. My players don't care about the inputs of other players. Time progresses regardless of input. You mentioned remote input arriving. In the case of the local player, there is no remote input.

ok i pointed u to ggpo to see if it could help in your case but u found that it doesn't; ok understood.

let's step back a bit… u previously said:

Because device performance is so low due to having to sim multiple ticks a frame. ?

and much earlier:

The prediction ticks just take up so much frame time.

if u sim at 30fps or 60 or whatever, how much time exactly does each of those multiple ticks take per frame? and why?

i understand that you're running on mobile with all optimization guns blazing, but u need to see if u can log or profile those prediction ticks times somehow, otherwise there's a chance we'll keep giving you advice which won't fit your model.

There is no question that something is eating up those times, but we will never know what it is if u don't clock it… u said if u remove the tech/experimental engine, u get better results… well… clock your code without this engine, then put the engine back on and clock your code again and see where the difference comes from?….

is this not possible ?

Until then ?

ddlox said:

ok i pointed u to ggpo to see if it could help in your case but u found that it doesn't; ok understood.

let's step back a bit… u previously said:

Because device performance is so low due to having to sim multiple ticks a frame. ?

and much earlier:

The prediction ticks just take up so much frame time.

if u sim at 30fps or 60 or whatever, how much time exactly does each of those multiple ticks take per frame? and why?

i understand that you're running on mobile with all optimization guns blazing, but u need to see if u can log or profile those prediction ticks times somehow, otherwise there's a chance we'll keep giving you advice which won't fit your model.

There is no question that something is eating up those times, but we will never know what it is if u don't clock it… u said if u remove the tech/experimental engine, u get better results… well… clock your code without this engine, then put the engine back on and clock your code again and see where the difference comes from?….

is this not possible ?

Until then ?

Yes I'm looking for ways to ditch it. Unfortunately that choice is likely out of my hands but I can use the results to poke the engine creator.

Sorry I'm not trying to be dismissiv,I I appreciate thehelp I guess I'm just trying to make sure my prediction loop is actually correct and I'm the one not making the mistake. Like doing multiple ticks per frame when prediction is okay, and having to do up to 30~ ticks in 1 frame when a rollback happens.

NetworkDev19 said:

I'm not having rollbacks every frame, but I am having issues where rollbacks have to happen because I inevitably mispredicts. Because device performance is so low due to having to sim multiple ticks a frame. ?

This still sounds like a bug to me. You should be able to predict a long way into the future without anything going wrong, unless some other entity is affecting the simulation. Whether it's one tick or one hundred ticks in a frame shouldn't matter. Either you're capable of correctly calculating the results of your local input, or you're not.

Kylotan said:

NetworkDev19 said:

I'm not having rollbacks every frame, but I am having issues where rollbacks have to happen because I inevitably mispredicts. Because device performance is so low due to having to sim multiple ticks a frame. ?

This still sounds like a bug to me. You should be able to predict a long way into the future without anything going wrong, unless some other entity is affecting the simulation. Whether it's one tick or one hundred ticks in a frame shouldn't matter. Either you're capable of correctly calculating the results of your local input, or you're not.

The issue is that the server is running 60hz. Clients are trying to keep up and predicting ahead of that time wise. But if performance is too low, their progression of time slows. So their prediction falls behind what the server is calculating. Thus the need of a rollback. The client will diverge if they can't keep up with the server. So it absolutely matters if it's one tick or 100 ticks in a frame no? The client is running, say, 15fps or lower. The server will always be ahead of the client. Then the client has to try to rollback and repredict, which further kills performance. The tick time in the client is always now in a “catch-up”. The only way to get back in sync is to rollback, skip it's predicted tick time into future to readjust, then resim. It's constantly going to be trying to do this because perf is low. And because of that, it will mispredict. Does that make sense? Can I elaborate on any particular step that maybe I'm doing something wrong on?

Also, another issue comes up as a side effect. The server has to process inputs for specific tick times. If the client predicts their input will arrive on the server at tick 10, but the server is at tick 20 because the client has fallen behind when it should be ahead for prediction, the server has to ignore the input or it won't be deterministic. So that too will influence mispredictions right? A client who is too far in the past (thanks to low frame rate) will have difficulty sending commands for the right tick which means it will predict the input but the server will reject it. Misprediction occurs.

This however I think can be combatted by using the frame time delta and trying to guess at the server's real tick time.

Edit: oh fudge. This made me think of something. Quick side question, is it more “correct” to send a packet with input at the beginning of the frame or at the end? Right now I'm sending inputs at the end of the frame. This does not account for the current frame time. So if you do an input, the game samples it, then does prediction (which is slow currently) and then sends the input at the end. That frame time doing prediction is not accounted for in the packet being sent… this could be significant to my woes about missed input rollbacks issue mentioned at the end there.

NetworkDev19 said:
The issue is that the server is running 60hz. Clients are trying to keep up and predicting ahead of that time wise. But if performance is too low, their progression of time slows.

Right, that's the bug. The idea of a tick-based system is that each tick represents a fixed and predictable unit of time. You can't have time going slower or faster*. You can drop rendering frames to save processing time, but you can't define ticks as 1/60th of a second and then have some seconds where ticks cover 1/50th of a second. The simulations will play out differently and therefore you lose most of the benefits.

It's fine for the client to lag behind a little more from time to time. Whether this happens due to network lag or other performance characteristics doesn't really matter. Nothing needs repredicting, because nothing is wrong - we just haven't caught up yet, which takes time. The idea is that you don't render until you've caught up on your tick updates. If the client can't catch up, e.g. because the CPU burden is just too high, then your model parameters are not suitable for the constraints you have. You will need to adjust the parameters to fit within the resources available.

(* Actually, you can, but that's an added complication, and you need to get the basics working first. Watch the video on Overwatch's architecture and netcode to hear about how they stretch time.)

NetworkDev19 said:
If the client predicts their input will arrive on the server at tick 10, but the server is at tick 20 because the client has fallen behind when it should be ahead for prediction, the server has to ignore the input or it won't be deterministic. So that too will influence mispredictions right?

Sure. However, once you're in this position, the predictions are mostly worthless because the rest of the world has already overtaken that point. The server's already told everyone else where that client was on tick 11, 12, 13, etc. Not much point rolling back and reapplying locally when you know that state is invalid - better to just snap to whatever is the latest server state so that you've caught up.

This is not generally a tenable situation though, and for reasons mentioned above, you want to get your system into a position where this is a last resort for dealing with extreme lag spikes, not a standard part of most player's experience.

NetworkDev19 said:
is it more “correct” to send a packet with input at the beginning of the frame or at the end?

It doesn't really matter when you send it. What matters is how you reason about it. Each tick takes the current world state at T=N plus the current inputs and produces a successor world state T=N+1. When you receive a state from the server, you need to know what N was for that state, so that you can find your corresponding input N and re-do that tick (and all subsequent ones).

Kylotan said:

NetworkDev19 said:
The issue is that the server is running 60hz. Clients are trying to keep up and predicting ahead of that time wise. But if performance is too low, their progression of time slows.

Right, that's the bug. The idea of a tick-based system is that each tick represents a fixed and predictable unit of time. You can't have time going slower or faster*. You can drop rendering frames to save processing time, but you can't define ticks as 1/60th of a second and then have some seconds where ticks cover 1/50th of a second. The simulations will play out differently and therefore you lose most of the benefits.

It's fine for the client to lag behind a little more from time to time. Whether this happens due to network lag or other performance characteristics doesn't really matter. Nothing needs repredicting, because nothing is wrong - we just haven't caught up yet, which takes time. The idea is that you don't render until you've caught up on your tick updates. If the client can't catch up, e.g. because the CPU burden is just too high, then your model parameters are not suitable for the constraints you have. You will need to adjust the parameters to fit within the resources available.

(* Actually, you can, but that's an added complication, and you need to get the basics working first. Watch the video on Overwatch's architecture and netcode to hear about how they stretch time.)

NetworkDev19 said:
If the client predicts their input will arrive on the server at tick 10, but the server is at tick 20 because the client has fallen behind when it should be ahead for prediction, the server has to ignore the input or it won't be deterministic. So that too will influence mispredictions right?

Sure. However, once you're in this position, the predictions are mostly worthless because the rest of the world has already overtaken that point. The server's already told everyone else where that client was on tick 11, 12, 13, etc. Not much point rolling back and reapplying locally when you know that state is invalid - better to just snap to whatever is the latest server state so that you've caught up.

This is not generally a tenable situation though, and for reasons mentioned above, you want to get your system into a position where this is a last resort for dealing with extreme lag spikes, not a standard part of most player's experience.

NetworkDev19 said:
is it more “correct” to send a packet with input at the beginning of the frame or at the end?

It doesn't really matter when you send it. What matters is how you reason about it. Each tick takes the current world state at T=N plus the current inputs and produces a successor world state T=N+1. When you receive a state from the server, you need to know what N was for that state, so that you can find your corresponding input N and re-do that tick (and all subsequent ones).

I think you misunderstood the first part. The ticks are fixed timesteps. If it's 60hz, then the timesteps is 16ms per tick no matter what. It's a question of how many at that point. And if the client has to run 2+ ticks in a frame every frame, they continue to fall behind often to keep up.

When I said progression of time slows, I literally mean the time it takes for them to tick n frames it thinks it needs to predict ahead of the server, the server is already past those ticks by the time it receives the inputs.

And yes we do the similar time scaling as overwatch to speed up or slow down.

I'm saying that it can't work the way you want it to work. You have to be able to run sufficient tick steps to be able to keep pace with the other simulations. And if you have submitted inputs to the server in time for them to be processed, there should be no mispredictions in normal operation except for the rare cases where some other entity has interacted with you on the server and changed the results.

It's normal for different clients to need to process different numbers of ticks per rendering frame. It's also okay to have some variance from frame to frame because you don't want to process partial ticks, or because you had a short-lived bit of lag. But if you can't execute enough ticks per second to keep up with the server in general, it's game over. The whole model is built around the assumption that every client can provide inputs in time and can process them in time.

I would say your options are basically:

• change the game to use longer ticks, so that the overhead is lower
• reduce your rendering time so that you have more CPU time left over for handling ticks
• change your networking model - e.g. to a cheaper algorithm that attempts to converge simulations, rather than using deterministic steps

if the client has to run 2+ ticks in a frame every frame, they continue to fall behind often to keep up.

This is true if there are no locality benefits (caching, for example) and if there is no other cost for a “frame” (such as rendering.)

If there are other costs that amortize per frame, then the marginal cost of an extra tick is smaller than the cost of the first tick in a frame, and running more ticks will give you some amount of benefit.

That being said – if your simulation can't be run in real time on a given CPU, then the simulation can't be run in real time on that CPU. That's why games have “minimum spec” recommendations. If you want to target some ill defined market like “the web,” then you have to make a very hard trade-off between what you want your game experience to be, and how harsh you need to be against people whose clients don't keep up.