How to handle a large number of pickups in a MMO game

Question

How do games like Minecraft, or really any MMO game that has pickups, handle them?

Say terrain spawns 3 pickup drops of "dirt" everytime you dig said terrain. Say every item has a rotation animation computed every frame. If the number of pickups in the world goes very high, that would be a useless massive overhead in the frame computation for a client in a given server, as it's likely that a lot of those pickups items are light years away from you.

So what I thought is that you have to "do stuff" only with the pickups close to the local player, but still this would imply that every frame I have to check if any other pickup item is close enough that it has to start animating.

My actual question is: how have other MMOs solved this issue?

Answer 1

By simply only loading those parts of the world into memory which are close to the player. Anything else is suspended to hard drive. When there is a tiny object laying around two kilometers away, then the player can not see it and can not interact with it. So there is no reason to update it or send it to the GPU for rendering. The smaller the object and its interaction range, the lower the range around the player where you need to load it.

Regarding finding out what's close to the player: That mostly boils down to storing the world in a datastructure optimized for spatial lookup. Good candidates for those are spatial hashing and multi-dimensional trees.

Answer 2

You have two very different things to manage:

1. The server must manage the entire world, in an authorative manner. For that, communication with N clients (where N is "massive") is necessary.

2. The client could, in principle, know about the entire world, but it needs not. For the client, it is sufficient to know about what's nearby the player. Assuming for example a rather coarse grid-like partitioning, it would need to know only the player's cell and the 26 cells around the player (or 8 cells in case you have a 2D grid). A somewhat finer grid is better, but you get the idea.

Now, a lot of pickups, what is "a lot"? You dig maybe 5 things per second, that's maybe two dozen numbers that need to be updated on the server, and the server may have to transmit those to some other player whose area of interest overlaps your cell. For a computer, this is quite ridiculous amount of data, and a neglegible amount of computation. It may become a challenge when there's hundreds/thousand of players in the same cell (then your paritioning is too coarse).

The server does not need to know, nor care about the rotation of the pickups or such details. Why would it?

The client actually doesn't care either, since this is just eye candy that the client can make up on the fly.

What's necessary from the server's point of view is knowing that you were digging at (30, 40, 50) in the node you're in, and it decides that this spawns e.g. three objects of type 5, or one object of type 7 with a count of 3. That's all it cares about, and it's all it tells you. It will also include that information in the data sent to someone moving his area of interest over the grid cell later (assuming it's still there by then).

The client gets told three objects spawned there, blah blah. Now, whether the client displays an ASCII-art map where there's now a 'D' or whether it shows a rotating pile of dirt, it's all the same. Whether the piles have different rotations or whether only the ones close to your player rotate is all the same, too. It's just stuff that is displayed on your monitor, it doesn't affect anyone else.

So, in the concrete case that you want to rotate only nearby piles of dirt, you can just do a range check on all the objects you know about. Since the data set isn't large, even brute force on everything will work.

You can (and should) depending on your partitioning size, trivially prune away grid cells that are too far away.

You can, of course, furher sub-partition your cell and use something super smart. Use a kd-Tree if you will, but do not expect huge gains. You can prune stuff away with Manhattan distace, or your can sort your stuff in a small grid of your own... but why?

A distance check (really squared distance, but it's the same to you) is a mere two multiplications and an addition (optimized to MUL, MADD, so really just two operations), followed by a branch or conditional move. That's pretty much as fast as any other operation which doesn't prune entire grid cells at a time. In fact, this is something that you could even do on the GPU...

Seeing how you will have a few hundred, or at most a few thousand distance checks against the same position (squared distance works fine), you really don't have much trouble just doing that calculation, even more so as it's a rather cache-friendly iteration over contiguous memory, and with conditional moves, it's dirt cheap. Something like (pseudocode) rot = r[i] + 1; r[i] = ((dx*dx+dy*dy) < DIST_SQ) ? rot : r[i];. That's one iteration over an array of a few hundred values per frame. The computer couldn't care less about doing that, it's contiguous loads and stores, simple ALU, no branches, and only a few thousand iterations.

This (many-to-one) is not the same class of problem (many-to-many) as on the server. Really, the client isn't the problem.

Answer 3

@T.Sar writes in a comment that you should look into Minecrafts "loaded chunk" concept for more information. If you do, be aware that this is rather complicated in Minecraft due to people building machines in the game.

A very simplified version follows:

The world is divided into square regions(chunks). In Minecraft there is also a height division but most mmos don't need that.

The game client only cares about the regions close to the player. This is much simpler than drawing a circle around the player, but perfectly good enough.

In Minecraft, the regions are 16x16 blocks, and the client knows about 9x9 regions, 4 regions out in each direction. (4 regions east + region player is in + 4 regions west = 9 regions total. Same north/south)

There is nothing magical about these numbers, use whatever makes sense in your game.

The client only animates things inside this area. The server only calculates things like wandering monsters in regions that is close to some player.

When a player walk around inside a region, nothing special happens, when they cross a region border the "edge of animation" is pushed one region over. The client then needs to ask the server about the regions it now sees.

There is nothing wrong with having several nested animation limits. E.g. animate item drops in a 3x3 area, wandering monsters in a 5x5 area and just show the landscape in a 9x9 area.

The server keeps a "frozen version" of regions which no player sees. If this takes a lot of memory, you may want to unload these after a time. When a player next arrives, the region is reloaded without the item drops. You need to be faster next time, Player 1.