26
\$\begingroup\$

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?

\$\endgroup\$
  • 9
    \$\begingroup\$ In addition, in the context of Minecraft, after a certain number of items are near enough to each other (3+ of the same item in the same blockspace), the server replaces the 3 instances with a grouped instance that contains the block type (minecraft:dirt) and a count(30), so that when the player is close enough to pick it up, it just add as much of the count as possible to the player's inventory. If the player only has room for 6 items and a stack of 30 is on the ground, the player will pick up the 6, and the stack on the ground's count is reduced to 24. \$\endgroup\$ – Zymus Nov 6 '17 at 22:57
  • 6
    \$\begingroup\$ @Zymus It's worth noting that actually decreased tick performance for moderate numbers of dropped items because they're all constantly looking for nearby ones. \$\endgroup\$ – user253751 Nov 7 '17 at 1:24
  • \$\begingroup\$ Have a read through en.wikipedia.org/wiki/Occlusion_culling \$\endgroup\$ – RJFalconer Nov 8 '17 at 13:45
48
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the quick answer. I was thinking about using Unity as I am guessing it uses some kind of spatial partitioning to check trigger colliders, so I would create one big circle collider around my character and every item inside it would be "animated". Is this a way of implementing your answer? Correct me if I am wrong, cheers! \$\endgroup\$ – Alakanu Nov 6 '17 at 16:19
  • 2
    \$\begingroup\$ @Alakanu It can be used if you want objects to be visible at long distances but only perform certain computation-intense behaviors when close to the player (and just rotating something around its y-axis should not be very expensive). But the actual challenge when implementing an open world game in Unity is intelligently instantiating and destroying game objects while the player moves through the world (or even better: use object-pooling instead of instancing and destroying). \$\endgroup\$ – Philipp Nov 6 '17 at 16:24
  • \$\begingroup\$ Yeah, object pooling is mandatory in this situation :) Ok thank you very much! \$\endgroup\$ – Alakanu Nov 6 '17 at 16:26
  • 3
    \$\begingroup\$ @Alakanu You can check Minecraft's "Loaded Chunks" concept for more information about how this answer applies to that game. \$\endgroup\$ – T. Sar - Reinstate Monica Nov 6 '17 at 17:08
  • 1
    \$\begingroup\$ This is not only true for pickups. ANY object that is too far from the player can be treated that way. Sometimes even objects that are close to the player. Imagine a house with a full interior but there is no need to render until you actually enter the house. \$\endgroup\$ – Zibelas Nov 7 '17 at 8:16
22
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'm sorry, I thought it was clear that I was talking about a client when I started talking of framerate. \$\endgroup\$ – Alakanu Nov 7 '17 at 9:53
  • 1
    \$\begingroup\$ But the client is never the problem. The client is very much non-massive, and very much local, it needs to know a lot less than the server. Ideally, the client knows the spatial partitioning node (whatever it is, say, grid) the player is in, and the immediately surrounding ones, and that's it. Updates are thus very modest unless a thousand players stand next to each other. Normally, you only ever need deltas for one or two objects, and a new grid node's contents after moving towards one direction for more than half a node's width. Everything else: Not your problem. \$\endgroup\$ – Damon Nov 7 '17 at 10:18
  • 1
    \$\begingroup\$ The point is that being too smart can be a massively stupid idea. Your world is necessarily spatially divided already, with a manageable number of objects in each node. Modern CPUs (and GPUs even more so) are good at sequentially processing bulks of SoA data. They do not like incoherent branching, and they like incoherent memory access even less -- which is however exactly what "only process nearby" does. For manageable numbers (some hundred, some thousand), "process all" within one cell is perfectly adequate, and likely the best thing you can do. \$\endgroup\$ – Damon Nov 7 '17 at 15:16
  • 1
    \$\begingroup\$ @Alakanu This looks like a detailed and complete answer to your question, to me. If you think it's not an answer, either you've misunderstood it or your question is so unclear that it's been misunderstood by Damon, me and all the people who've upvoted this answer. \$\endgroup\$ – David Richerby Nov 8 '17 at 11:22
  • 2
    \$\begingroup\$ @Alakanu You really do spend a huge amount of time complaining at people who are trying to help you. Good luck with that. \$\endgroup\$ – David Richerby Nov 8 '17 at 12:21
2
\$\begingroup\$

@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.

\$\endgroup\$
  • \$\begingroup\$ Draw distance is adjustable but in this case 8 chunks is 9x9 and is a client-side decision, it can inform the server to speed things up though (so the server doesn't send data the client won't render). Also... didn't Doom and Quake solve that problem about rendering only what makes sense? \$\endgroup\$ – SparK Nov 7 '17 at 22:13
  • \$\begingroup\$ About despawning the dropped items... in minecraft the item only "ages" when there's a player nearby. So you can "save" a dropped item into an unloaded chunk and get it later. \$\endgroup\$ – SparK Nov 7 '17 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.