How fighting games use delay-based and rollback netcode (2019)
ki.infil.net
ki.infil.net
[0]: magazine article by the author of GGPO [pdf] https://drive.google.com/file/d/1cV0fY8e_SC1hIFF5E1rT8XRVRzP...
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.
I didn't mean disappointment that the tech hadn't advanced, I meant that my expectations were set really high by the grandparent comment ("Neural networks? In 2006? Surely not! But it must be something really fancy, judging by all these flowcharts!" [0]) and by how they kept hyping up the "prediction algorithm" for half the article, when it's just
1. take the data you already had
2. (there is no step 2)
[0]: https://drive.google.com/file/d/1cV0fY8e_SC1hIFF5E1rT8XRVRzP...
Think about the time scale under which this prediction is made: 60Hz. Even the best players do not change input at nearly that rate. So it's clear that the current value is going to be the best estimate for the next value. That realization doesn't even begin to solve the problem though!
Predicting right is only important in short bursts at critical moments, and it’s also the hardest to predict and less forgiving moments, so I’d assume being conservative is the more cost effective and pragmatic choice.
For instance, say the local player tries to hit the remote one. If the prediction for the remote player is to evade, the local player can choose to chase him. However if you now rollback and the remote player did not evade but charge in, the local player has been fooled.
Also, don't forget than in these games, input could be polled every 1ms. So a player pressing down "left" for 1s in fact is considered to have 1000 down inputs on left. Since players don't change inputs very fast, just replicating the last input is in fact 99.9% accurate.
Sadly, fighting games, and to the same extent FPS casually break that assumption. 1s is an eternity in a close fight, and players don’t just react, they also read ahead and align inputs based on the situation they expect, regardless of the speed of the game.
Commands will be entered in as low as one to three frames depending on the players, and it will be common to train to do some combos to input them faster. Basically “shooting twice” could actually be “shoot once, go left, go right, shoot again” if doing that has any advantage (canceling the shooting cooldown time for instance). And players don’t do these consistently, or succeed every time.
It’s really complicated :)
This was a pretty obvious result when LinusTechTips did their different frame rate testing in first person shooter games. Higher frame rate benefited worse players more than skilled players. My assumption is that skilled players have learned the pattern. Kind of like martial arts - you practice a flow of moves so that you can execute them without having to think about the next move. (Perhaps this is also how people type very quickly.)
Sure, but that's nothing compared to the speed of just polling inputs.
I would assume a pro player in a fighting game to have what, say 180 APM at peak ?
That's 3 actions per second, so if we assume a uniform holding time and a 60 FPS game that's 1 input change every 20 polled inputs. Assuming repeated inputs does seem like a good strategy in this situation.
An other way of seeing it, is that if a player with 180APM realistically can only change inputs every 333ms, then with a remote input lag of 25ms (50ms ping / 2) there is just a 1/13 chance that an input change would occur in this time slice.
On the 1 change every 20 polls calculation, it’s true locally, but for a ping of 200ms for instance, 333ms of loss is ‘only’ 3 times the one way trip time. I think momentarily losing 3 times the connection speed happens often enough, and of course the bar for losing an actual action due to lag is yet lower for intercontinental games.
https://cns.utexas.edu/news/game-bots-pass-turing-test
"In order to most convincingly mimic as much of the range of human behavior as possible, the team takes a two-pronged approach. Some behavior is modeled directly on previously observed human behavior, while the central battle behaviors are developed through a process called neuroevolution, which runs artificially intelligent neural networks through a survival-of-the-fittest gauntlet that is modeled on the biological process of evolution."
this is not fundamentally different than what we already do in these games though, which is to choose tactics that work to your advantage given how the game deals with lag.
client side hit detection? be the aggressor and do the moving into view and get milliseconds advantage to start shooting.
Why would you waste time trying to shove neural nets into a solution which has such amazing properties? It really terrifies me that that's the first place you went to.
https://github.com/pond3r/ggpo
I haven't used it myself yet - mostly because I'd want Haskell bindings first hah
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 Haskell, you just have a list of game states at the end of every frame, pick what you want and go.
Of course, you're not going to get C# performance this way, but you should still be able to build something pretty advanced if you give it a dedicated CPU core.
There are over a thousand people at this moment playing my indie web games built with rollback networking - if anybody has any questions, happy to answer them!
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.
Event sourcing, at it's core, is making sure your source of truth is a log of events and your app state is derived from that.
Beyond those constraints, there are many variations of how it can be done, each with very different tradeoffs.
But outside of that edge case, it's outstanding.
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 far faster than in many fighting games.
Dashdancing with rollback leads to some annoying camera judder.
They managed to pare it down to only one frame.
I play Melee on CRT with my wife all the time. Fox vs Sheik.
Rollback sucks in comparison. Sheik teleports all over the place.
No, Nintendo famously doesn't bother to understand or pay attention to details like this. Their higher-ups can't be embarrassed because they barely understand the very concept of networking, let alone how it affects their own online multiplayer, let alone the distinction between delay-based and rollback, let alone how such a distinction might manifest in a foreign tournament on the far sign of the world. Nintendo's lawyers, on the other hand, are predictable: advertise anything about a modded game of theirs and the C&Ds come out. It's the same reason they went after Project M.
It's all fun stuff - the dev discord is also open for people who enjoy this kind of stuff, some really knowledgeable people in there.
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: allow for play after one player disconnects, or used to estimate ELO by having the neural nets play each other before the match or be AIs you could play against in offline mode.
In a single-player game you could also create an enemy NPC that uses that same neural net, for sort of a "Dark Link" effect where you have to play against yourself. Would be awesome for chess also.
Lots of possibilities.
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.
Second, your rebuttal is not especially good support for the idea that we should be trying to solve the problem with a technology specifically designed to imitate humans.
The distribution of people who enjoy playing fighting games will probably look somewhat different, though.
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.
I assume the interpolation relates to something displayed on the screen? The idea makes me kind of uncomfortable, because it seems like it would confuse players by causing identical jumps to display different results. If you only learn about jumping by watching the departure point and the landing point, fine, but if part of how you get used to jumping is by watching the animation, this sounds like it could make things a lot harder.
(If the player sees position data calculated locally, and the interpolation is just a process for bringing the remote idea of where the player is into line with the local idea of where he is, that sounds much better.)
It's the equivalent of letting an AI take over the player when the player drops out, with the AI intended to replicate the dropped-player's playstyle until he rejoins. In short enough time-spans (disconnect-duration) you have some hope of being exactly correct.
And if you were 100% correct at predicting the remove player, all of the time, you don't even need the other player --- you could just run the AI and stay offline, and just "pretend" there's another player.
Some games like Killer Instinct have AIs that learn to play like a certain player. It's pretty cool!
To me, having played games with rollback, this takes away one of the key benefits of simplistic rollback: predictability and consistency. Sure it's not the same as offline, but your brain gets pretty good at understanding when it happens and even at predicting it. If an opponent is stationary a few more frames than feels right, or keeps moving, you know to correct for an actions they've already sent - and it's a good estimation most of the time.
Over fitting with neural nets IMO removes this consistency without providing much benefit, plus if you've got a strong neural net you might as well train locally against that first.
For those who want to skip to the code, the article links to these resources:
https://drive.google.com/file/d/1nRa3cRBQmKj0-SEyrT_1VNOkPOJ... - a writeup on the GGPO library including code samples of how it works
For an example of what GGPO feels like when implemented in a game from day one, this Reddit thread illuminates what's possible: https://www.reddit.com/r/Games/comments/lolukg/guilty_gear_s... - "I was playing matches with a friend in Denmark from the east coast of the US without any issues whatsoever. It's like black magic. If this kind of netcode is what we have to look forward to with GGS, I literally won't play any other fighting game that doesn't have it from here on."
Taking a step back from gaming applications though: I'd love to see a convergence between those researching CRDTs and those who have implemented rollback netcode in the wild. This article from September 2020, by one of the contributors to Google Wave back in the day, is a great overview: https://josephg.com/blog/crdts-are-the-future/
There's a fascinating confluence of talents needed to generally solve the problem of "how do you keep people in a flow-state when collaborating in the presence of network delay" - which is more applicable now than ever. There's psychology, user experience design, user interface design, deep domain knowledge, fundamental CRDT research, the types of artistry that go into really good gaming netcode, people who have implemented undo stacks in massive desktop applications and know all the warts that arise there, security researchers, distributed systems researchers (the latter two because this will enable decentralized applications in a huge way)... All these people will come together in the coming years to make computing seemingly defy the laws of physics. It's an exciting time to be a software engineer.
8 Frames in 16ms: Rollback Networking in Mortal Kombat and Injustice 2 https://www.youtube.com/watch?v=7jb0FOcImdg
One of my favorite topics, partially because there's not that much literature on the subject but it's so important
This is actually the topic of a degree project I've been working on for the past year, and I hope to finalize the report next month and publish the code on github soon. The tldr is that it seems to take a lot of additional complexity for the improvement you get, and it is currently unknown how "false positive" predictions (ie when the model predicts a new buttonpress that doesn't happen) affect the user experience (but intuitively it seems like it would be worse than the false negatives we currently experience). In other words, we don't know if it would actually feel any better to play even if, say, the prediction accuracy is slightly higher. That said, this is only a first attempt and who knows how much it could be improved.
I'll probably post more about it as @zeknife on twitter next month.
[1]https://www.nintendoenthusiast.com/knockout-city-is-the-wild... (only mentioned in one sentence)
For example, game rules state a player can only make a move when opponents is in state A. Local player sees a prediction of Remote player in state A and executes the move, but really the player was in state B. When the rollback happens, there is an illegal game state of local player executing the move against opponent in state B.
The situation is similar to a write-write conflict in a multi-leader DB.
> Good netcode matters, period. So let’s talk about it.
Because at that point I didn't read anything about netcode, except how important it is.
Without being any less subtle, games like Apex Legends is known for really bad server performance, latency, and among other things.
Prior to this article, I've suspected there was some sort of predictive algorithm that helps make things smooth overall. I've noticed on a few occasions, I'll get shot by someone pre-firing a corner I haven't gone around yet (like sprinting to a corner to make a play). Several times, the kill cam has shown me fully around the corner for the other player.
I also have poor latency (my ISP routes poorly) and playing with friends that are geographically far - with servers even further away from me (though relatively close to them). It's a bummer that it happens, but I'm up to 200ms behind realtime. I suspect the game is predicting my movements - some of which put me in very bad positions, unintentionally.
It results in the usual problems (peeker's advantage and being teleported backwards when a high-ping player kills you while you are moving) though it is not obvious how you can work around these.
I think as long as a term has a relatively unambiguous Google result (which is true in this case), it’s fair game to be used in public texts.
> Ricky "Infil" Pusch is a long-time fighting game fan and content creator. He wrote The Complete Killer Instinct Guide, an interactive and comprehensive website for learning about Killer Instinct. This article was originally published there. - ArsTechnica
Both sites clearly reference where the original source came from. Nothing has been stolen.