I have written a blogpost about the "sliding bug", a bug that has pestered our game Awesomenauts for over 1.5 years. We recently finally fixed it in a patch. I think it is a nice example of the complexities of collision handling in a purely peer-to-peer architecture, so I hope it is okay to make a topic about it here and post a link. An interesting lesson for me was that the solution we used turns out to be really incorrect, but to work really well with actual player behaviour. True correctness is not always needed!

How we solved the infamous sliding bug

It's a very difficult problem, actually, especially peer to peer. Lag is the enemy, even minute. That's why most games run through an authority (server), that controls the game state, while clients merely predict locally what's happening and get corrected by the host. Which causes jumping, re-sync, ect... when two characters collide (see, the original counterstrike).

There are possibilities. Some of them involve using loose tolerances for collisions, making them more soft and forgiving, and letting the collisions resolve themselves on each client. Which can generate rubber-banding physics when you get two players colliding. Players will loose sync as well. What you see on one machine will not match what you see on the other machine, and will take a while to resync. Not nice at all.

Something I always wanted to try, was using in-sync, RTS-style game states. Every player has the same global, deterministic view of the game, with their inputs running at the same ticks, and sequence numbered. Every tick, the game state is saved on each machine, and you sort of 'predict' each remote player's input ahead of time, while you run the local player inputs ahead. Once you receive a remote player inputs, you can rewind the entire game state, and replay the game from that point on to arrive at new locally simulated game state. This means you will have a deterministic game on every machine, and consistent physics across the game. The problem now becomes, what happens when the prediction diverges from the local simulation. And that, I don't know until I can run an experiment myself.

It's a bit how RTS games handle networking. Think of it like Braid, but in a multiplayer context (except Braid of course, breaks the time continuum as part of the game mechanics).

You can also look up Gaffer's networked physics, but in general, that kind of problem you encounter is often resolved ad-hoc, with hacks, basically breaking your internal laws of physics (turning collisions) off for a short while. That's one reason I hate Peer to Peer topology.

It's still valid, we're making games, not shooting rockets at Mars, but it's a bit 'dirty'. Latency is in general, nasty, and a difficult problem. That's why we have all sorts of techniques to hide lag as best we can, like client-prediction, server correction, lag compensation. And even then, it's still in general, crap. Can't bend time, unless you have consistent sub-frame latency, you'll always suffer lag.

Something I always wanted to try, was using in-sync, RTS-style game states. Every player has the same global, deterministic view of the game, with their inputs running at the same ticks, and sequence numbered. Every tick, the game state is saved on each machine, and you sort of 'predict' each remote player's input ahead of time, while you run the local player inputs ahead. Once you receive a remote player inputs, you can rewind the entire game state, and replay the game from that point on to arrive at new locally simulated game state. This means you will have a deterministic game on every machine, and consistent physics across the game. The problem now becomes, what happens when the prediction diverges from the local simulation. And that, I don't know until I can run an experiment myself.

This would be a really interesting experiment! I think it could work, but the big problem is that it is ridiculously complex to build. It is really difficult to write fully deterministic code, so I'd say that the added complexity of building this plus the work in fixing bugs is going to cost an enormous amount of extra development time...

Just a pet project of mine :) I wanna see how that would work, if at all.

FWIW: That's basically what GGPO does, as well as various other networked physics engines. It's not that hard to build if you can either store a log of physics state for each object, or you can allocate all needed physics state in a single block of RAM. You just have to make sure your engine is set up for it ahead of time, rather than trying to retro-fit it.

Coo

FWIW: That's basically what GGPO does, as well as various other networked physics engines. It's not that hard to build if you can either store a log of physics state for each object, or you can allocate all needed physics state in a single block of RAM. You just have to make sure your engine is set up for it ahead of time, rather than trying to retro-fit it.

Cool. Looks like it's worth a look.

FWIW: That's basically what GGPO does, as well as various other networked physics engines. It's not that hard to build if you can either store a log of physics state for each object, or you can allocate all needed physics state in a single block of RAM. You just have to make sure your engine is set up for it ahead of time, rather than trying to retro-fit it.

Does GGPO also do the full determinism? I know it does the rewind/resimulate thing, but I never heard it also does full determinism.

@Oogst, thanks for sharing the crazy solution

@papalazaru - I've seen that basic idea used in 360/PS3 action games.

Each player is constantly trying to commit 'actions' to the game state, with both players having an 'agreed' upon state, and then both players stacking up actions on top of that as 'predictions' locally. Over time, the 'agreed' upon state advances forward by applying the actions of each player. Sometimes this process means that a certain player's predictions have to be undone / popped from their stack, as they're not valid actions any more after the other player's actions have been inserted underneath them.
Sometimes you need a bit of arbitration to resolve conflicts -- e.g. if on the same frame a player carrying a ball says they've kicked it, while on the same frame an enemy says they snatched the ball away. In that case you'd need a rule saying that the person carrying the ball has their actions applied first, etc, etc. Then when trying to apply the "snatched" action, it isn't valid (as the person they're snatching it from doesn't have a ball -- it's now been kicked into the air), so it gets thrown away and the client who performed that action sees a small 'pop' in their gameplay, as the invalid prediction is unwound on their end.

FWIW: That's basically what GGPO does, as well as various other networked physics engines. It's not that hard to build if you can either store a log of physics state for each object, or you can allocate all needed physics state in a single block of RAM. You just have to make sure your engine is set up for it ahead of time, rather than trying to retro-fit it.

Does GGPO also do the full determinism? I know it does the rewind/resimulate thing, but I never heard it also does full determinism.

In general, If you think you need prefect determinism, you should be able to adapt your algorithms to use more 'loose' tolerances.

What I'm thinking of :

1) some error tolerance on your objects (object position, velocity, ect...), beyond which a de-sync is detected.

2) rollback objects affected by the de-sync, re-apply the fix that reduces or eliminate the error.

3) replay those de-synced objects up to current time.

In general, If you think you need prefect determinism, you should be able to adapt your algorithms to use more 'loose' tolerances.

This is the wrong way to think about the problem, in my opinion.

Either you need full determinism, and only send inputs, or you don't need determinism, and you send state checkpoints (perhaps as baselines, with inputs as deltas for some small amount of time.)

Achieving full determinism is absolutely possible, as demonstrated by many games. It's also not easy, as demonstrated by a lot of post mortem write-ups in Game Developer magazine and other resources :-)