Server-side "Fog of War"

Question

I am working on my custom server for my online game and I was wondering if there is any way to accomplish this in a more performant way.

Basically I will be spawning and despawning objects (such as other players) to clients based on the distance between their positions. Basically, if you are within, say, 500 meters away from another character, the server will send you a "Spawn character" packet to spawn that character on your client. If you move more than 500 meters away from that client, the server will send you a despawn packet.

The only way I can think of doing this on the server is a nested for loop. For every character on the server, check every other character position. That's expensive and obviously as the character count grows, so does the time it takes for process the loops.

Can anyone think of any different approach to this that will be better performant? Most survival games don't do this, and you just have all characters spawned on every client, but this allows for ESP hacks (Extra Sensory Perception which basically is a hack that shows you exactly where everyone is, even if the client isn't rendering them because they are far away) and I don't want that as a possibility.

If you need any other information let me know, thanks.

Answer 1

You can tame this in the same way we tame other \$n^2\$ interactions in games, like collision detection: use a spatial partition to break it into smaller, more tractable pieces.

Let's say I divide my world into 500 m x 500 m chunks. As players move around the world, the server keeps track of which chunk each player is in. When a player enters a new chunk, they're removed from the list of players in their previous chunk, and added to the list of players in their new chunk.

Now when we want to notify nearby players, we only need to search the lists of players in the same or adjacent chunks - everyone else on the server is too far away to even consider.

So it's still an \$n^2\$ problem, but with a much smaller \$n\$, proportional to the density of players in a single chunk, rather than the total population of the server.

The more finely you break up the world, the better you can thin down the list of players (or other significant entities) within any given region/radius, but also the more work you need to do to keep everything sorted into their respective buckets. So you'll have some tuning decisions to make based on your typical densities, query ranges, and movement patterns to find the trade-offs that work best for your game's use cases.