How does a wow server handle which player position to set to each nearest players?

Question

I already understood how game developers could create very large game levels, bypassing the floating point precision limit.

This was my very first mind boggling question, and I understood it when I read how some programmer told the story of some dungeon PC game.

My question is more related to game networking, more precisely wow.

There are no interruptions in the game level (apparently I think).

Since the viewing distance is much smaller than the world size, and since there are a lot of players, you can't send all players positions because it would require too much bandwidth; so you have to only send the nearest players positions, among a pretty big list of connected players.

Those servers are almost always online, with a large number of players (only doing quests or idling into cities, since I guess dungeons and raids must be hosted on dedicated servers), and they must find a solution to save as much bandwidth as possible.

So at one point the server has to determinate which players positions it has to send to which players, and when it has to stop sending it.

I was wondering about how the server does this, because to me it seems to have O(n^2) or even an O(2^n) complexity. How do they do it ? Do they fragment into virtual tiles so they only check players in the nearest tiles ? Do they calculate this not so often so that the server can handle it ?

A continuous online persistent world is quite awesome, but technically I don't really know how they do it.

Answer 1

This is really a data structure issue, in that you need a quick way of looking people up based on position.

Analogy: If you were to try and find a psychology book by Freud in the library, you wouldn't look at every book in turn. Instead, you'd go straight to the psychology section. And once you were there, you wouldn't start at A and look through each book until you found it: you'd go to the 'F' section and look there. This requires the library to have decided on a couple of criteria - subject area and alphabetisation - to order their books. Then, armed with that information, you can find the books you want without having to look at every other book in library.

So how can we do this for geographical positions, given the knowledge of an initial position? It turns out there are several ways:

• Sort all objects by one of the coordinates. You still have a long list of N objects, but you can jump somewhere in the middle based on the coordinate in our original position, and from there can quickly narrow the search down. This would be a bit like the library ignoring subject areas but sorting everything by author. It's not ideal, but it works well enough in many situations. Most small games can perform well enough with this method.
• Store objects in a tree structure. You can divide up all the possible positions, eg. into 2 halves, and then subdivide them further, continuing until you have very subdivisions that are small enough to be manageable. You can search the tree quickly because every position comparison lets you rule out half of the objects. If you created a binary tree based on one coordinate then you essentially have the same system as the previous idea, except that the structure is explicit in the tree instead of implicit in the way you search the list. More usefully, you could create a quad-tree that is divided up by 2 coordinates and eliminate 75% of possibilities with each decision, and if you need all 3 coordinates, an oct-tree works for that.
• Store objects in a hash-table. A hash treats an input value as a way of indexing into a large structure. Normally you want each input value to generate very different hashes, but in our case we want some coherence between adjacent values so that objects near to each other tend to get hashed nearby. So you might take 2 coordinates and divide them by 50 and discard the remainder to get a hash value - this means that objects within that 50x50 area will be hashed under the same value. This in turn means that you may only need to check that box and the ones around it to quickly get a list of all nearby characters.
• Store objects in a grid. If you divide your world up into arbitrary zones or tiles of a predictable size, you can easily find nearby objects by first determining the zone to start from, and then getting all objects in that zone or in adjacent zones within the range of interest. To determine which grid square a position is in is a case of dividing the position coordinates by the size of the grid. You can easily see that this is basically the same as the previous method and that the way to determine the grid square is a hash function, and the grid squares holding objects are the hash table.

Any of these approaches would work for most games. Although the tree approaches look elegant, usually a 2D grid is sufficient, with it being very easy to write and test, and having good lookup speed. For smaller games it's often not necessary to implement any spatial database at all, or to stick with the sorted list.

Answer 2

Get on a long flight path, with a Hunter who can track is best. Watch NPCs around you come into existence and disappear behind you.

WoW is apparently working with little chunks like @thedaian says. All the server has to do is subdivide everyone into chunks, much much faster than N^2, close to linear. And these chunks are quite small, the amount of the NPC world that exists for you can be felt even when running around on the ground.

google "space partitioning" to find various ways that these chunks are done, though I expect that WoW took the easy way and just laid down a 2D grid manually. The advantage to the manual way is that special areas like cities can be tuned for performance, so remember that "easy" is not "bad!"

Answer 3

In case of cities and dungeons, I know that the server split it in sections. In stormwind you don't receive information about players in other districts. In the past you could see that with the glitch that allowed you to go under the terrain in stormwind. You could only visually see the players in the same district above you.

Outside I think the server has no option other than separate players by their distance, and there's a lot of ways to do that

Answer 4

A scene graph, and likely not too much of a complicated one..

When you think of graphical rendering you are sending hundreds of thousands of vector values to figure out which parts of which models you are rendering on the screen. And this happens 30+ times a second depending on the game and the hardware.

Translate that to the number of people per-zone in WoW and you are talking about having to handle a scene graph of a few thousand entries at most. The hardest place would be in the cities where people gather to trade and the like, but as pointed out by Papavoikos they are further broken down into which district in the city you are in.

In either case, the number of elements you are dealing with, connected players in your region, is never all that high as compared to things like rendering that are doing the exact same sort of calculations, which objects with positional data am I near?

Hope this helps.