3
\$\begingroup\$

(Preface: Using C++, Box2D, and built UDP client and server classes that are reasonable efficient for a built-from-scratch game using client-server model.)

This question is specifically in regards to an MMORPG (WoW, Rift, Maplestory) / ARPG (Diablo, Path of Exile, etc) setup. My conundrum is this: How to efficiently share only what the client needs to know, without running the server (performance) into the floor?

To elaborate, I have narrowed down to three separate approaches, but all of them feel horrifyingly inefficient and "iteration-spammy". I will detail each below as succintly as I can, though (hopefully) with enough actionable information. My concern is keeping the CPU time as short as possible as a physical server may be running 20+ zones (or "level", if that makes more sense). I will not be sending full data each time, more of full data "as needed" (ex: id, health, x/y/z, velocity), then changes as they occur (ex: [id, x/y/z], [id, new health], [id, velocity]).

To keep things consistent, I will give the following example "setup" that will be referenced with each approach.

  • Map size is 20 'units' by 6 'units'
  • Players / NPCS are 0.5 'units' squared.
  • Sight Range: 1.5 'units' from player center, in a circle.
  • Number of Players: 3
  • Number of NPCs: 10

Approach A: Entity-based Checking

This consists of the server either iterating over all NPCs from each player's perspective (or all players from each NPC's perspective). This would look something like "for each player, loop through npcs and check if within n "units" of player. Once player's iteration is done, create and send payload to said player before next player's iteration" (where 'n' = sight range). This is fine in principle, until there are 10-20 players and 100+ NPCs. That ends up with 1,000+ iterations occurring each round (1-3 rounds per second). Again, not horrible by iteself, but 20+ zones could make this exceptionally slow and ruining the player experience.

Approach B: Tile-based Checking

By the use of tiles of size 'n' squared (again, 'n' = sight range), divide up the map. With the example map size, let's say it becomes 10 nearly perfectly fitting tiles. For this, the server would maintain the data per tile, then send concatenated entity data (e.g. vector) of tiles which the player is inside and adjacent tiles. This does have the advantage of breaking up the into much more managable areas, though it feels like maintaining the location checking for these tiles may become just as tedious as Approach A in that each 'round' (again, 1-3 rounds per second) the bounds checking will need to be performed against each entity multiplied by the number of tiles; 10 tiles x (10 NPCs + 3 Players) = 130 possible iterations.

Approach C: Lazy Physics-based Checking

I believe this is either the least terrible or the absolute most terrible (with no middle ground), though I cannot definitively prove which side of the fence it is standing. This would consist of creating an invisible circle around the player equal to their sight range as a radius. This has the advantage of using the Box2D collision detection and 'sensor' functionality to lazily determine what is and is not in range. Though, given what I've seen from working with Box2D, this is likely similar to simply iterating over the Entities themselves. The obvious con would be the requirement to either maintain a list of 'visible' entities or simply rebuild it each 'round'.


If you made it this far, you are a scholar and a saint. I appreciate any feedback, insight, or constructive criticism.

Again, in all seriousness and sincerity, thank you for reading!

\$\endgroup\$
  • 1
    \$\begingroup\$ B looks like the best option, since you don't really need to iterate over all tiles to determine which tile an entity belongs to. To get tile coodinates you simply divide entity coordinates by tile size and truncate the result. \$\endgroup\$ – HolyBlackCat Jun 12 '18 at 15:27
  • \$\begingroup\$ I would use B with tiles size of 2n (2 x sight radius = sight diameter), but you could make some assumptions to reduce the workload. 1. You dont need to check every Tile, only Tiles with entities. 2. When an Entitiy is in a tile, check every surrouding Tile for entities. Only those are possible to see for the Entities in the original Tile. 3. Mind the position of your Entities in your tile: If in the bottom right corner, dont check against entities in the top, top left and left Tiles. Im on work right now, maybe i write an answer later on. \$\endgroup\$ – PSquall Jun 13 '18 at 11:17
3
\$\begingroup\$

Preface: I'm not familiar with Box2D, but these structures can be found in Boost Geometry (R-trees) if you are really interested, as well as other libraries:

Premature Optimization (Don't Do it)

Premature optimization leads to longer development times with no benefit, but many people consider micro optimizations to be the only cause of premature optimization when in reality it applies to more than that. Even higher level optimization can be time consuming and equally fruitless.

Do the easiest thing you can implement first, if it actually ends up being a bottleneck then optimize. For your test numbers, I doubt even the slowest solution you've suggested will matter in the slightest.

That being said, if you do actually find performance issues with any naive solution you've chosen...

Spatial datastructures

Instead of iterating for all entities for each player, use spatial hashing or other spatial data-structures that should already be used for broad phased collision detection.

This can be:

plus any extras I've missed.

With these methods, you should be able to retrieve the list of enemies mostly in range of sight (use final check to make sure that they are actually in range before sending) in times between O(log(N)*N) to O(N), much faster than your O(N^2) suggestions. The issue will be updating these structures upon both players and entities moving. You will have to figure out for yourself which of these structures will be better for your use case (you could probably also come back here and ask as well). Some will work better with static entities some will work better for moving, and you may be able to utilize box2d's broad phase collider.

You are essentially colliding a bounding volume (box or circle) of the players vision with the bounding volumes of the other entities, if it intersects then you send that information to that client.

\$\endgroup\$
  • \$\begingroup\$ thank you for the detailed reply. My biggest concern was overloading the client or providing too much info (see Everquest vs Macroquest for a wonderful reason why this is valid). As Box2d does have notably efficient broad phase detection, I will look deeper into using it versus reinventing wheels as it (per the docs) uses a specially crafted quad-tree setup to help in large object count, 2d environments. So, in short, thank you for your time and well written information! \$\endgroup\$ – Beau B. Jun 14 '18 at 22:14

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.