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