Thread: Finding closely located points on a grid

I posted this in the Other topics category in the University Math section before posting here. I know that I'm just impatient, but I thought that posting it here too might have a higher chance of finding somebody with an answer.

That said, this is my problem:

I am currently a programming a server for a massive online game, and I want to make it as efficient as possible. The current problem I have to solve involves how the server checks for people close to a given player so that it can send the data about the other players to that player.

The entire game runs on a huge grid, and each player has an absolute X and Y coordinate on this grid.

Here's a simplified, real-world example:
Jack is at point 1,2
Jane is at point 9,5
Bob is at point 3,2

Everyone within 4 units of range of each other (calculated using the distance formula) can talk to each other.
Figure out who is within talking range of who.

Obviously, for this small data set, this is a pretty simple matter. However, the game server is going to be doing this with THOUSANDS of players. I want to know if the current way of doing this could be improved.

Currently the logic that the computer does to determine who is within "talking distance" right now works like this:
The server has a list of all of the players online, and the X and Y values of each on the grid. So, for each player in that list (remember, there's thousands), it compares its X and Y value to the X and Y value of each and every other player online, and determines whether they are in range. Then, it moves on and does this for the next player, and on, and on, until each single player has been individually compared to every other player online.

If that made any sense to you, you can tell why the current way of doing things is woefully inefficient. In the ideal solution to this problem, the computer could find the players within range of every player without looping through the player lists at all.

I tried to make things as simple as possible for people who don't know many computer terms. Is there any less computationally-intensive way of finding who is near who? Much appreciation in advance.

Note: I'm only in 9th grade and have only taken geometry, so if needed I can look into some more advanced math if required to solve this problem. Some explanation of terms would be helpful though

I do not know much in computer programs but you can make a circle of radius 4 unit around each player and any two circles intersect the talk can happened
I think this will be more effective

dose this make sense for you

Detecting that intersection still requires a loop, though... Hmm... Your approach would work quite well if I had a powerful GPU doing the processing, but I can't imagine how you could make that work well on a CPU...