How to find and send data about on-screen players to a client in a real-time multiplayer game?

Question

I'm surprised I couldn't find much information on this.

I am making a top-down browser game in which the players see a small section around their player (see the image). Since the player doesn't need to render the players far away that they can't see, it would be unnecessary to send data about them. I want to know how the server should calculate who is near enough to the client that they appear on their screen and therefore receive data from the server about those players.

The way my problem differs from what I have found is that I need to track many players (at least 50 and preferably up to 100) and many can be on screen at one time (assume a maximum of 10 on screen at any one time).

Some assumptions/considerations that are made:

• The players are always moving and positions constantly changing
• Must handle at least 50 players at one time (preferably up to 100)
• Players can drop in and out at random locations so should be able to adapt to this quickly
• Screen sizes vary
• Player input is just movement (but there should be scope for other simple actions)
• Data sent over TCP as will be browser based
• Node.js server

Initially I thought about sending data for all the positions of the players to each player but this seems like a terrible idea with so much unnecessary data being sent - from what I understand the server should be sending as little as possible.

My current strategy (shown in the image) is to have the server periodically (every second for example) calculate the distances between all players to determine those near enough to each other to appear on screen. For the next second, data will only be sent to the client regarding those near it. After the next second, new distances are calculated to decide what to send (and render) for each player.

Some problems to take into account:

• A lot of calculations must be performed by the server for all the players
• Extra information would need to be sent about players just outside the screen to account for any movement between updates
• Interpolation would probably be required
• Different screen sizes will mean that some players can see more than others (the fairness isn't the issue here, but tracking to what distance to let players see)

The main issue is the ability of the server to process all of this with everything else that it must already do. I am not convinced this is a very good way.

This is trivial for off screen entities in a single player game, however for multiplayer games with many players moving at once this becomes much more difficult.

How can I figure out what players are on screen efficiently and what data should be sent regarding this? Or please point me to where I can find information on this.

Answer 1

If you divide the game's map into different chunks then you can map each player's position into a separate data structure for each chunk where every other player a given chunk is visible to every other player within that chunk respectively.

The rest is really up to you (what the size of a chunk is), and in essence each player in a "chunk" or subsection gets the same data so you don't have to re-compute it every tick or so. This makes for constant time lookup and is nice since you don't have to do any distance calculations to check which players are visible for every other player since the size of a chunk will demarcate the region of visibility. This approach is basically quadtrees and games like Minecraft use this approach.

If an entity X moves from position A to position B then you find the chunk where position A was, remove entity X from that chunk and place entity X in the chunk where position B is. This move operation is O(n) in the size of the chunk, but you can probably make it constant time with a hashmap or something clever. The cost of this approach is the space allocated for the quad tree. Finding a chunk is constant time, though.

Also, you may not want to send n(n-1) packets each frame for n players regarding every other player's n positions necessarily if you're concerned about performance too much. The best approach may be to fit all of this data each tick into one giant packet containing the positions of every other player within the same chunk as the player you're sending position data to, so there are as few send() calls as possible (then again, this may not be a huge performance hit either in practice depending on the game). The size of one packet in this case is upper bounded by the num of players in a chunk * size of player packet.

In the worst case there could be 100 players in one chunk in your case, but it's up to you how you divide the map. The smaller the packet the better, and a packet can be up to 1500-65,000 bytes in size so you shouldn't have a problem unless you're dealing with thousands of players/poor network speeds. This is completely dependent on how much data is represented for each player, and how many players there are.

EDIT: But yeah, I wouldn't be concerned at all with sending data for players that aren't visible at all using this approach. It's very practical to send all of surrounding chunks in a game if they have the potential to be visible depending on the size of a chunk compared to your screen's size.