Following is an excerpt from GDAlgorithms-list (http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list) ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: [Algorithms] Network console game/distributed object strategies Date: Wed, 2 Apr 2003 16:43:58 -0800 Hello all, Just curious as to how people are managing network console games these days- Not so much a focus on security, but more fundamentally the concept of distributed object management & simulation. I've read Tim Sweeney's Unreal network manifesto (http://unreal.epicgames.com/Network.htm) and it seems very good (and obviously successfully field-tested), but I was wondering if anyone has toyed with the idea of decentralizing the game a little bit. Say I'm a client in a network game and I have the sniper rifle. You (my intended victim) know that I'm sniping _at_ you, but you don't know exactly where I'm shooting. With my skill, I pull the trigger right when your head is targeted in my sights, even though you're running full-tilt perpendicular to my aim vector. Do I get the kill? Anyone who's played even a _slightly_ laggy game of unreal/quake knows that the answer is a resounding NO. The way they work, it takes some amount of time to send the "I'm shooting this way with the rifle" packet to the server, who does the local simulation decision, and then reports back to you that you missed. This forces would-be snipers to learn how to 'lead' their victims with respect to ping/latency. Sniping another player's head seems like a heavily weighted action. By that I mean that the player who pulled the trigger has overwhelmingly more 'simulation information' than the player who's simply watching sniper rifle tracers zing by his/her head. Intuitively, I also feel that the player who has the skill to line up the sniper bead on their target's head "deserves" the shot, and that as a local client I can authoritatively say that this happened. Of course, there are tons of problems with this. What about laggy connections? If network proxy players are using dead-reckoning or spline extrapolation to figure out where they are between authoritative server updates, then their motion between updates is very smooth and predictable. Fine, so if another player is laggy, give the kill to the shooter. But what if the shooter is laggy? By not hearing from the server, it's not going to hear an update that the targeted player juked out of the way and will accordingly assume (by the local simulation) that the sniper shot hit home. Subsequently, an "I shot this player in the head with the rifle" packet will be queued up and reliably sent to the server.... Eventually. A cheater could even rig up a hypothetical 'kill-switch' to their controller that, while hit, disables the ethernet connection. Start sniping, hit the button, watch everyone slip into dead-reckoning mode, start killing, let go of the kill-switch, watch them drop. What about hacks? Are PS2/Xbox hacks common these days? Are we at the tips of a wide-spread cheating epidemic? Cheating completely breaks the fun of a network game. It seems dangerous to have the sniper console be able to authoritatively say "YES, I KILLED THAT PLAYER"- like it's begging for a man-in-the-middle helper or some such. I remember just a few days ago people here talking about PSO-Xbox already being hacked. That sucks. :( The underlying problem is that every console is responsible for at least one integral actor in the distributed simulation, and that the actions between these actors overlap. Most solutions work _great_ when latency gets low enough (i.e. LAN Halo/Quake/Unreal) because there's never enough 'dead-time' for quirks to make a difference, but what approaches are people taking to keep the game A. Responsive- I fully expect to see the effects of my button mashing instantly (turning/moving) B. Solid/Real- I expect my actions to act on other actors in the game (head-shot sniping without leading) when the latency kicks up and you hit the internet cloud? I know there's no silver bullet for network latency, but the only text I've seen on this is Sweeney's. I'm curious to know how other people are dealing with this high-level issue. TIA for all responses/corrections/advice. Regards, charles nicholson ================================================================================ From: "Research \(GameBrains\)" (research^gamebrains.com) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 10:09:11 +0800 As everyone has said, and will say, authoritative clients just doesn't work on any platform. Console cheating isn't as hard as it seems at first glance either. With a combination of prediction and smoothed syncronization, lag isn't really the issue I feel, especially for action-oriented console titles (that only come with broadband adapters, sold to primarily US customers with decent connections). The combination of recoil from your sniper rifle, the large ratio of thumb to cursor movement on consoles, and the fact that the guy ran full tilt across the screen means the player won't feel cheated if they miss as they have no clear vision, sitting across the room of whether it should have hit or not. At any rate, I doubt they will moan they missed that shot due to lag! For the record, I have a 10 foot, hi-res projection TV and sit about 8 feet in front of it so it's huge and it is far less clear what precisely is happening on screen when compared to 1024 x 768 (or higher) LCD PC screen where you can see so much unsaturated detail. The real work to be done on multiplayer FPS console simulations is getting the controls to feel right. There still hasn't been a FPS on consoles that even comes close to how a PC plays. Also, "chat" without a keyboard is an excercise in futility. These two issues alone are a far more serious problem on consoles than lag in my opinion. Would you rather play an FPS on PC with 500 ms lag or on a console with 250 ms lag? If money is at stake, I'll choose the PC because although it's laggy, I'll win because you'll have more difficulty killing me on a console than I will with a laggy PC, and once I kill you I'll be chatting up a storm about how I wasted you while you sit by idly. In the future, all consoles will come with headsets and perhaps keyboards, but until then if your game is mass market you should focus on playability. You'll sell more games :-) Cheers, Brett ================================================================================ From: "Research \(GameBrains\)" (research^gamebrains.com) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 10:22:11 +0800 Gamasutra just released an article on online gaming for consoles you might be interested in if you haven't seen it already. http://www.gamasutra.com/features/20030328/isensee_01.shtml ================================================================================ From: (arQon^promode.org) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Wed, 2 Apr 2003 19:17:42 -0800 >I've read Tim Sweeney's Unreal network manifesto >(http://unreal.epicgames.com/Network.htm) and it seems very good (and >obviously successfully field-tested) Not for nothing, but the UT2K3 netcode is generally regarded as among the worst ever made for an FPS. (My personal take is that the real problem is actually elsewhere, given that a perfect shot on a stationary target on LAN is also unreliable, but I thought I'd mention it). >This forces would-be snipers to learn how >to 'lead' their victims with respect to ping/latency. Among serious gamers, this is considered a skill. For Joe Newbie though, it is indeed annoying and frustrating: hence CS/ZPM/etc/etc hacks. >Intuitively, I also feel >that the player who has the skill to line up the sniper bead on their >target's head "deserves" the shot, and that as a local client I can >authoritatively say that this happened. And of course, that's where you're wrong. :) The piece that you're missing is that the OTHER player is continuing to move during this time, because YOUR information is just as outdated as the lag TO the server that you think is unfair. For all you know, he's dodged (or even teleported/translocated in some games) in that time. You're robbing Peter to pay Paul, as they say. >A cheater could even rig up a hypothetical >'kill-switch' to their controller that, while hit, disables the ethernet >connection. Start sniping, hit the button, watch everyone slip into >dead-reckoning mode, start killing, let go of the kill-switch, watch >them drop. Actually, this was a very popular trick in ZPM. :) >what approaches are people taking to keep the game > >A. Responsive- I fully expect to see the effects of my button mashing >instantly (turning/moving) You can always predict client movement perfectly provided there are no external forces at work: the problem cases come when you've been affected by some form of knockback (i.e. a shot), collided with another player, etc. The standard response in those cases is to accept the new position instantly (so that you don't continue to mispredict) but blend the VIEW transition over a small number of frames to make it less jarring. >B. Solid/Real- I expect my actions to act on other actors in the game >(head-shot sniping without leading) Then you need to use CS-style hackij, and penalise the target (who can't possibly compensate with skill) rather than the shooter (who potentially can). >I know there's no silver bullet for network latency Good. :) >but the only text I've seen on this is Sweeney's. >I'm curious to know how other people are dealing with this high-level >issue. This has been covered a fair bit by Yahn Bernier, myself, and at least a dozen others in the past few years. Google should find enough of it to give you a decent background. The key thing to remember is that whichever option you choose, someone gets screwed. Stick it on a post-it on your monitor; tattoo it on your arm; but keep repeating it until you understand that it is a fundamental truth: SOMEONE ALWAYS GETS SCREWED. :) Now, WHO you chose to penalise really depends on your target audience and your gameplay. "Serious" gamers generally prefer to accept the lag and deal with it, but they're a small minority; casual ones prefer to accept the artefacts in return for lower skill demands, and they're massively the majority. If your game is predominantly hitscan weaponry (CS and clones) and especially if those weapons have a built-in "luck" factor (random spread etc: again, CS and clones) then the CS approach works extremely well (as you'd hope :P). If you have significant projectile weapon use however, the CS approach is extremely undesirable as you either give players conflicting perceptions of lag (hitscans are hacked, proj are not) or very unpleasant side-effects if you attempt to compensate proj as well (the target sees the proj/explosion a safe distance away, but takes damage because you just teleported him back 4ft). It is, frankly, a sucky problem. :P You can balance the tradeoffs by clamping the amount (i.e. time) of hackage that you're willing to backwards-reconcile (this is essentially what we've done in competitive Q3/RTCW, and seems to make most people happy). Your goal should be to try and make BOTH players' views as "real" and consistent as possible: right now, you're only looking at it from one side. K ================================================================================ From: Jay Stelly (Jay^valvesoftware.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Wed, 2 Apr 2003 19:33:09 -0800 > This has been covered a fair bit by Yahn Bernier, myself, and > at least a dozen others in the past few years. Google should > find enough of it to give you a decent background. I'm surprised the original poster hasn't come across at least one of Yahn's articles on networking. The one most relevant to this question is available online here: http://www.gdconf.com/archives/2001/bernier.doc For more info on how Counter-Strike deals with client/server authority and prediction, do a google search on "lag compensation." Jay ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 11:19:43 -0800 > It is, frankly, a sucky problem. :P > You can balance the tradeoffs by clamping the amount (i.e. time) > of hackage that you're willing to backwards-reconcile (this is > essentially what we've done in competitive Q3/RTCW, and seems to > make most people happy). Your goal should be to try and make BOTH > players' views as "real" and consistent as possible: right now, > you're only looking at it from one side. I'd like to second this approach. You save some amount of historical state, and when you're asked to hit test something at time X, you hit test against your saved state at that time, not at the current time. If you're asked to hit test at a time that's further in the past than you keep state, you claim it missed. This still allows "time warp" cheats for people with fast connections; they can time warp an amount that's the size of your total window, minus their own "ping time". You might want to measure the ping time between all nodes and reduce the window to the maximum data point (plus a small slop). Once the amount of state you need to save becomes big, and/or the amount of lag you want to compensate for becomes long, the size of your saved state may become unwieldy on memory-starved consoles, so you may need to start doing more involved things to compress state, but the basic strategy is sound (well, works for us :-) Cheers, / h+ ================================================================================ From: "Chris Butcher \(BUNGIE\)" (cbutcher^microsoft.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 17:53:45 -0800 > Jon Watte wrote: > > I'd like to second this approach. You save some amount of historical > state, and when you're asked to hit test something at time X, you > hit test against your saved state at that time, not at the current > time. If you're asked to hit test at a time that's further in the > past than you keep state, you claim it missed. > > This still allows "time warp" cheats for people with fast connections; > they can time warp an amount that's the size of your total window, > minus their own "ping time". You might want to measure the ping time > between all nodes and reduce the window to the maximum data point > (plus a small slop). > > Once the amount of state you need to save becomes big, and/or the > amount of lag you want to compensate for becomes long, the size of > your saved state may become unwieldy on memory-starved consoles, so > you may need to start doing more involved things to compress state, > but the basic strategy is sound (well, works for us :-) > This is all well and good, but it seems to me that you're sidestepping the really hard problem here, which is: How do you know what was on the client's screen when they fired? You can know what data you had sent them (if they tell you the last packet they received), but you can't know what packets prior to that they actually received successfully and hence you can't know what frames they were actually interpolating between. My $0.02 is that a better approach than doing the test against the server's authoritative position at that frame is to have the client send more data. For example, "This is what I thought my avatar's state was (position etc), this is the action I undertook, and this is what I thought the relevant world state was (target object position etc)." Then the authoritative remote machine must check that: 1) under the reported conditions, would the action succeed? 2) did the reported conditions "match" the real authoritative conditions? This is a generalization of the Counterstrike-like lag compensation strategy, and it allows for a wider spectrum between (less satisfying, more accurate) and (more satisfying, prone to exploitation). I think broadband gaming on a fixed console hardware platform (i.e. what we're doing) should err more towards the fuzzy side. -- Chris Butcher Rendering & Simulation Lead Halo 2 | Bungie Studios (butcher^bungie.com) ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 18:15:11 -0800 > How do you know what was on the client's screen when they fired? You > can know what data you had sent them (if they tell you the last packet > they received), but you can't know what packets prior to that they > actually received successfully and hence you can't know what frames they > were actually interpolating between. You don't. Thus, if a client is shooting at what looks like a person, but that is empty air, then the client will miss. Someone is authoritative for shots against character X, and only that someone should decide if character X gets hit. You could, alternatively, decide that character Y is authoritative for what he shoots. At that point, client-side hit detection is all fine and dandy, and there's no problem. Except for the cheats ;-) In my mind, there really isn't any other way to do this. Someone always gets screwed. Might as well be the one guy who had a packet drop right before shooting, rather than everyone else. > My $0.02 is that a better approach than doing the test against the > server's authoritative position at that frame is to have the client send > more data. For example, "This is what I thought my avatar's state was > (position etc), this is the action I undertook, and this is what I > thought the relevant world state was (target object position etc)." > > Then the authoritative remote machine must check that: > 1) under the reported conditions, would the action succeed? > 2) did the reported conditions "match" the real authoritative > conditions? > > This is a generalization of the Counterstrike-like lag compensation > strategy, and it allows for a wider spectrum between (less satisfying, > more accurate) and (more satisfying, prone to exploitation). I think > broadband gaming on a fixed console hardware platform (i.e. what we're > doing) should err more towards the fuzzy side. I don't understand 2). If it matches, then why would the client have to do the detection at all? If client matches server, then server can make the determination without explicitly being told what the client state was. Thus, client needs to send no state. If it doesn't match, then what do you do? If you still accept the hit, then you're letting the client do the hit test, and you might as well send the single bit that the client thought it hit. If you don't accept the hit, well, then you're back at server being authoritative. Perhaps there is a third case I'm missing here? Cheers, / h+ ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 18:21:32 -0800 > My $0.02 is that a better approach than doing the test > against the server's authoritative position at that frame is > to have the client send more data. For example, "This is what > I thought my avatar's state was (position etc), this is the > action I undertook, and this is what I thought the relevant > world state was (target object position etc)." > > Then the authoritative remote machine must check that: > 1) under the reported conditions, would the action succeed? > 2) did the reported conditions "match" the real authoritative > conditions? How would this new information help the server make the decision 'better'? I mean, say the server receives a packet from the client saying "at this time, I shot this guy in the head with the sniper rifle". It time-travels back to when the packet was approximately sent (based on the client's latency), and determines whether or not the head shot was actually possible? Isn't that the same as actually doing the CS-style time-rewind ray test anyway, or are you implying that there should be some 'maybe-it-was-possible' threshold in which the ray was 'close enough' to the target's head at that instant in time? If not, then why does the server need where you thought the target was? If the server is rewinding time, then hopefully the target will be somewhere near where you thought it was anyway, and wouldn't need your guess as to where it was (because the server 'knew'). > This is a generalization of the Counterstrike-like lag > compensation strategy, and it allows for a wider spectrum > between (less satisfying, more accurate) and (more > satisfying, prone to exploitation). I think broadband gaming > on a fixed console hardware platform (i.e. what we're > doing) should err more towards the fuzzy side. It seems that if this is the approach, then the server is no longer the primary owner of the simulation- that it becomes 'fuzzy' as you mentioned. What are the implications of this? Also, on a related note, are there any good approaches to non-relative objects like projectiles? Bernier's paper mentions that projectiles become a bit of a mess because they exist in absolute time (i.e. aren't 'owned' by any particular user) BTW, I'm not criticizing- I'm na=EFve and curious. We're ramping up on this and I'm trying to learn as much as possible about it before making potential blunders. Regards, charles nicholson ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 18:40:28 -0800 > You don't. Thus, if a client is shooting at what looks like a person, > but that is empty air, then the client will miss. Someone is > authoritative > for shots against character X, and only that someone should decide if > character X gets hit. You could, alternatively, decide that > character Y > is authoritative for what he shoots. At that point, client-side hit > detection is all fine and dandy, and there's no problem. > Except for the > cheats ;-) How bad are the console cheats these days? I mean, I thought the major large private online console service had angry encryption (~80 bytes per packet overhead)- you'd need some computer sitting on your subnet faking encrypted packets with spoofed "I shot your face" info to really manipulate the game... Are there any gameshark onboard hacks for online console games? (I'm disregarding the PSO hack, as that involved a save-game file exploit.) I'd imagine that it would be possible on a LAN game, but presumably you're only LAN-ing with trusted peers... ("Who are you? What's that computer doing in my living room?") Obviously cheating is prolific in online PC games, but how much of this exists on the consoles? Is it something we have to worry about for an all-platform console game? What about 3rd-party lobby/global ID services? A weak part of me is tempted to just say "screw it, anyone smart enough to hack it deserves the free kills and godlike status", but that's obviously less than an optimal solution... ;-) So once again, as soon as the client is authoritative, the cheaters make the game suck. charles nicholson ================================================================================ From: "Conor Stokes" (cstokes^tpgi.com.au) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 11:12:13 +0800 > Obviously cheating is prolific in online PC games, but how much of this > exists on the consoles? Is it something we have to worry about for an > all-platform console game? What about 3rd-party lobby/global ID > services? A weak part of me is tempted to just say "screw it, anyone > smart enough to hack it deserves the free kills and godlike status", but > that's obviously less than an optimal solution... ;-) So once again, as > soon as the client is authoritative, the cheaters make the game suck. I think the varying between client and server authoritive based on how good the player is seems reasonable. If your client is doing well, or people initiate a "cheat" vote against him (above certain params), you bump to more server authoritive. If a player is doing unnaturally well on his own skills, that little extra lag penalty will even up the game a bit :) Conor Stokes ================================================================================ From: "Research \(GameBrains\)" (research^gamebrains.com) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 11:50:32 +0800 Charles, How about a console connected to the net via an intermediate PC with two NICs installed? The way it works is that there is a driver with built-in packet sniffer running on the PC that communicates to a simple app that allows you to set rules for what packets to look for and the rules applied to them. The app needs to know the encryption your using and the key to work, but not an impossibility to obtain and in fact easy in some cases. It just sits there watching the traffic going and coming and if it sees one of interest it stops it and modifies it in place. So it could find outgoing position, aiming, firing packets and apply rulles like "90% of the time aim perfect", whatever. Because it sits on the network and looks at traffic, this type of packet-sniff-and-modify toolkit can be used with any device including consoles, PCs, etc. Very easy to imagine homes with both a PC and a console and an extra network card laying around. It is easy to install, easy to use and requires no modifications of the player's equipment. Or how about a combined piracy/enhancement hack? In this case the hackers take your game and patch it (like PC cracks) but they then _add_ code to either automatically cheat or even offer a custom menu to choose cheat options, then upload it to the net as an ISO image that can be downloaded and burned with Nero or Easy CD Creator to CD-R and ran on a chipped console. You get pirated and cheated both. I have actually seen an example of this running before, although it didn't work well. But that was two years ago, I can only imagine how much more saavy they have become now that more info is available about the hardware. Console cheating is a real problem, small now but growing. Brett ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Thu, 3 Apr 2003 21:28:32 -0800 > How bad are the console cheats these days? I mean, I thought the major > large private online console service had angry encryption (~80 bytes per > packet overhead)- you'd need some computer sitting on your subnet faking > encrypted packets with spoofed "I shot your face" info to really The cryptography in the X-box is actually fairly high-class. It'd be hard to write a generally useful man-in-the-middle agent such as an aim bot for an X-box Live! game. If you're on another console, you'd probably be able to construct the same level of security yourself, or perhaps buy it from someone. But... There are tools to flash the X-box bios, FTP into the machine, copy the contents of a DVD to hard disk (maybe a hard disk you added to your X-box as an F: drive), crack open the XBE files on your PC hard disk, re-generate an XBE from files on hard disk, re-upload to boxes, burn user DVDs, set flags that allow running from any media, blah blah blah. I would assume that my executable, running on the client, is cracked. But that's just me. If you think otherwise, do a google for "mod chip copy games" or perhaps "xbox retail recover bios". I'm assuming you're talking about X-box, because they have the tightest integrated online service for now. The overhead of Xbox networking is nowhere near 80 bytes per packet (but it's also not 0, btw :-) > services? A weak part of me is tempted to just say "screw it, anyone > smart enough to hack it deserves the free kills and godlike status", but > that's obviously less than an optimal solution... ;-) So once again, as > soon as the client is authoritative, the cheaters make the game suck. What you really are saying is: "anyone who can download a pre-packaged, scripted solution from the web is getting the free kills, and users will think my game sucks," unfortunately. Running servers is very expensive, though, so you're better off if you can get away with peer-to-peer. (There are possible solutions to the NAT problem, too). If you're using a matchmaking service that allows you to store metadata (also known as "high scores" :-) about players, then you can detect which players seem to cause more network mis- matches, and not let them host games. Cheers, / h+ ================================================================================ From: Christopher Phillips (cphillips^reflectionsinteractive.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 12:35:53 +0100 > Perhaps there is a third case I'm missing here? (I'm assuming here that server->client world state update packets are allowed to be lost, but client->server packets are reliable) How about client says 'these are the packets I've recieved from you that I'm basing my interpolation on'. Very little extra data to send back, then the server can make it's authorative decision based on the same information that was used to display the player's victim dead in the middle of their crosshairs. I would prefer to die unexpectedly from time to time than to be denied hits I 'know' I should have got.. ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 09:49:35 -0800 > I think the varying between client and server authoritive > based on how good the player is seems reasonable. If your > client is doing well, or people initiate a "cheat" vote > against him (above certain params), you bump to more server > authoritive. If a player is doing unnaturally well on his own > skills, that little extra lag penalty will even up the game a bit :) > > Conor Stokes That sounds to me like a really bad idea. You're increasing the complexity of the code by dynamically shifting authoritativeness from client to server and back in real-time using fuzzy heuristics (which themselves are a pain to define- how good is "too" good?). You're also forcibly flattening out the skill range of players by granting advantages to worse players. That doesn't sound like fun to me- if I spent 80 hours becoming FANTASTIC at a game, I don't want to be artificially punished because I mop up the Noobs.... charles nicholson ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 10:19:15 -0800 > (I'm assuming here that server->client world state update packets are > allowed to be lost, but client->server packets are reliable) Of course client->server is not reliable. That's why you get lag-jumping on your own client. Unless you want the client to be authoritative about its own position, which seems like a bad idea from a cheating perspective. > How about client says 'these are the packets I've recieved from > you that I'm > basing my interpolation on'. Very little extra data to send That would work, but it would cause significant amounts of re-simulation on the server for each shot. On a console peer-to- peer set-up, one of the consoles is also the server (or, perhaps, all of them are, if you're in a N:N topology). I find it unlikely that the server console has the oomph to re-simulate back half a second, taking into effect dropped packets, for all of the clients that happen to be shooting at some particular step. Think "rail guns". Now, if it could be done, it'd probably work very well, except for the parts where a player teleport packet gets lost, so that the shooter shoots a player he sees, but the shot player gets hit at some totally random location after the teleport. > I would prefer to die unexpectedly from time to time than to be > denied hits I 'know' I should have got.. Fix the CPU load from re-simulation, and you'd be able to get that. If you don't have the CPU to spare, I think that basing all decisions on authoritative information is the best choice. Cheers, / h+ ================================================================================ From: "Michael Pohoreski" (MPohoreski^cyberlore.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 13:25:17 -0500 Yes, but if the game becomes a "tad" harder for you, and a little easier for the casual gamer, you're maximizing the fun for more people. Slaughter noobs left, right, and center doesn't retain the fun factor, because it's no longer challenging. "Noobs" don't like playing a game where they are constantly being wasted by the more skilled players. I know quite a few people that just give up on the game when that happens. ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 10:38:50 -0800 Well, right, but hopefully that's where good lobby services would come in handy. If i'm creating a game, i could say "Experts game, beware!" or "We're a bunch of beginners!" and then people would bucket themselves accordingly. This is how Warcraft 2 worked online... regards, charles nicholson ================================================================================ From: Peter Cowderoy (psycho^petercowderoy.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 20:03:51 +0100 (GMT Daylight Time) On Fri, 4 Apr 2003, Charles Nicholson wrote: > Well, right, but hopefully that's where good lobby services would come > in handy. If i'm creating a game, i could say "Experts game, beware!" > or "We're a bunch of beginners!" and then people would bucket themselves > accordingly. This is how Warcraft 2 worked online... And it tends to create a big problem for players who're good enough to crap on newbies without having practiced any but don't put in the time to become real experts early on. You have real problems when you try to define "intermediate" or "beginner but competant"... -- (psycho^petercowderoy.org) ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 10:56:40 -0800 > > (I'm assuming here that server->client world state update packets are > > allowed to be lost, but client->server packets are reliable) > > Of course client->server is not reliable. That's why you get > lag-jumping on your own client. Unless you want the client to > be authoritative about its own position, which seems like a > bad idea from a cheating perspective. Well, we've divided all network content into reliable & unreliable. Right now, it's looking like pretty much everything is reliable EXCEPT for actor location data. I really don't want those to stall because one dropped and I'm waiting for rexmission... > > How about client says 'these are the packets I've recieved from you > > that I'm basing my interpolation on'. Very little extra data to send > > That would work, but it would cause significant amounts of > re-simulation on the server for each shot. On a console > peer-to- peer set-up, one of the consoles is also the server > (or, perhaps, all of them are, if you're in a N:N topology). > I find it unlikely > that the server console has the oomph to re-simulate back half a > second, taking into effect dropped packets, for all of the > clients that happen to be shooting at some particular step. > Think "rail guns". That doesn't seem like a deal-breaker to me, just because the "time-shifting" algorithm seems equivalent to interpolating an animation position between keyframes. You have some "keyframes", which are location packet updates, so you just find the two between which the event took place and interpolate a location for every actor. Simulate the shot and be done with it. If you have 16 players tops, that doesn't sound too bad. You could potentially incorporate your visibility culling into it as well, if there's no potential visibility between the shooter and a potential target, don't bother testing. This is all off the top of my head. > Now, if it could be done, it'd probably work very well, except > for the parts where a player teleport packet gets lost, so that > the shooter shoots a player he sees, but the shot player gets > hit at some totally random location after the teleport. Player teleport packets are reliable and must arrive in-order. If the contest between "I shot you!" and "I teleported!" is that close, then I can't see any obvious solution. This happens in counterstrike when you get shot around corners. > > I would prefer to die unexpectedly from time to time than to be > > denied hits I 'know' I should have got.. > > Fix the CPU load from re-simulation, and you'd be able to get > that. If you don't have the CPU to spare, I think that basing all > decisions on authoritative information is the best choice. Letting clients be authoritative still has problems. What if a hellaciously laggy player snipes a low-ping player because he/she just isn't getting the position packets? It's a strange case, because you want to reward the player whose experience was "I have your head in my sights", but you don't want to reward the overtly laggy player because it's not "fair". Also, if you're doing that, then you're susceptible to the ZPM "ethernet-kill-switch" hack that would be remarkably easy to do on a console. Regards, charles nicholson ================================================================================ From: "Tom Forsyth" (tom.forsyth^blueyonder.co.uk) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 20:16:23 +0100 RE: [Algorithms] Network console game/distributed object strategiesThat's certainly the way it should be. If you get a 2:1 kill ratio against newbs, you're pretty good. If you get a 4:1 kill ratio, you're a hero. If you get a 10:1 ratio, you're just a bully :-) So skewing things against the better player (as long as it's a linear penalty, not an arbitrary one) seems fine to me. You do need to be on the lookout for exploits of it though - people fragging themselves or falling off things a lot to lower their skill rating, then storming out with all the newbie-assists in their favour. TomF. ================================================================================ From: "Tyson Jensen" (twjensen^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 11:41:23 -0800 >>That doesn't sound like fun to me- if I spent 80 hours becoming >>FANTASTIC at a game, I don't want to be artificially punished because I >>mop up the Noobs.... Actually, you DO want to be artificially punished. You DON'T want to have no one to play with. It's a meta-gaming issue. Mop up the noobs, and you aren't having fun because there isn't a challenge and they aren't having fun because they can't do anything. The self-bucketing didn't work for crap. I'd join an "experts" game and then get a bunch of angry fellow players when I slaughtered them. I'd proceed by joining an "intermediate" game and get my butt handed to me on a plate. People don't really know their "real" rank unless you have an effective ladder. Ladders are good because cheaters can all eventually face off against other cheaters at the top of the ladder. X-Box Live is good for this because it provides a nice environment for it and pathological cheaters can be booted from the service and forfeit their $50 US if that's how they want to play. Although so far I don't think Microsoft has had to do that to anyone. OTOH, automatic handicapping is a delicate issue. You end up frustrating everyone if the game's mechanics are completely opaque (ie, "why does my game always take away my rocket launcher after I get 5 kills?"). The automatic handicap should be a toggle when the game is created, everyone should be able to see if it is "on" and the instruction manual should explain what the automatic handicap does and how much of a skill range it compensates for. ================================================================================ From: "Michael Pohoreski" (MPohoreski^cyberlore.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 15:18:41 -0500 Interesting to note, that driving games have been doing this for years, and I haven't seen any loud complaints about it. The changes don't have to be big or noticable! Even a minor one is often enough, such as boosting everyone's top speed who isn't the leader. (This is typically done with AI players) I could easily see a FPS ever so slightly penalizing a player by slowly lowering there top velocity for every X frags they are ahead, where X is ~ 5 to 10. I don't think a "discrete" auto-balancing option is the way to go. Players will notice that, and complain. Yeah, the self-bucketing doesn't work. You could easily "pretend" that you aren't very good, and go into a newbie game. (Unless the game is globally tracking stats, how are people supposed to know just how good (or bad) your skills really are??) Ladders are definitely cool -- they are the great equalizer. ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 12:15:02 -0800 > > Of course client->server is not reliable. That's why you get > > lag-jumping on your own client. Unless you want the client to > > be authoritative about its own position, which seems like a > > bad idea from a cheating perspective. > > Well, we've divided all network content into reliable & unreliable. > Right now, it's looking like pretty much everything is reliable EXCEPT > for actor location data. I really don't want those to stall because one > dropped and I'm waiting for rexmission... This is networking we're talking about. You'd better design for everything being unreliable. Look at it this way: suppose the player picks up a power-up, which makes the range of his weapon be 2x what it was before. Suppose you say you use "reliable transport" for broadcasting this, but that the first packet gets dropped. If the player then tries to shoot someone within his new range (but outside his old range), then some parts of the system know about the power-up, and others don't, because the "reliable" re-transmission hasn't yet happened. I e, there is no way that all parts of your system are going to be in full sync at any particular time step; thus you should decide where you want authority to live, and you should assume that anyone who is not authority, may or may not have the authoritative data. The corollary to this is that client input may be unreliable, because it may get dropped when sent to the source of authority. The re-transmit timeout for TCP after a dropped packet is usually in the seconds range, so once that packet gets re-transmitted, it's often way too old to do you any good, btw. Hopefully, when you say "reliable" you mean something you built yourself on top of UDP, or you're working around the issues of TCP using some other method. > > That would work, but it would cause significant amounts of > > re-simulation on the server for each shot. On a console > > peer-to- peer set-up, one of the consoles is also the server > > That doesn't seem like a deal-breaker to me, just because the > "time-shifting" algorithm seems equivalent to interpolating an animation > position between keyframes. You have some "keyframes", which are No, it's not the same at all. Suppose the server keeps state for time steps 0, 1, 2, ... 20. Suppose, at time 20, the server gets a message from the client saying "At step 12 I shot this guy, and I received updates for steps 0, 1 ... 4, 6, 7, ... 12 at that point". Then the server would have to wind back to step 5, then re-play all physics for steps 5 (discounting the update for that step), 6, 7, ... 12 to actually know what the situation looked like on the client. Different clients may have different packets dropped, so you end up with running 10 simulation steps per hit request, per client. The CPU impact of this can be quite expensive, if you're doing something better than sweeping fixed-size balls through a coarse BSP tree. > > Now, if it could be done, it'd probably work very well, except > > for the parts where a player teleport packet gets lost, so that > > the shooter shoots a player he sees, but the shot player gets > > hit at some totally random location after the teleport. > > Player teleport packets are reliable and must arrive in-order. If the > contest between "I shot you!" and "I teleported!" is that close, then I > can't see any obvious solution. This happens in counterstrike when you > get shot around corners. "That close" can easily be 500 milliseconds (half a second) on the Internet. If you allow for router jitter and lost packets, you would probably want a wider window than that, especially if phone modems are in the picture. Just because a teleport packet "must arrive in order" doesn't mean that it has arrived at the point where the guy got shot at -- it just means it was sent out, and is currently waiting for the 3 second TCP retransmit delay. If you decide that what happens on the server is authoritative, then if the guy's teleport packet gets to the server before the shot packet, then the shot is a miss, else it's a hit, and most players participating in the simulation will see the same thing. > > Fix the CPU load from re-simulation, and you'd be able to get > > that. If you don't have the CPU to spare, I think that basing all > > decisions on authoritative information is the best choice. > > Letting clients be authoritative still has problems. What if a I am not suggesting you let clients be authoritative. I am saying you should carefully think about who should be authoritative for different pieces of the simulation. If it's all peer-to-peer, you might want more than one client being authoritative, and running consistency checks between them, to try to weed out cheats, although you still have to account for packet loss (this gets really hairy -- in fact, I've proven to myself it can be done, but not implemented it -- our product uses authoritative, secured servers). > hellaciously laggy player snipes a low-ping player because he/she just > isn't getting the position packets? It's a strange case, because you > want to reward the player whose experience was "I have your head in my > sights", but you don't want to reward the overtly laggy player because > it's not "fair". Also, if you're doing that, then you're susceptible to > the ZPM "ethernet-kill-switch" hack that would be remarkably easy to do > on a console. Thus, keeping one central state as authoritative seems to me to be the least evil. People with better connections may get a truer view of what's actually going on -- that's not much different from people with digital cable getting less noise on their TV picture than people with an aerial antenna. And people in a Yugo probably hear more road noise than people in a BMW. Cheers, / h+ ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 14:02:34 -0800 > This is networking we're talking about. You'd better design for > everything being unreliable. I think we're using different definitions of unreliable. By reliable I mean that data will come through or the connection no longer exists. I have a guarantee from my network layer that data I peg as reliable will come in in-order, uncorrupted and not duped. If this isn't 'reliable', then what exactly are you referring to? Latency? > Look at it this way: suppose the > player picks up a power-up, which makes the range of his weapon > be 2x what it was before. Suppose you say you use "reliable > transport" for broadcasting this, but that the first packet gets > dropped. If the player then tries to shoot someone within his > new range (but outside his old range), then some parts of the > system know about the power-up, and others don't, because the > "reliable" re-transmission hasn't yet happened. I e, there is no > way that all parts of your system are going to be in full sync > at any particular time step; thus you should decide where you > want authority to live, and you should assume that anyone who is > not authority, may or may not have the authoritative data. The > corollary to this is that client input may be unreliable, because > it may get dropped when sent to the source of authority. If I send packet A and then packet B in sequence, the application layer won't get packet B until it has packet A. That's what reliable means to me. The 2x damage multiplier and the shoot request would both be sent reliably (in-order), and this keeps the simulation deterministic- the server has a guarantee that it would receive the damage multiplier packet before the shoot request. If the damage multiplier packet gets dropped and the gameplay gets weird for a split second, that's ok if it happens infrequently. If it happens frequently, the connection is obviously lagged/unstable/bad and the player should find a different game. This is how PC fps work and is also why you sort by ping, right? > The re-transmit timeout for TCP after a dropped packet is > usually in the seconds range, so once that packet gets > re-transmitted, > it's often way too old to do you any good, btw. Hopefully, when > you say "reliable" you mean something you built yourself on top > of UDP, or you're working around the issues of TCP using some > other method. Yes. Our protocol is built on UDP and stream-based, with both reliable and unreliable transfers. Our data timeouts are much more aggressive than TCP, and we do congestion avoidance by simply dropping unreliable packets on the floor (as they make up a fair amount of our bandwidth usage, and, hey, you knew they were unreliable when you sent them! ;-) ). > No, it's not the same at all. Suppose the server keeps state for > time steps 0, 1, 2, ... 20. Suppose, at time 20, the server gets > a message from the client saying "At step 12 I shot this guy, and > I received updates for steps 0, 1 ... 4, 6, 7, ... 12 at that point". > Then the server would have to wind back to step 5, then re-play all > physics for steps 5 (discounting the update for that step), 6, 7, > ... 12 to actually know what the situation looked like on the client. > Different clients may have different packets dropped, so you end up > with running 10 simulation steps per hit request, per client. The > CPU impact of this can be quite expensive, if you're doing something > better than sweeping fixed-size balls through a coarse BSP tree. OK, I wasn't thinking that the client would say "At time 12", I more figured it would just say "I shot this guy". The server has the average latency for that client, and uses that to time-travel back to (approximately) when it happened. There's no replaying of physics, it's a simple interpolation between positions, with some code to account for things like crouching, dying, teleporting, etc... Just the simple counterstrike lag compensation algorithm. > I am not suggesting you let clients be authoritative. I am saying > you should carefully think about who should be authoritative for > different pieces of the simulation. If it's all peer-to-peer, you > might want more than one client being authoritative, and running > consistency checks between them, to try to weed out cheats, > although you still have to account for packet loss (this gets really > hairy -- in fact, I've proven to myself it can be done, but not > implemented it -- our product uses authoritative, secured servers). If clients aren't authoritative, then the server is. It seems very binary to me- use client prediction to help the local player feel more responsive, let the server run the show. If the client is partially authoritative, then it's completely authoritative. I mean, if the client says "I shot you in the head at time T" and the server isn't willing to blindly believe this, then it server has to recreate the head shot locally. It's not also fully peer-to-peer, logically it's a client/server network. It could behave like a p2p, but I've never heard of a fully p2p fps, and I'm a little frightened to break new ground. > Thus, keeping one central state as authoritative seems to me to be > the least evil. People with better connections may get a truer view > of what's actually going on -- that's not much different from people > with digital cable getting less noise on their TV picture > than people with an aerial antenna. And people in a Yugo probably hear > more road noise than people in a BMW. I completely agree with this. Actually, I was thinking about decoupling the game host from the game server. Halo has a 10 second countdown before the game starts- why not use that time to do bandwith/latency testing and decide which console will actually serve the game? Just because I want to host a game on XBL doesn't mean that my console should run the show. I guess my question is really, is there a better way to do a network FPS than how counterstrike does it? Regards, charles nicholson ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 14:33:53 -0800 > > This is networking we're talking about. You'd better design for > > everything being unreliable. > > I think we're using different definitions of unreliable. By reliable I > mean that data will come through or the connection no longer exists. I > have a guarantee from my network layer that data I peg as reliable will > come in in-order, uncorrupted and not duped. If this isn't 'reliable', > then what exactly are you referring to? Latency? Those are fine guarantees. Sounds like TCP. However, the problem with that guarantee is that if a certain packet gets dropped, then LATER packets will be withheld by the networking layer, waiting for the previous packet to get re-sent, causing unacceptable delays in delivery. That's the price you pay for guaranteed in-order delivery. What I'm saying is that, in actuality, the delays are worse than having to deal with missed or out-of-order packets, and thus you don't really want this guarantee; you want something less stringent that doesn't cause data that makes it across to be delayed, waiting for lost previous data. That's what I mean when I say "design for everything being unreliable." > If I send packet A and then packet B in sequence, the application layer > won't get packet B until it has packet A. That's what reliable means to > me. Fine enough. Works great for databases. However, there is no guarantee WHEN those packets will be delivered. They may (and will) be delivered with 3 second latency under these conditions. Meanwhile, there's a 3 second window when the client doesn't know about the teleport happening (or, for that matter, anything else). If you think this is fine, then by all means, keep going down the path you're going. > packet before the shoot request. If the damage multiplier packet gets > dropped and the gameplay gets weird for a split second, that's ok if it What networking protocol do you use for your underlying transport? If you use TCP, the value of "split second" is likely to be "3 seconds". > happens infrequently. If it happens frequently, the connection is > obviously lagged/unstable/bad and the player should find a different > game. This is how PC fps work and is also why you sort by ping, right? Most FPS-es use protocols built on UDP, and deal with dropped packets just fine. Withholding newer data (not delivering to the higher-level application) just because you dropped some older data is NOT what you want to be doing in a real-time distributed simulation. > OK, I wasn't thinking that the client would say "At time 12", I more > figured it would just say "I shot this guy". The server has the average > latency for that client, and uses that to time-travel back to > (approximately) when it happened. There's no replaying of physics, it's That's almost exactly the approach I suggested. I hope you realize that this means that if the client lost a packet in the window, then the client will believe it shot the guy, it'll send the request, and the server will look it up in its log and believe that he didn't hit, because the player being shot at was in a different location on the rest of the systems; only the client system had suffered the packet loss. This means that the client had the guy in his sights, shot, and missed, because his simulation was out of whack with reality. That's just a fact of life with shitty network connections. Luckily, on the Internet, you usually have close to 0% packet loss, with occasional spikes of 50-100% packet loss. While this gets reported as an average of "1%" packet loss, I think players will easily be able to tell when they're having bursts, vs when it's running fine. > If clients aren't authoritative, then the server is. Agreed. > I completely agree with this. Actually, I was thinking about decoupling > the game host from the game server. Halo has a 10 second countdown > before the game starts- why not use that time to do bandwith/latency > testing and decide which console will actually serve the game? Just > because I want to host a game on XBL doesn't mean that my console should > run the show. I agree. In fact, it probably makes sense to round-robin successive games. I believe the recommendations for XBL is to automatically add a server to the pool from the local client when a matchmaking query returns too few running servers with the desired characteristics. Cheers, / h+ ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 14:50:27 -0800 > If you think this is fine, then by all means, keep going down the path > you're going. Sorry, when reading this post I realized this could come off sounding nasty. I didn't intend to :-) What I intended was saying that "if this works allright for you, then no need to change". Note that with Internet latency, any re-transmit timeout less than 500 milliseconds is very likely to cause lots of spurious re-transmits. Even that is sort-of pushing it, especially if modems are involved. If you think it's fine to delay some packet for 750 milliseconds (timeout, plus the transmission delay of the retransmit packet) just because some previous packet has gotten lost, then you're probably working on a differend kind of game design than I'm imagining. Cheers, / h+ ================================================================================ From: Lucas Ackerman (ackerman7^llnl.gov) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Fri, 04 Apr 2003 15:33:38 -0800 Charles Nicholson wrote: >[snip] > >It's not also fully peer-to-peer, logically it's a client/server >network. It could behave like a p2p, but I've never heard of a fully >p2p fps, and I'm a little frightened to break new ground. > > > > If I recall correctly, the networking in Forsaken was peer-to-peer, as were possibly the early Descent games (prior to #3, which I think lacked a pure peer-to-peer mode). Google turned up no details however. I'd be interested to see how they handled these issues. Does anyone know the whole story here? -Lucas ================================================================================ From: "Tyson Jensen" (twjensen^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 16:08:59 -0800 TCP??!!?!??!! Who said we or anyone else would try to implement reliable GAME traffic over TCP?! Might as well debate the relative merits / demerits of using smoke signals to send update packets. ================================================================================ From: "Michael Pohoreski" (MPohoreski^cyberlore.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 19:21:09 -0500 Yeah, Descent 1 & 2 were client-side authorative, with peer-to-peer networking. You would see people 'warp' across the map all the time. I hacked up my D2 client to be invulnerable in a few mins, back in the day. Pissed off my a good co-worker to no end. Hey, I thought he'd be impressed by my 3l334 skills. ;-) Descent also had a 3d strafe bug, but that's another topic. ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 16:21:59 -0800 Heh, I prefer highly caffeinated carrier pigeons myself. I submitted it as a transfer protocol, but the leads nixed it. Yeah, we rolled our own protocol. None of that pesky exponential retransmission backoff stuff. No nagling either. ;-) ================================================================================ From: "Tyson Jensen" (twjensen^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 16:47:40 -0800 Ok, now that's out of my system. There's a certain class of events in my simulation that would severely negatively impact the game quality if the event just "doesn't" happen. Say a client fires a rocket and is now simulating the rocket. It sends a packet to the server, and the packet never arrives. 5-10 seconds later the client machine realizes that the rocket was never even created in the simulation! This is a TERRIBLE result if the rocket explosion on the client caused a boulder to roll down a hill! Do I now roll the boulder back up the hill? Most packets make it without issue. A reliable packet in real time means that maybe I broadcast twice and take the small bandwidth hit for those very very important messages. That limits the number of bad cases. I then expect that if I don't get an ack tacked onto the normal traffic that I have to retransmit, but this happens on the order of one roundtrip time, say 250 ms. If my double broadcast fails AGAIN, I'm now at 500 ms. Assuming a 90% reliable network, I expect 99.99% of my reliable traffic to be authenticated by the server within 375 ms and confirmed back to the client by 500 ms. Assuming DSL / Cable modem typical ping times, I do even better. ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Fri, 4 Apr 2003 16:58:23 -0800 > Who said we or anyone else would try to implement reliable GAME traffic > over TCP?! Any protocol that guarantees in-order delivery will suffer from the following problem: 1) It will need to re-transmit packets. 2) The soonest it can re-transmit packets is after one round trip time. 3) Thus, a lost packet means that no packets (even the packets sent after the lost packet) will be delivered for a time window equal to 1.5x round-trip time (assuming symmetric round-trip). You can live with this for things like text chat, or logging in, or high-score updates, but not for anything that affects real game play (in my opinion). If you're rolling your own, my recommendation is that you'd do well to design something that maybe guarantees delivery (if you need that guarantee) but which doesn't guarantee in-order delivery. If you need in-order delivery, you can re-order at the application level where it makes sense, rather than have your network layer hide and withhold data from you that it's already received. Cheers, / h+ ================================================================================ From: "Chris Butcher \(BUNGIE\)" (cbutcher^microsoft.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Sat, 5 Apr 2003 12:08:58 -0800 Danger! Long email ahead! I have been thinking about this for the last few days and wanted to collapse my replies to this thread in to a single message, hope you don't mind the length. > Jon Watte wrote: > > You don't. Thus, if a client is shooting at what looks like a person, > but that is empty air, then the client will miss. Someone is authoritative > for shots against character X, and only that someone should decide if > character X gets hit. You could, alternatively, decide that character Y > is authoritative for what he shoots. At that point, client-side hit > detection is all fine and dandy, and there's no problem. Except for the > cheats ;-) > > In my mind, there really isn't any other way to do this. Someone always > gets screwed. Might as well be the one guy who had a packet drop right > before shooting, rather than everyone else. I agree with this sentiment. As arQon says, someone always has to lose out in any arbitration dispute. However, my contention is that you can come up with a good solution in which the decision as to who gets screwed isn't made solely based on what the type of action being performed is, but also by looking at how "close" the client was to the server's authoritative game state. > > Then the authoritative remote machine must check that: > > 1) under the reported conditions, would the action succeed? > > 2) did the reported conditions "match" the real authoritative > > conditions? > > > > I don't understand 2). If it matches, then why would the client have > to do the detection at all? If client matches server, then server can > make the determination without explicitly being told what the client > state was. Thus, client needs to send no state. Here's another way of stating this approach. The client has some input from its local user, and based on this input it makes a decision on what happens to the world. It sends the input, world state, and the result of the decision to the server. The server examines the information that the client had at the time the decision was made. This may be done in several ways - either by keeping records of what had been sent to the client and assuming they got everything successfully, or the client can send information about which packets it received which allows the server to reconstruct the exact world state, or the client can simply send the actual world state that it used. The server then must decide whether it will allow the client to be authoritative about the result of this action, or whether it will reject the client's decision. There are several interesting questions that we can ask. - Was the client's decision valid given the information that it had? (This guards against things like player state changes which would probably not be transmitted in the reduced world state that the client sends to the server) - Was the client's information "sufficiently" close to the server's reality? (This guards against clients who are lagging, have a time cheat, or have an ethernet kill switch which allows them to make other players appear to move in a reliable fashion on their local machine) - Was there some theoretical player input that would have allowed the decision to succeed, if it was run _in the server's reality_? (This guards against decisions that are inconsistent with the world, e.g. players shooting through walls) My assertion is that if these three decisions validate successfully, the server should accept the client's decision as authoritative. This might require some amount of simulation rewind and/or object fixup depending on your game. > Charles Nicholson wrote: > > > This is a generalization of the Counterstrike-like lag > > compensation strategy, and it allows for a wider spectrum > > between (less satisfying, more accurate) and (more > > satisfying, prone to exploitation). I think broadband gaming > > on a fixed console hardware platform (i.e. what we're > > doing) should err more towards the fuzzy side. > > It seems that if this is the approach, then the server is no longer the > primary owner of the simulation- that it becomes 'fuzzy' as you > mentioned. What are the implications of this? > > Also, on a related note, are there any good approaches to non-relative > objects like projectiles? Bernier's paper mentions that projectiles > become a bit of a mess because they exist in absolute time (i.e. aren't > 'owned' by any particular user) I view the server as still being the primary owner of the simulation. Ultimately every decision is made on the server, and the server is in control of exactly where it decides to bend the rules of the simulation in order to make individual clients' experience better. As to the implications, well, ultimately that depends on exactly how you code the tests that must pass in order for the server to accept a client-side decision. In Counter-Strike, projectiles exist in absolute time. They have a complex tracking between client time and server time because their server rewind function requires that you can associate a particular client action with the state as it was on the server. I believe in our game the creation of a non-instantaneous projectile will be treated just like shooting someone with an instantaneous projectile, i.e. it will be an action about which a client will typically be authoritative if the server decides to allow it. Therefore projectiles will appear exist in local time. The downside of this is that other clients will see projectiles appearing to warp in, but I don't believe this will be a big problem since our game isn't about dodging projectiles as much as, say, Quake is. > Charles Nicholson also wrote: > > > I think the varying between client and server authoritive > > based on how good the player is seems reasonable. If your > > client is doing well, or people initiate a "cheat" vote > > against him (above certain params), you bump to more server > > authoritive. If a player is doing unnaturally well on his own > > skills, that little extra lag penalty will even up the game a bit :) > > > > Conor Stokes > > That sounds to me like a really bad idea. You're increasing the > complexity of the code by dynamically shifting authoritativeness from > client to server and back in real-time using fuzzy heuristics (which > themselves are a pain to define- how good is "too" good?). You're also > forcibly flattening out the skill range of players by granting > advantages to worse players. That doesn't sound like fun to me- if I > spent 80 hours becoming FANTASTIC at a game, I don't want to be > artificially punished because I mop up the Noobs.... I definitely agree with you about trying to characterize players' performance using fuzzy heuristics and penalize people who are 'too good' being a bad idea. However I believe that we can accurately characterize the quality of a client's information about the world. Shifting authoritativeness back and forth between client and server happens anyway in modern networked games with things like player movement. In a game where a server has the final say about the state of the world, any client-side prediction at all incurs this overhead of shifting authority. I believe that putting a single fundamental architecture underneath all of these actions can help us reduce complexity. For example, Counter-Strike has systems for movement prediction and action compensation that don't share any of their heuristics. And they have a very simple world. Imagine taking a next-generation simulated world (or even just something as complex as Halo 1) and trying to insert different heuristics and prediction schemes for every different class of action that can be undertaken. > Tyson Jensen wrote: > > There's a certain class of events in my simulation that would severely > negatively impact the game quality if the event just "doesn't" happen. > Say a client fires a rocket and is now simulating the rocket. It sends > a packet to the server, and the packet never arrives. 5-10 seconds > later the client machine realizes that the rocket was never even created > in the simulation! This is a TERRIBLE result if the rocket explosion on > the client caused a boulder to roll down a hill! Do I now roll the > boulder back up the hill? In this case, I think yes, you do cause the boulder to roll (or lerp, or warp) back up the hill. More precisely, you have four options: 1) Don't let the client fire the rocket until the server tells it to. 2) Don't let the client show the rocket explosion particles until the server tells it the rocket exploded. 3) Let the client predict the rocket explosion particles, but not any of the effects of the explosion (objects flying around, etc) until the server tells it what the reactions of those objects were. 4) Let the client predict the explosion and its effects, and then be open to the possibility that the server will warp all of the objects around after the fact. Like I explained above, I think that the answer is either 3 or 4, depending on how "close" the client thinks that its simulation is to the server's. > Most packets make it without issue. A reliable packet in real time > means that maybe I broadcast twice and take the small bandwidth hit for > those very very important messages. That limits the number of bad > cases. I then expect that if I don't get an ack tacked onto the normal > traffic that I have to retransmit, but this happens on the order of one > roundtrip time, say 250 ms. If my double broadcast fails AGAIN, I'm now > at 500 ms. Assuming a 90% reliable network, I expect 99.99% of my > reliable traffic to be authenticated by the server within 375 ms and > confirmed back to the client by 500 ms. Assuming DSL / Cable modem > typical ping times, I do even better. 500ms is still terrible latency for player actions. I strongly suggest that you replicate the client -> server action stream across multiple consecutive packets. Virtually every modern architecture does this to some extent. Obviously this redundancy should be introduced at the application level rather than the packet stream level. Phew! -- Chris Butcher Rendering & Simulation Lead Halo 2 | Bungie Studios (butcher^bungie.com) ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Sat, 5 Apr 2003 13:26:58 -0800 > - Was the client's decision valid given the information that it had? This sounds like a weak check to me. If someone hacks the client, surely they will send world state that corresponds to their actions. > (This guards against things like player state changes which would > probably not be transmitted in the reduced world state that the client > sends to the server) Note that it's as likely that the client is out of sync because a packet FROM the client TO the server got lost, so the client player position is not the same on the client and the server. That's equally likely to some packet about the target being dropped, and will cause the same aiming problems. > - Was the client's information "sufficiently" close to the server's > reality? (This guards against clients who are lagging, have a time > cheat, or have an ethernet kill switch which allows them to make other > players appear to move in a reliable fashion on their local machine) Fair enough. Sending enough world state to determine this seems a bit expensive to me, though. In a player-server world, this would mean that if everyone fired at the same world step, the poor server console would have to have incoming bandwidth sufficient to receive all the world state copies from all the clients at the same time. > - Was there some theoretical player input that would have allowed the > decision to succeed, if it was run _in the server's reality_? (This > guards against decisions that are inconsistent with the world, e.g. > players shooting through walls) If this degenerates to line-of-sight on the server, I understand how to do this. However, if you allow for both target and shooter to be somewhat out of place, you suddenly have a cylinder of possible shot rays, all of which could conceivably be allowed. Doing exhaustive search is clearly too expensive. Traditional collision detection only detects whether some part of the cylinder intersects -- testing for full intersection is more expensive. > The downside of this is that other clients will see projectiles > appearing to warp in, but I don't believe this will be a big problem > since our game isn't about dodging projectiles as much as, say, Quake > is. There is several hundreds of milliseconds between the players. I don't see how projectile warping can be avoided. However, you can hide it; for example, by letting projectiles travel at 4x the speed from the source following the real trajectory, until they actually catch up with their intended position. > Shifting authoritativeness back and forth between client and server > happens anyway in modern networked games with things like player > movement. In a game where a server has the final say about the state of > the world, any client-side prediction at all incurs this overhead of > shifting authority. I'm not so sure. The client renders a predicted world, but that's not the same as saying that the client is authoritative. One way of doing server-authoritative client movement is to locally do the movement, and send the movement to the server, and have the server validate that the movement was plausible before sending it on; this is talked about as "terrain validation" in some available middleware literature. Another way, which I prefer, is to locally perform the movement on the client, and then send the stimuli to the server, which re-simulates the same movement as the client did (assuming they're in sync). You need to recover your baseline if you fall out of sync, such as unconditionally re-sending it every so often, but that seems like a better model to me. > very simple world. Imagine taking a next-generation simulated world (or > even just something as complex as Halo 1) and trying to insert different > heuristics and prediction schemes for every different class of action > that can be undertaken. Oh, I'm quite busy imagining just that already ;-) > > Say a client fires a rocket and is now simulating the rocket. It sends > > a packet to the server, and the packet never arrives. 5-10 seconds > > later the client machine realizes that the rocket was never even created > > in the simulation! This is a TERRIBLE result if the rocket explosion on > > the client caused a boulder to roll down a hill! Do I now roll the > > boulder back up the hill? > > In this case, I think yes, you do cause the boulder to roll (or lerp, > or warp) back up the hill. More precisely, you have four options: If your time to recovery is 10 seconds, then your simulation may be as much as 5 seconds out of date. I'd suggest designing with a faster time to recovery than that. > 3) Let the client predict the rocket explosion particles, but not any of > the effects of the explosion (objects flying around, etc) until the > server tells it what the reactions of those objects were. > > 4) Let the client predict the explosion and its effects, and then be > open to the possibility that the server will warp all of the objects > around after the fact. > > Like I explained above, I think that the answer is either 3 or 4, > depending on how "close" the client thinks that its simulation is to the > server's. I also believe this is true. Waiting for the server before actually doing anything will make the game feel very mushy. > > Most packets make it without issue. A reliable packet in real time > > means that maybe I broadcast twice and take the small bandwidth hit > > traffic that I have to retransmit, but this happens on the order of one > > roundtrip time, say 250 ms. If my double broadcast fails AGAIN, I'm I would assume a round-trip time of 500 ms if a traditional analog modem is involved. And even that is when the connection is behaving as expected. I've found that, on the internet, when you get packet problems, they come in clusters. Thus, sending two copies of the packet right after each other isn't all that great of a solution, because if one drops, it's likely the next drops, too. Instead, I think the focus should be on fast, correct distribution of data when the network works, and on predictable, guaranteed recovery where you get losses, with a little bit of lipstick (position interpolation, etc) to try and smooth it over. Cheers, / h+ ================================================================================ From: "Chris Butcher \(BUNGIE\)" (cbutcher^microsoft.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Sun, 6 Apr 2003 18:10:52 -0700 > > - Was the client's decision valid given the information that it had? > > This sounds like a weak check to me. If someone hacks the client, surely > they will send world state that corresponds to their actions. Agreed. This check is not useful against hacked clients. It is intended to account for the fact that the client is transmitting _partial_ world state - just a few object positions, that sort of thing. An example would be if the client says "player A at position X shot player B at position Y", but the server knows that in the interval between the client firing and the message reaching the server, player A has already been killed. > Note that it's as likely that the client is out of sync because a packet > FROM the client TO the server got lost, so the client player position is > not the same on the client and the server. That's equally likely to some > packet about the target being dropped, and will cause the same aiming > problems. Well, yes, although I imagine that client -> server action packets have deliberate redundancy because it's important that the server get an uninterrupted movement stream. > Fair enough. Sending enough world state to determine this seems a bit > expensive to me, though. In a player-server world, this would mean that > if everyone fired at the same world step, the poor server console would > have to have incoming bandwidth sufficient to receive all the world > state copies from all the clients at the same time. In all of our models, we see server upstream bandwidth (server -> client) as being several times more precious than server downstream bandwidth (client -> server). So I'm not worried about this. Also, this "world state" that we're sending is really minimal, just simple information about the entities that are interacting in the action, and any state information about them that is likely to be inconsistent between client and server due to prediction (e.g. mostly just position). > If this degenerates to line-of-sight on the server, I understand how to > do this. However, if you allow for both target and shooter to be somewhat > out of place, you suddenly have a cylinder of possible shot rays, all of > which could conceivably be allowed. Doing exhaustive search is clearly > too expensive. Traditional collision detection only detects whether some > part of the cylinder intersects -- testing for full intersection is more > expensive. It comes down to line-of-sight on the server. There are two possibilities: 1) the player was auto-aiming at their target, which turns in to "will an auto-aimed ray on the server hit?" 2) the player was firing in a particular direction and hit their target, which turns in to "is the ray from player to the same point on the target's server-relative position valid?" I definitely think you're right about reducing the time-to-recovery as much as possible. Right now I use the algorithm described in Van Jacobson's 1990 paper "Berkeley TCP Evolution from 4.3-Tahoe to 4.3-Reno". This method continuously measures the mean round-trip time and mean deviation based on time taken for successful packet acknowledgements, and calculates the timeout value for retransmission T=3D M + kD where k=3D 4. I then have another layer on top of this that handles backoff and bandwidth throttling (unlike TCP, which ties these levels of response together). I would be curious to hear if you have any better algorithm. -- Chris Butcher Rendering & Simulation Lead Halo 2 | Bungie Studios butcher@bungie.com ================================================================================ From: "Charles Nicholson" (cnicholson^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Tue, 8 Apr 2003 09:24:57 -0800 > I definitely think you're right about reducing the > time-to-recovery as much as possible. Right now I use the > algorithm described in Van Jacobson's 1990 paper "Berkeley > TCP Evolution from 4.3-Tahoe to 4.3-Reno". This method > continuously measures the mean round-trip time and mean > deviation based on time taken for successful packet > acknowledgements, and calculates the timeout value for > retransmission T= M + kD where k= 4. I then have another > layer on top of this that handles backoff and bandwidth > throttling (unlike TCP, which ties these levels of response > together). I would be curious to hear if you have any better > algorithm. That's exactly what I've been doing in our network layer, it seems to work pretty well so far.... If anyone wants the explanation & math w/o digging through IETF archives, check "TCP/IP Illustrated, Volume 1: The Protocols", by W. Richard Stevens, published by Addison-Wesley. Specifically, page 300. It's a pretty great book. Chris, I'd be curious to hear your approach to congestion avoidance. Clearly, if you have simultaneous reliable & unreliable streams in the same protocol, then the obvious solution is to simply start tossing your unreliable packets (which for us constitute a good 70-80% of network transmissions). Are you doing anything fancy to detect this though? Regards, Charles Nicholson ================================================================================ From: "Chris Butcher \(BUNGIE\)" (cbutcher^microsoft.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Tue, 8 Apr 2003 10:49:19 -0700 > Chris, I'd be curious to hear your approach to congestion avoidance. > Clearly, if you have simultaneous reliable & unreliable streams in the > same protocol, then the obvious solution is to simply start tossing your > unreliable packets (which for us constitute a good 70-80% of network > transmissions). Are you doing anything fancy to detect this though? Still working on traffic balancing, no hard facts to report yet. My plan is basically to assign raw packet sizes and packet intervals to handle congestion based on estimated bandwidth available and current packet loss statistics, and that there is no feedback from "current amount of traffic desired" into this. (There may be exceptions for large guaranteed messages that need to fit into a single packet, but I'm not sure.) -- Chris Butcher Rendering & Simulation Lead Halo 2 | Bungie Studios butcher@bungie.com ================================================================================ From: "Max Elliott" (maxe^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Tue, 8 Apr 2003 18:36:09 -0700 > Any protocol that guarantees in-order delivery will suffer from the > following problem: > > 1) It will need to re-transmit packets. > 2) The soonest it can re-transmit packets is after one > round trip time. Not entirely true. If I have bandwidth to spare (and sometimes I do) I can simply retransmit preemptively. There is much about TCP which does not suit our purposes ;> > 3) Thus, a lost packet means that no packets (even the > packets sent after the lost packet) will be delivered > for a time window equal to 1.5x round-trip time > (assuming symmetric round-trip). Not necessarily. See comment about 2) above. With the right retransmission algo, this will happen only once in a while and recover very quickly (i.e. on the next 'retransmission'). That is a whole lot better than '3 seconds' and perfectly acceptable even for an action game if it only happens once in a while... RUDP: Pure custom goodness! Max Elliott Sammy Studios ================================================================================ From: "Max Elliott" (maxe^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Tue, 8 Apr 2003 18:52:16 -0700 As regards the whole 'hacked client' issue, I would propose the following: Don't design your arbitration scheme to be 'cheat tolerant' but rather, design a good cheat detection scheme and drop players who are cheating. Can the ZBM 'line-kill' hack be detected? You bet it can. If I don't get an update for 1 second, what does that tell you? What do you do when you detect someone doing this? Drop em. Give 'em a polite dialog indicating that 'trouble was detected' with their Ethernet connection, so that you don't accuse folks with loose cabling of cheating... What do you do if they have 'hacked your client app' to disable this error detection pass? Perform lots of little crc type checks, etc. Anti-cracking fare. Can spoofed packets be detected? Yes. You can use: Nonce, Packet Serialization, CRC, MAC, HMAC, etc. Lots of ways to detect cheating... My $0.02 Max Elliott Sammy Studios ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Tue, 8 Apr 2003 19:08:20 -0700 > Not entirely true. If I have bandwidth to spare (and sometimes I do) I > can simply retransmit preemptively. There is much about TCP which does > not suit our purposes ;> If you have bandwidth to spare, then you're not utilizing the network pipe fully -- allow more players in the game! :-) Also, I don't know if you target Live! or modems, but no matter which, you'll see that different users have different bandwidth available, because of local cable modem uplink speeds, contention, modem connect quality, and all of that jazz. Also, if you re-transmit soon-ish, then the re-transmit is about as likely to be hit by a router hiccup as the first packet. I believe the internet is really quite bursty -- it has long periods of perfect delivery, and then suddenly you get an outage that lasts seconds. At that point, it doesn't matter much what your re-transmit policy is. The cause for sporadic dropped packets would be something like a jam- packed modem dropping packets, or possibly a user listening to MP3s while playing (not entirely uncommon), and at that point, I'm not sure that more traffic on the line will improve things, either. But, again, if it works for you, ship it! :-) Cheers, / h+ ================================================================================ From: "Jon Watte" (hplus^mindcontrol.org) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Tue, 8 Apr 2003 19:13:01 -0700 > If I don't get an update for 1 second, what does that tell you? What do > you do when you detect someone doing this? Drop em. Give 'em a polite I suggest you get an actual residential internet connection and run a continuous ping to some faraway state at about half-second intervals and plot the loss and delays. You'll see that one-second hiccups do occur just naturally. Cheers, / h+ ================================================================================ From: "Ding Ai Jun" (daj528^163.com) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 10:57:33 +0800 > > Any protocol that guarantees in-order delivery will suffer from the > > following problem: > > > > 1) It will need to re-transmit packets. > > 2) The soonest it can re-transmit packets is after one > > round trip time. > > Not entirely true. If I have bandwidth to spare (and sometimes I do) I > can simply retransmit preemptively. There is much about TCP which does > not suit our purposes ;> Not a good idea. Spare bandwidth must be reserved for peaks in traffic. In the worst case, if a packet is lost, it indicates a possible traffic jam somewhere. So fast retransmission will worsen the jam. Retransmission in a long interval gives network time needed to recover. On the contrary, I would suggest to carefully differentiate the data into finer classes, and reduce the number of retransmissions. For instance, the new game states will obsolete old ones, so that old ones need not be reansmitted if new states are known received by the remote party. This is a good characteristic which can be made use of. In my mind, guaranteed and unordered transmission plus scheme which obsolete old useless packets are enough for networked game. TCP is a good general purpose protocol, which guarantees smooth and reliable transmission of large files. However, it is not suitalbe for games, as games usually do not need guaranteed and ordered transmission. TCP is not suitable for the obsolete scheme we mentioned above. It will constantly retransmit old states if they are lost, but the old states are obsolete and not needed any more. > > 3) Thus, a lost packet means that no packets (even the > > packets sent after the lost packet) will be delivered > > for a time window equal to 1.5x round-trip time > > (assuming symmetric round-trip). > > Not necessarily. See comment about 2) above. With the right > retransmission algo, this will happen only once in a while and recover > very quickly (i.e. on the next 'retransmission'). That is a whole lot > better than '3 seconds' and perfectly acceptable even for an action game > if it only happens once in a while... > > RUDP: Pure custom goodness! > Instead, I would suggest a light-weigth SCTP a good sample. regards, aijun ================================================================================ From: "Conor Stokes" (cstokes^tpgi.com.au) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 11:32:37 +0800 >I suggest you get an actual residential internet connection and run >a continuous ping to some faraway state at about half-second intervals >and plot the loss and delays. You'll see that one-second hiccups do >occur just naturally. Which is why 5 seconds would work better - unless the user has rigged up a fancy kill switch, its probably going to take more than 5 seconds to pull out the cable, shoot someone and then put it back. Conor Stokes ================================================================================ From: "Conor Stokes" (cstokes^tpgi.com.au) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 11:35:22 +0800 > > >I suggest you get an actual residential internet connection and run > >a continuous ping to some faraway state at about half-second intervals > >and plot the loss and delays. You'll see that one-second hiccups do > >occur just naturally. > > Which is why 5 seconds would work better - unless the user has rigged up a > fancy kill switch, its probably going to take more than 5 seconds to pull > out the cable, shoot someone and then put it back. > Forgot to mention, you can always check how many kills the user got during that long connection blip - if they had a connection blip and got a bunch of kills, you either disallow the kills on the server side, or kick the player if he has X kills + a connection loss. Pretty simple algorithms. Conor Stokes ================================================================================ From: "Max Elliott" (maxe^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 09:26:24 -0700 > If you have bandwidth to spare, then you're not utilizing the network > pipe fully -- allow more players in the game! :-) > True-ish. I will utilize all available bandwidth, but throttle the UDP/unreliable content to accommodate my aggressive RUDP band's needs. > Also, I don't know if you target Live! or modems, but no matter which, > you'll see that different users have different bandwidth available, > because of local cable modem uplink speeds, contention, modem connect > quality, and all of that jazz. We are targeting Live! and also PS2 online environment (we roll our own here). Variable bandwidth constraints are one of the reasons we chose to have highly controllable UDP throttling. How much and when to throttle is a broad subject, but typically involves analysis of current latency values, packet loss rates, etc. There are many ways to approach the 'perfect bandwidth utilization' ideal. The tradeoffs are game specific. In our case, it would simply be better to back off on the UDP band very quickly (this band contains data like entity position and direction) and aggressively (but safely) recover the RUDP band. > Also, if you re-transmit soon-ish, then the re-transmit is about as > likely to be hit by a router hiccup as the first packet. I believe the > internet is really quite bursty -- it has long periods of perfect > delivery, and then suddenly you get an outage that lasts seconds. At > that point, it doesn't matter much what your re-transmit policy is. Yes and no. If it is a 'router hiccup' as you suggest, then all bets are off, and you are correct in asserting that no retransmission algo in particular is going to be better or worse. It is simply a matter of time until the path is either changed or becomes clear. If, on the other hand, it is simply my ISP capping my upstream bandwidth utilization (which is the most likely scenario, given that I am attempting to utilize the entire available bandwidth, and given that this is exactly what most cable-based providers are doing) then the next packet to go out will not be dropped unless I am still demanding more bandwidth than I am 'allowed'. In my experience (with Live! and cable modems, e.g.) this is actually the case. If I drop a single packet, the best assumption to work with at that time is that I am not encountering a persistent condition, but rather have encountered an anomaly, and should proceed as if the next packet will get through (it mostly does). If I detect more dropped packets, then I should execute plan B, which is what I would call 'recovery mode', which can last a long-ish time as you suggest. At that point, the game has visibly hiccuped, and the users expectation will already be 'adjusted'. > The cause for sporadic dropped packets would be something like a jam- > packed modem dropping packets, or possibly a user listening to MP3s > while playing (not entirely uncommon), and at that point, I'm not > sure that more traffic on the line will improve things, either. But, > again, if it works for you, ship it! :-) We are not planning support for Mac or PC, just console... Our users will not likely be streaming Gigs of Pron as they play our game... Well, not likely anyway... ;> Also, modems are a drag and we will probably have a disclaimer in the game about them. I hope the broadband adoption stats will have changed a bit by the time we release... Max Elliott Sammy Studios ================================================================================ From: "Max Elliott" (maxe^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 09:46:50 -0700 > I suggest you get an actual residential internet connection and run > a continuous ping to some faraway state at about half-second intervals > and plot the loss and delays. You'll see that one-second hiccups do > occur just naturally. Yeah. I know. I wouldn't actually drop someone for a single 1-second blackout. But there is a limit. If it happens 'a lot' then their network connection is bad, or they are cheating, and they need to be dropped in order to salvage the game. If there is a blackout for much more than a second, then the game is in jeopardy again, and we should drop the 'unlucky' one. Live! actually has guidelines about this... Max Elliott Sammy Studios ================================================================================ From: "Max Elliott" (maxe^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 09:56:24 -0700 > Not a good idea. Spare bandwidth must be reserved for peaks in traffic. In > the worst case, if a packet is lost, it indicates a possible traffic jam > somewhere. So fast retransmission will worsen the jam. Retransmission in a > long interval gives network time needed to recover. I respectfully disagree. See my reply to Jon Watte previous to this message. Understand that dropped packets happen for several, very different reasons. The recovery characteristics of these different events are very different as well... > On the contrary, I would suggest to carefully differentiate the data into > finer classes, and reduce the number of retransmissions. For instance, the > new game states will obsolete old ones, so that old ones need not be > reansmitted if new states are known received by the remote party. This is > a good characteristic which can be made use of. In my mind, guaranteed and > unordered transmission plus scheme which obsolete old useless packets are > enough for networked game. We only use the reliable pipe for 'events'. Meaning, state changes which cannot be 'overridden' by later changes. If a state item is of the type which can be 'overridden' by later state, then it goes out in the unreliable band...I would suggest you not use a 'reliable' mechanism for non-event data... > TCP is a good general purpose protocol, which guarantees smooth and reliable > transmission of large files. However, it is not suitalbe for games, as games How unclear have our original posts been on this? We are NOT using TCP. Nobody on this list is using TCP. (I seriously hope not...If you are, you better be writing an internet-chess game or something) > usually do not need guaranteed and ordered transmission. TCP is not suitable > for the obsolete scheme we mentioned above. It will constantly retransmit > old states if they are lost, but the old states are obsolete and not > needed any more. Clearly. Max Elliott Sammy Studios ================================================================================ From: Martin Piper (MartinP^argonaut.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 18:09:42 +0100 I've found this topic interesting. Mostly because I like writing network APIs and apps in my spare time. At home I have had reasonable success with expanding the usual reliable UDP in to two discrete types of packet. One packet is guaranteed in the same order delivery and the other type guarantees delivery but without maintaining order. The last type is completely unreliable UDP packets. This way you can mix and match which events are really important, semi-important and not important. ================================================================================ From: "Tyson Jensen" (twjensen^sammystudios.com) Subject: RE: [Algorithms] Network console game/distributed object strategies Date: Wed, 9 Apr 2003 10:29:00 -0700 Actually, I have more dropped packets over my high bandwidth @work connection than I do with my @home DSL. When I was in Utah, I got an e-mailed apology practically on a per-dropped-packet basis. The 'net is far more reliable than it was back when I took networking in college. I respectfully suggest that the author of the somewhat rude message below has not actually performed such a test recently and is relying on somewhat out of date information. Typically, a 1-second drop of all packets is cause for a severe game hiccup no matter what protocol is being used so deriding our desire to have "guaranteed" packets based on 1-second hiccups is disingenuous. Your unreliable packet game will suck just as bad as ours under such conditions. And don't assume that I'm using the most na=EFve possible implementations of aggressive re-transmit. Let's assume that I have a packet that is so important that I decide it is worth bumping 5 unreliable packets to insure that it gets there in a timely fashion. My transmission profile will look like: Time 0ms - send the first time Time 1ms - send the second time (gets there right on time and slips past bandwidth throttle on the ISP end) Time 20ms - send the third time (gets past most hiccups that we actually see these days) Time 100 ms - send the fourth time (gets past many common internet tangle hiccups that happen from time to time) Time 200 ms - at this point, I'm expecting a reply, and will only send if I haven't gotten the reply yet. Time 250+ depending on game quality setting. This setting is determined at the beginning of the game based on how long I expect packets to take round trip. Waiting... I haven't gotten a reply, so I'm going to go into a completely different mode, the resync the game mode where I throttle back my unreliable traffic to a trickle while I try to get the game back to a sane state. This may simply involve pausing the game and waiting for my packets to arrive (works 99% of the time when the problem is delay rather than failure, delay is very common on the 'net, failure less so.) Time 500ms - whenever. Depending on the quality of the game (green =3D 500 ms, 56K modem =3D what the heck, 5000 ms). Now I need to display a message informing the user of why the game sucks. So, what does reliable traffic buy me? Ah, the real question, glad you asked. It buys me the ability to consider peer-to-peer as an alternative to client-server. Since client-server can be implemented as a subset of a good peer-to-peer distributed authority solution (all authority is simply transferred to a server, but the same authentication code applies), I can try both client-server and peer-to-peer versions of the game and pick which one is giving better overall game. This is very handy when we want a multi-platform game. Maybe I like peer-to-peer on Live! but decide that on PS2 I should use client-server and designate the PS2 on broadband as server with dial-up PS2s as clients. I can even do a hybrid with multiple servers and multiple non-authority bearing clients! Yay! Now that I wrote the above paragraph, I am going to try to deflect the obvious criticism by pointing out that yes, I do realize that server side authentication gets more complicated than peer-to-peer. ================================================================================ From: "Mickael Pointier" (mpointie^eden)-studios.fr> Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Thu, 10 Apr 2003 09:28:35 +0200 Max Elliott wrote: >> The cause for sporadic dropped packets would be something like a jam- >> packed modem dropping packets, or possibly a user listening to MP3s >> while playing (not entirely uncommon), and at that point, I'm not >> sure that more traffic on the line will improve things, either. But, >> again, if it works for you, ship it! :-) > > We are not planning support for Mac or PC, just console... Our users > will not likely be streaming Gigs of Pron as they play our game... > Well, not likely anyway... ;> Also, modems are a drag and we will > probably > have a disclaimer in the game about them. I hope the broadband > adoption stats will have changed a bit by the time we release... If I'm correct, PS2 or Xbox don't have modems ? They only have RJ45 100mb Ethernet socket, that should be plugged on a switch, or on a ADSL/Cable modem, right ? In this situation, if the user has this kind of connection, I assume it will be shared between the game console and some computer. So while the hardcore gamers in the family will be playing Halo 2 on the Sofa, I would not be surprised if someone else is using the computer listening to some 128kb shoutcast streaming on www.scenemusic.net, while downloading the latest trailer of Matrix 2, and occasionaly checking the mail ;) Mickael Pointier ================================================================================ From: (phil_wilkins^playstation.sony.com) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Thu, 10 Apr 2003 09:20:12 -0700 Mickael Pointier: > If I'm correct, PS2 or Xbox don't have modems ? The PS2 adapter has both a modem port and an ethernet adapter, the XBox has ethernet built in (although you have to purchase a Live subscription for it), the Gamecube has two seperate adapters, like the DreamCast (except that the DC came bundled with the modem adapter). Cheers, Phil ================================================================================ From: "Igor Kravtchenko" (igor^obrazstudio.com) Subject: Re: [Algorithms] Network console game/distributed object strategies Date: Thu, 10 Apr 2003 20:40:11 +0200 > streaming on www.scenemusic.net ... or ofcourse www.streamingsoundtracks.com :) Igor.