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++).

  • \$\begingroup\$ Divide and conquer. Spatial partitioning. Grids are great if you have a known map size. Why do you think that your current grid system isn't efficient? A separate thread would work fine, minus having to manage locks, but has nothing to do with your real question. \$\endgroup\$ Dec 3 '11 at 23:01
  • \$\begingroup\$ Ignore the previous comment, sorry. I may investigate ways to make the current system better. If you were to design a grid system from scratch, what would the best design be? Should distances be cached for faster access? \$\endgroup\$
    – Pat S
    Dec 3 '11 at 23:30
  • 2
    \$\begingroup\$ Your problem is also known as "interest management" if you're looking for search terms. Photon describes its basic concepts here: doc.exitgames.com/v3/mmo/concept There's also a doc (pdf) that describes different types of interest area spacing here: gram.cs.mcgill.ca/papers/boulanger-06-comparing.pdf \$\endgroup\$
    – Tetrad
    Dec 4 '11 at 1:28
  • \$\begingroup\$ @Tetrad: Interesting article. I didn't think about actual visibility checking. \$\endgroup\$
    – Jimmy
    Dec 4 '11 at 1:40

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.


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.