{"id":6185,"date":"2009-12-30T09:59:08","date_gmt":"2009-12-30T13:59:08","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=6185"},"modified":"2015-06-03T16:50:07","modified_gmt":"2015-06-03T21:50:07","slug":"mmo-population-problems","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=6185","title":{"rendered":"MMO Population Problems"},"content":{"rendered":"

Someone emailed me with a series of questions about the server limits in MMO games. The whole thing was too big to tackle in one go, but the central question was roughly:<\/p>\n

“Why can you have millions of people viewing the same webpage, but you can’t have more than a thousand or so users in the same shard of an MMO?”<\/p>\n

While the availability of processing power and bandwidth have skyrocketed in the last decade, that “1,000 users” number has changed very little in the same time period? (And perhaps it’s even gone down in practice.)<\/p>\n

Welcome to the thorny problem of multiplayer worlds, which involves population density, server network throughput, client framerate, client side prediction, and a whole bunch of other variables. I’m not an expert at this by any stretch of the imagination (I usually stay away from server-side work) but I offer my non-expert overview of the problem here.<\/p>\n

Consider you, in an MMO, standing all by yourself:<\/p>\n

traffic_alone.jpg<\/td><\/tr><\/table><\/p>\n

As you move around the world, you send your positional data to the server. At minimum, you need to send your x, y, and z position, along with a heading to indicate which way you’re facing and some additional data to indicate how you’re moving<\/em>. You might also send data indicating if you’re looking up or down, and what other things you might be doing. (Performing emotes, shooting, changing weapons, spell effects, etc etc.) <\/p>\n

How often this is sent depends on the game in question. A fast-paced action game might have a base framerate of 30fps, which works out to you sending your positional data 30 times a second. (Or as close as your PC can come, if you’re really struggling to run the game.) An MMO might get away with a lot less. I wouldn’t be surprised if they only updated a few times a second. <\/p>\n

Goldshire represents a worst-worst case scenario: The worst distribution of the worst sort of players.<\/td><\/tr><\/table><\/p>\n

In our case above, you send this positional data to the server, and in turn the server sends back its own idea of where you “really” are. If you’re lagging it’s possible that you and the server might not agree. The server is ultimately in charge, and so your game client will “correct” your position, yanking you back to where the server says you are. People call this “rubber banding”, because you appear to walk forward and then snap back to where you were a few seconds ago.<\/p>\n

So you’re constantly sending your position, and the server is sending back your position. For the sake of simplicity, let’s just assume these two things happen at the same rate. You send one up, and get one back down. The server gets one, and sends one back out. No problem.<\/p>\n

Now, you find yourself standing near another user:<\/p>\n

traffic_two.jpg<\/td><\/tr><\/table><\/p>\n

You send your data, and you get back data for two. You get your position, and the other player’s position. The other player gets the same deal. One up, two down. No problem.<\/p>\n

But the server is doing something different. It’s getting two updates, but then it must send two updates to two people. So, it gets two, but sends four. I’m sure you can see where this is going:<\/p>\n

traffic_twenty.jpg<\/td><\/tr><\/table><\/p>\n

Twenty users. Everyone sends an update, and gets twenty in return. (Their own position, plus one for each of the other 19 people.) The server gets twenty updates, and sends four hundred – twenty updates to twenty people. <\/p>\n

Well, obviously we’ve got a very annoying growth curve here where the outgoing updates is the square of the number of people in the environment. <\/p>\n

We need to mitigate this problem if we want to get anywhere near making a half-decent MMO. We do this by trying to cut down on the numbers on both sides of the multiply sign:<\/p>\n

Maximum Distance<\/strong><\/p>\n

The population here is distributed sparsely, but the people themselves are pretty dense.<\/td><\/tr><\/table><\/p>\n

Obviously we can implement some sort of maximum-view radius. Everyone will only see other users that are within some reasonable distance. Picking a good value is crucial, and that “good value” depends on a lot of other factors. Making this value too small means people will pop in and out of view abruptly, and two people might have trouble finding each other even in a perfectly open area. The woods might be thick with players, but if they’re spread out and I can only see people within twenty meters of me, the place can feel sort of empty. Suddenly you start to lose the “massive” in MMO.<\/p>\n

On the other hand, people are not spread out evenly over the world. They tend to congregate in cities and around key locations. It might seem reasonable to see everyone within fifty meters when I’m out in the wilderness, but with a view distance like that I’ll be able to see almost everyone in town. If you’ve ever been to the bank or the auction house in World of Warcraft, you know that a huge number of people cluster around those areas. This optimization fails to help in dense areas, which is where most of the problem occurs. <\/p>\n

Limit Viewable Characters<\/strong><\/p>\n

For the auction house clustering problem, you might consider putting an upper limit on how many people you can see. Perhaps if the local population gets to be extremely dense, everyone will only see the closest (say) forty people? <\/p>\n

This will introduce a little strangeness to the world, in that you’ll have I-can-see-you-but-you-can’t-see-me issues. To help picture this, imagine a super-simple world where you only see yourself and the one person closest to you:<\/p>\n

traffic_radius.jpg<\/td><\/tr><\/table><\/p>\n

Blue and green will each see one another and not be aware of yellow. Yellow will see blue but not green. Try adding this feature to a game with PvP and see how fast it all flies apart and gameplay turns into a morass of confusion and exploits. <\/p>\n

Cull Extraneous Data<\/strong><\/p>\n

Some games will go to great lengths to reduce how much data is sent. For example, perhaps your vertical position is only sent when it changes. (Left 4 Dead does this.) This can let you leave out one of the x, y, z values if you don’t need it, although a feature like this would be worthless in a world without a good supply of flat surfaces. <\/p>\n

An obvious way to cut down on data sent is to simply not send out updates for a character that’s standing still. This works really well for people who might be using the bank, auction house, or a shop (finally! a technique that helps with the in-town crowds!) but won’t be a great deal of help in the wild when people are always on the move, looking around, and firing off abilities and spell effects.<\/p>\n

The server might decide to “throttle” updates from other users. So, the game might give me ten updates per second if I’m with just one other person, but if I’m in a huge crowd I might get updates for other people once a second. I’ll still be able to see a huge crowd without bringing the server to its knees, but everyone else will appear to have very choppy or uneven movement.<\/p>\n

CPU Concerns<\/strong><\/p>\n

Arg. So many people in the way. When are they gonna make a single-player version of this game?<\/td><\/tr><\/table><\/p>\n

Ideally you’d want a system that scales based on what’s around the user. If they’re out in the wilderness alone, it should be aggressive at showing other players and showing them at great distances. But if they’re socializing in town on a Saturday night during a holiday event and the place is wall-to-wall with players, then the server should be working to limit how much you see. Oh! Don’t forget that the server should always try to show you people who are in your party, even if they’re a little distance away and you’re in a crowd. Also don’t forget that there’s an overhead to introducing you to someone new because it has to send a larger block of data describing their avatar. And the server also needs to propagate chat messages which, while pretty lightweight on their own, still have to be sorted by distance and zone so that everyone sees the text that they should. Don’t forget that you need to transmit data for pets and mounts. And then the killer: moving all those tens (or perhaps hundreds) of thousands of monsters around and keeping players up to date on where they are. <\/p>\n

Okay, it’s obvious that this stuff can get incredibly complex in a hurry. <\/p>\n

And typical of the tradeoffs that that you face in these sorts of situations: The more of these bandwidth<\/strong>-saving techniques we use, the more CPU<\/strong> we need. In a world with 1,000 or 1,500 users (a common user count for an MMO) you can end up doing an absolute ton of per-frame-per-user operations. For example, finding the closest 50 users for everyone in the world means doing a ton of distance calculations and sorting. Every one of the 1,000 users has a unique list of monsters and other users that they can see. That list needs to be updated and sorted on a regular basis. While this doesn’t need to be done every<\/em> frame, it’s still a nasty multiplicative problem because for each of the 1,000 users, the other 999 need to be considered for visibility. Any number that ends up being squared is a number you want to keep a low as possible. <\/p>\n

We have lots of great algorithms for doing these sorts of sorting and comparison operations. (A lot<\/strong> of Information Science<\/a> theory is spent on these very subjects. Very smart people were sorting and comparing massive lists of data long before anyone ever thought about making an MMO.) But even with our fancy new whiz-bang computers and advanced sorting technology, 1,000+ people moving X times a second produce (and demand) more than enough data to tax a server. Given the multiplicative effects of crowds, a modest increase in population can lead to severe spikes in demand.<\/p>\n

traffic_world.jpg<\/td><\/tr><\/table><\/p>\n

And in the end, do we want<\/em> more than 1,000 people in the world with us at once? There is a certain “sweet spot”. You don’t want that “ghost town” feel, but you also don’t want the “smothering” effect you get in high population areas. Big cities are notorious for rudeness, small towns are famous for being friendly. This isn’t because only jerks live in cities and only nice people live in small towns. There is a psychological effect to having a press of people around us, competing for our resources and taking up our elbow room. People get impatient and edgy when they’re fighting a crowd. But if you’ve got lots of resources and lots of room, you might even find yourself eager to connect with someone else. You’re more inclined to greet them on the road and help them if you can. This behavior carries over to the virtual world. <\/p>\n

I think that despite an MMO being “massive”, it’s actually a lot more fun and a lot more conducive to team play if you can get people to have that “small town” feel. That sense that we’re all in this together. You want enough people that players will be able to meet, interact, and form groups, but few enough that they’ll actually want to. Even if your servers have lots of power and bandwidth and your MMO could support 5,000 simultaneous users, it would probably be detrimental to gameplay to do so. <\/p>\n","protected":false},"excerpt":{"rendered":"

Someone emailed me with a series of questions about the server limits in MMO games. The whole thing was too big to tackle in one go, but the central question was roughly: “Why can you have millions of people viewing the same webpage, but you can’t have more than a thousand or so users in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[55],"tags":[],"class_list":["post-6185","post","type-post","status-publish","format-standard","hentry","category-game-design"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/6185","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6185"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/6185\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}