Player Visibility Problem

Question

I'm looking into designing and implementing an online RPG (or more accurately, redesigning an existing piece of server software).

One of the problems is that of managing visibility. Update data for other players should only be sent to a game client if their player is near the other players (i.e. you shouldn't get health updates for people you can't see on the other side of the map). The main problem is that if you had to compare all the players every time an update is sent, it would just take way too long as the number of players scales (think up to a few thousand players per map and each of them updating up to 3-5 times a second).

If the players are in a 2D space (it's 3D but the z difference shouldn't affect visibility) what is the best way to manage the visibility of other players?

My idea is to have a separate thread that compares the space difference of all the players every few seconds or so and stores references to all nearby players in the player's object for easy access when an update needs to be broadcasted.

The existing system uses grids to organize players, and only uses only players in the current and neighbouring grids to do updates. There are some problems with the system though, as it isn't that efficient (besides knowing which grid they are in, no other caching) and sometimes visibility limits should extend beyond 2 grids of distance.

Is there a better or easier way? If it can be multithreaded that would obviously be better, and the less main-thread calculation the better.

(For anyone wondering, the project is in C++).

Answer 1

Your current grid system sounds like the spatial hashing system described here.

In theory, the performance should be fine unless too many entities exist in the same grid block.

However, the grid-based hashing isn't as commonly used as a Quadtree. The Quadtree is a bit more involved to implement, but it has a few nice features.

• it costs O(log N) to find something. This is pretty graceful in terms of scaling up to thousands or millions of objects.

• It isn't fixed at a particular scale. This means that it works just as well when you have 1000 really close to each other or 1000 objects really far apart. Obviously both these cases are not handled gracefully by the grid.