How we solved an infamous sliding bug | Hacker News Reader

How we solved an infamous sliding bug

joostdevblog.blogspot.nl

65 pointsexch22 comments

Problem: Lag + collision detection = characters slide. Solution: Turn off collision detection.

I was sincerely hoping for an actual technical solution for dealing with peer-to-peer networking and lag. I feel somewhat cheated out of the time it took me to read that article. While it did explain the problem very nicely, the solution was to just disable the feature outright.

Well, the first paragraph did say

> The solution we finally managed to come up with is also a good example of how very incorrect workarounds can actually be a really good solution to a complex problem.

So you knew they were presenting a "very incorrect workaround"---which, counterintuitively, worked better than some of the more "correct" things they tried.

>So you knew they were presenting a "very incorrect workaround"

It actually made it a bit more enticing, I was expecting a horrific chain of gotos or some other cliche programming paradigm being completely violated for the sake of pragmatism.

What we got instead was, "This is a hard problem, let's just not solve it." which was written up with a title of "How we solved a hard problem"

They did solve the problem, the solution was to turn of collision detection.

> While it did explain the problem very nicely, the solution was to just disable the feature outright.

To be fair, they did solve the problem. If it isn't noticeable during gameplay and doesn't create unwanted degenerate actions from players, they succeeded in fixing the bug, even if the technical aspect is simple.

How do you stop clients from cheating in a peer-to-peer game like Awesomenauts?

You probably can't. If stopping cheating is a goal you need to go for client-server were you host the servers yourself. A lot of developers are not prepared to take that on.

In many RTS peer-2-peer games like Starcraft or Age of Empires, they use a lock-step model, which can stop the majority of cheating.

Every player uses a tick-engine (ie tick every 0.1s) that performs the same commands on the same ticks. When a player issues a command, such as "Build Unit X", it sends it to every other player to run a couple ticks ahead (how far ahead is based on average lag or whatever). If anyone performs differently, then a de-synchronization occurs and the game is over.

It's explained much better here http://www.gamasutra.com/view/feature/3094/1500_archers_on_a... "Because the game's outcome depended on all of the users executing exactly the same simulation, it was extremely difficult to hack a client (or client communication stream) and cheat. Any simulation that ran differently was tagged as "out of sync" and the game stopped. Cheating to reveal information locally was still possible, but these few leaks were relatively easy to secure in subsequent patches and revisions. Security was a huge win. "

Your assertion that a game like Starcraft is built such that it makes cheating difficult is unfounded. Because Starcraft players both synchronize the full state of the game, even what's in the fog of war to your opponent means that cheating is trivial. There are some trivial countermeasures here where if the two simulations differ it the two machines will quit over the desynchronization, so you can't just spawn a million units, but you can have full map vision in a game whose rules are tied strongly to the notion of imperfect knowledge of the board.

I've worked anti-cheat (and written cheats) for several games, and there's little you can do in the space of 1-on-1 games to prevent cheating(1), but in the space of 3+ player games the separate simulations can "vote" to remove the player who is cheating (in the desynchronization fashion as above), if you assume there are going to be fewer cheaters in games than legitimate players. Of course if there is any knowledge hidden by the client in its render/UI of the game then a cheater can always recover that data, which is why when you can build a client/server model not transmitting hidden data is the most effective strategy to counter cheating (for example don't transmit entities the player shouldn't be able to see.) This is often difficult, of course, for example if you want footstep sounds to travel through walls in an FPS, but a lot of low-hanging fruit that cheaters would want can be pruned that way.

1: The other (common) approaches are to detect the cheats and punish the cheaters afterwards (Punkbuster, Valve Anti-Cheat, Warden, etc.) or try to lock down the process and make it difficult to write effective cheats (GameGuard, or one trick Blizzard does is attach a second process as a debugger of the game process and IPC validation checks so you can't directly/easily hook into the main process.)

Edit: I now realize you mention hidden data still being recoverable, and desynchronization as a method to combat cheating, I missed that at first but figure I'll leave my post up anyways, even if only to emphasize that seeing the whole map is a very valuable cheat that has taken players easily into the top of the Starcraft ladder (and the top of the Grandmaster rank in Starcraft 2).

But multiplayer RTS games are notoriously easy to cheat in. Cheating is extremely common in Starcraft 2, and as far as I know, the only way Blizzard combats it is to detect unauthorized behavior and ban those accounts.

This is the first time (as a non game-dev) I'm reading about a P2P game where each peer computes only part of the world. That's quite clever, especially for an indie developer who'd be hurt more by spending lots of money on server resources. It should be possible to build quite massive multiplayer worlds this way. Has this ever been attempted, say, in a WoW or Eve type game? I imagine that for massive battles, each peer could serve as a proxy for all the data it has received already, such that only one connection to another peer is needed to see the whole thing - similar to how bit torrent works. Lag could become a larger problem there of course, so it probably only lends itself to a slower paced gameplay where players don't target each other using a visor - but it should work for a WoW style combat system, no?

It seems like this solution implicitly acknowledges (and fails to resolve) the fact that their game has frequent, pervasive desyncs. The bug being described is only possible when in a state of persistent desync - that's a little scary in a competitive or semi-competitive game (like most games in the 'MOBA' genre are, including Awesomenauts).

I wonder what their reasons were for going with peer-to-peer instead of anointing a player as the 'server' as many other console multiplayer games do (Awesomenauts started out on console, IIRC)? That would solve a lot of these desync problems because the server would be responsible for resolving all the collisions.

I guess the reason is "character control is super fast: your computer can execute button presses immediately and there is no lag involved in your own controls"

Unless you run in lockstep, your distributed game is always in a persistent state of desync. It's probably more fair for both players to be desynced equally, than to let one player be synced perfectly with the server, and the other be subject to latency issues.

Would it work to have a different response to collision, namely to apply a reverse of your last step? (A full reverse or partial).

There might still be corner cases, but it would seem to resolve the described issue, since irrespective of where you think the other player is, if you both reverse your motion you should disengage.

I can see 3-body problems being more problematic, but that's probably also the case with the original code.

With their example code if lonestar is walking to the right and froggy precives that they land on the right side of lonestar, but lonestar precives that they landed on the left of them, then they would both slide to the left if they just undid their last step.

Yes, and that would make it so they would not collide anymore, so I'd be interested to know why they did not use that solution. Probably it would also give a wrong feel in gameplay.

If they both slide to the left then they would still be in a collision.

Okay, because of lag they might have to retrace more than one step. But eventually, they would have gone "back in time" enough to disentangle, regardless of their direction.

How does the player with the lower objectID detect that the sliding bug is happening? The way it was described, only the player with the higher objectID would be able to figure that out. Did they change it so both players sends the message? Or does the player with the higher objectID simply send a message when they detect the bug, meaning they turn off their collision first? Or something else entirely?

> How does the player with the lower objectID detect that the sliding bug is happening?

In the original version only the higher objectID would react and disable his collision, thus not requiring the lower objectID to detect the problem.

It is not called out, but it looks like they not have both sides call out when a collision occurs, allowing both to turn off in this case.

So the collision occurs, both say "I am going right" and when they hear the other one doing the same they both stop.

Could you resolve the issue by introducing an element of stochasticity into the distance players are displaced to avoid collisions?

That way, one player would move right (or left) more than the other player and the collision would still resolve itself.

Reply on news.ycombinator.com