Is there a "Least Terrible Method" for sharing Entities over Network?

Question

(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!

Answer 1

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:

• R-trees
• ball trees
• kd-trees
• quad-trees/oct-trees
• spatial-subdivision/spatial hashing (which is the working version of your #2)

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.