# How to efficiently solve "close" players/items in an online game without iterating through all of them?

I have an online game server that works as follows:

1. Once a player connects, he is in one of predefined sessions (consider them physical location, e.g. Island, Underground location, etc.).
2. Then any action (movement, attack) is always broadcasted to all other players in the same session. Also when he enters a session, all items dropped in that session are sent to him, as well as players who are there.

This is simple and easy but in the client, the concept of splitting the game into locations is ruining the experience of "one world", if you know what I mean. I am trying to figure out a way how to always broadcast/receive data only about objects that are close enough but I realize that iterating through all players/items everytime and comparing the distance would be a nonsense.

Is there any standard approach that I could use?

• You need a data structure that will return items within a circle of specified size. I'm not quite sure what that data structure would be, though. Sep 5, 2018 at 14:49
• Sep 5, 2018 at 14:52
• against fixed locations - any spatial indexing should wprk well - against dynamic locations then you have to weight up the cost of maintaining a spatial index over just iterating over everything
– jk.
Sep 5, 2018 at 14:52
• @RobertHarvey Thank you. I will take a look. I am just afraid if running these for everything would not be also costly. Sep 5, 2018 at 14:54
• Sep 5, 2018 at 15:38

The standard approach is to divide your world up into large squares/cubes and keep track of which each player is in.

You can then iterate over the players in the square the player is in, rather than all the players in the world.

The problem comes near the edges of the square. Here you need to check adjacent squares. There are some clever tricks where you have two overlapping grids of squares if you need to optimise.

Boxes are efficient because your players/objects will have x,y(,z) coordinates. A simple comparison is all that's needed to know when they move out of one box and into another.

If required once you have the list of 'nearby' players, you can then calculate the actual distance to each other player and exclude the 'corner' ones

Here is a good article on the subject:

http://gameprogrammingpatterns.com/spatial-partition.html

For example a simplistic approach

List<Square> squares

class Square
{
public int x; //grid position of square
public int y; //grid position of square
public double top; //game world limits of square
public double bottom;
public double left;
public double right;
List<Player> Players // players in the square
}

Player.Update()
{
if(position.x > mySquare.right) { //move to next square }
}

Game.FindNearbyPlayers
{
var players = player.MySquare.Players()