How fighting games use delay-based and rollback netcode (2019) • Hacker News Board

Re: How fighting games use delay-based and rollback netcode (2019)

#41

Post by reitzensteinm » Sun, Feb 28, 2021, 5:59 AM UTC

andai wrote: post #38

thewarrior wrote: post #29

This piece was really interesting. That you can hide network delays by building a “fake” model of the other player that replicates what a real player would do and rolling back when this prediction fails. So you can train some neural nets on what players do in such situations and you get a certain accuracy. And yet you can keep making this “fake” player better and better until it’s indistinguishable from fighting a hu…

Where did you get the thing about neural networks? I read your comment before reading the article and was really disappointed the prediction "algorithm" (pioneered by GGPO in 2006 [0] and still used today) is literally "assume nothing changed", ie. the opponent is still holding down the same keys as the last frame. [0]: magazine article by the author of GGPO [pdf] https://drive.google.com/file/d/1cV0fY8e_SC1hIFF5E1rT…

You shouldn't be disappointed. Nothing has changed is overwhelmingly the correct answer.

It is incredibly jarring to assume a remote player takes an action, display them taking that action, then roll back when you realize they didn't. From your local perspective, it looks like they blocked for a few frames, which makes you assume they're going to block, then they flash back to being defenseless, and your attack weirdly goes through even though you anticipated that it did not.

Even if you can get your fancy neural net to figure out that the enemy is likely to block you - which is a feat worth writing some papers about - you're still going to be wrong about the frame on which they do it. Was their reaction time 160ms? 176ms? 182ms?

If you're right about the action they take and wrong about the frame, that's going to cause each action in the game to have weird timing. You anticipate a block, then it doesn't come so you roll it back, then wait, it actually has come it was just late! The remote player flays around like they don't know what the hell they're doing, and it's not clear to you when you land your hit whether the timer started from when they first telegraphed their block or when the glitch occurred. Your punch appears to land at random.

And blocking is an insignificant action - what if you're playing something like DayZ and the neural net decides that some random other neutral player is likely to try to attack you, say because they happened to mouse over you qucikly.

It looks like they just shot you for a few frames, but weirdly your health goes down and springs back up again, but you're not going to figure out it is the netcode playing tricks on you. Instead you unload your magazine at the other player that's clearly trying to kill you.

And since you are actually shooting now, of course they're going to return fire. Your prediction algorithm just caused two peaceful players to fight to the death.

Just because the algorithm is simple doesn't mean it's possible to do better.

Re: How fighting games use delay-based and rollback netcode (2019)

#42

Post by whateveracct » Sun, Feb 28, 2021, 6:06 AM UTC

enneff wrote: post #37

zucker42 wrote: post #27

Earlier quoted context omitted.

AFAIK they didn't do anything special to save two frames, just a CRT (which is what's used on LAN) has 2 frames of lag.

CRTs don’t traditionally introduce any latency. It’s digital displays like LCDs that use buffers to pre process images and that add latency.

Melee itself has a frame (or two?) of lag due to poor input processing or something.

Re: How fighting games use delay-based and rollback netcode (2019)

#43

Post by whateveracct » Sun, Feb 28, 2021, 6:07 AM UTC

CarVac wrote: post #23

whateveracct wrote: post #16

Earlier quoted context omitted.

The rollback is truly something else. Although - and I may be crazy - I swear it isn't quite as good as playing local people with delay-based netplay (such that the network delay can "hide" behind the inherent lag of the Gamecube/game itself) But outside of that edge case, it's outstanding.

The fact that they were able to optimize two frames of input lag away to make the online gameplay have the same latency as offline is itself incredible. As far as I know, even other rollback-equipped fighting games still add a little bit of latency in order to play online without requiring constant rollbacks. That said, Melee is also a game that is very hard on the rollback, because movement and attack startup are fa…

I play Fox and worry that I jump all over the place.

I play Melee on CRT with my wife all the time. Fox vs Sheik.

Rollback sucks in comparison. Sheik teleports all over the place.

Re: How fighting games use delay-based and rollback netcode (2019)

#44

Post by xeromal » Sun, Feb 28, 2021, 6:14 AM UTC

reitzensteinm wrote: post #32

whateveracct wrote: post #15

Relevant: GGPO, the age-old gold standard of rollback netcode, was recently open-sourced! https://github.com/pond3r/ggpo I haven't used it myself yet - mostly because I'd want Haskell bindings first hah

If your game state is entirely immutable, you're actually most of the way there. I built a rollback multiplayer system in C#, and most of work goes towards having classes that are mutable, but remember their previous state so they can be rewound to any frame in the past second or so. This involves enforcing invariants, persistent collection types, generating code to efficiently walk your entire game state, etc. In Ha…

Did you follow a pattern for recording and tracking those class states? I stick to the business realm of our industry and Iv'e used a pattern called event sourcing that sounds kind of similar. Every update to an entity is an event and you can rewind/fastfoward any entity to a moment in time. It consumes a lot of memory/db space and if you don't snap shot occasionally, it's time consuming to build the events into a model so I'm curious what you use. Might give me some ideas.

Re: How fighting games use delay-based and rollback netcode (2019)

#45

Post by joshspankit » Sun, Feb 28, 2021, 6:21 AM UTC

thewarrior wrote: post #29

This piece was really interesting. That you can hide network delays by building a “fake” model of the other player that replicates what a real player would do and rolling back when this prediction fails. So you can train some neural nets on what players do in such situations and you get a certain accuracy. And yet you can keep making this “fake” player better and better until it’s indistinguishable from fighting a hu…

Makes me even more curious about Stadia’s “button anticipation” code

Re: How fighting games use delay-based and rollback netcode (2019)

#46

Post by reitzensteinm » Sun, Feb 28, 2021, 6:23 AM UTC

xeromal wrote: post #44

reitzensteinm wrote: post #32

Earlier quoted context omitted.

If your game state is entirely immutable, you're actually most of the way there. I built a rollback multiplayer system in C#, and most of work goes towards having classes that are mutable, but remember their previous state so they can be rewound to any frame in the past second or so. This involves enforcing invariants, persistent collection types, generating code to efficiently walk your entire game state, etc. In Ha…

Did you follow a pattern for recording and tracking those class states? I stick to the business realm of our industry and Iv'e used a pattern called event sourcing that sounds kind of similar. Every update to an entity is an event and you can rewind/fastfoward any entity to a moment in time. It consumes a lot of memory/db space and if you don't snap shot occasionally, it's time consuming to build the events into a mo…

Event sourcing is exactly what this is. The game state is built from a combination of initial setup parameters (random seed, level etc), and a list of player inputs.

I snapshot after every recent frame. The snapshots are stored in the game entities themselves via generated code. Each user accessible entity has a bunch of shadow slots it can copy from or write to. Then a higher level system sends each entity commands such as "store your state in slot 5" or "copy slot 3 over your current state".

Old snapshots aren't useful and are discarded. The server itself runs a few seconds behind the client states, does no rewinding, and any player that falls behind that will receive a fresh copy of the server's state.

Re: How fighting games use delay-based and rollback netcode (2019)

#47

Post by shalmanese » Sun, Feb 28, 2021, 6:38 AM UTC

anonymoushn wrote: post #20

shalmanese wrote: post #5

Prediction code for rollback is somewhat akin to branch prediction code in that the dumbest solution works surprisingly well but there's incremental efficiency gains to be had. I wonder if any fighting games have thought to train a neural network per player to try and predict the player's actions N frames ahead. The neural nets could be used for smoother netcode but if the accuracy got high enough, they could, eg: al…

You probably don't want to do this. Players will get quite reasonably upset if the AI predicts thst the opponent will use an attack, so on their screen they hit the opponent out of the attack, then a rollback occurs and the opponent has actually blocked. Some games like Killer Instinct have AIs that learn to play like a certain player. It's pretty cool!

Could be accounted for by having different cost functions for each type of misprediction and heavily penalizing the ones that decrease enjoyment in the game.

Re: How fighting games use delay-based and rollback netcode (2019)

#48

Post by xeromal » Sun, Feb 28, 2021, 6:42 AM UTC

reitzensteinm wrote: post #46

xeromal wrote: post #44

Earlier quoted context omitted.

Did you follow a pattern for recording and tracking those class states? I stick to the business realm of our industry and Iv'e used a pattern called event sourcing that sounds kind of similar. Every update to an entity is an event and you can rewind/fastfoward any entity to a moment in time. It consumes a lot of memory/db space and if you don't snap shot occasionally, it's time consuming to build the events into a mo…

Event sourcing is exactly what this is. The game state is built from a combination of initial setup parameters (random seed, level etc), and a list of player inputs. I snapshot after every recent frame. The snapshots are stored in the game entities themselves via generated code. Each user accessible entity has a bunch of shadow slots it can copy from or write to. Then a higher level system sends each entity commands…

Haha! That's exciting to see something like that shared across industries. I use it for medical health records to ensure we track every single change and know when something changed. Pairs really nicely with dynamodb in aws.

Re: How fighting games use delay-based and rollback netcode (2019)

#49

Post by shalmanese » Sun, Feb 28, 2021, 6:43 AM UTC

thaumasiotes wrote: post #14

shalmanese wrote: post #5

Prediction code for rollback is somewhat akin to branch prediction code in that the dumbest solution works surprisingly well but there's incremental efficiency gains to be had. I wonder if any fighting games have thought to train a neural network per player to try and predict the player's actions N frames ahead. The neural nets could be used for smoother netcode but if the accuracy got high enough, they could, eg: al…

> I wonder if any fighting games have thought to train a neural network per player to try and predict the player's actions N frames ahead. The entire point of playing a fighting game is to attempt to solve this problem. A good player, by necessity, can't be accurately predicted; if they could, they'd be a bad player.

There's only a few key moments where players need to be unpredictable to win a game. Almost all the rest of the time they are executing predictable consequences of those unpredictable choices.

ie: imagine a player running to a ledge spanning a gap. The "naive" interpolation would be they continue running and fall off the ledge and die. A smarter system would realize that almost all the times they've run to the edge of a ledge, they've jumped and the AI could jump for you and then later confirm that prediction was correct. They could even jump at the median of all of your previous jumping choices and then lerp your position over time so you land at the correct point based on your actual jump.

Re: How fighting games use delay-based and rollback netcode (2019)

#50

Post by reitzensteinm » Sun, Feb 28, 2021, 6:56 AM UTC

xeromal wrote: post #48

reitzensteinm wrote: post #46

Earlier quoted context omitted.

Event sourcing is exactly what this is. The game state is built from a combination of initial setup parameters (random seed, level etc), and a list of player inputs. I snapshot after every recent frame. The snapshots are stored in the game entities themselves via generated code. Each user accessible entity has a bunch of shadow slots it can copy from or write to. Then a higher level system sends each entity commands…

Haha! That's exciting to see something like that shared across industries. I use it for medical health records to ensure we track every single change and know when something changed. Pairs really nicely with dynamodb in aws.

I've actually used Datomic to do backend development before, and it's really interesting to contrast two frameworks that are built around very similar ideas, but with vast differences in requirements and implementation.