How to let the server inform game clients about other nearby visible players in an efficient way?

Question

I'm working on a multiplayer flash game. The server informs each client what other players are near the player. To do this the server has to check which clients are near each other continuously. The following is what I am using at this moment, as a temporary solution:

private function checkVisibilities()
{
    foreach ($this->socketClients as $socketClient1)
    { //loop every socket client
        if (($socketClient1->loggedIn()) && ($socketClient1->inWorld()))
        { //if this client is logged in and in the world
            foreach ($this->socketClients as $cid2 => $socketClient2)
            { //loop every client for this client to see if they are near
                if ($socketClient1 != $socketClient2)
                { //if it is not the same client
                    if (($socketClient2->loggedIn()) && ($socketClient2->inWorld())
                    { //if this client is also logged in and also in the world
                        if ((abs($socketClient1->getCharX() - $socketClient2->getCharX()) + abs($socketClient1->getCharY() - $socketClient2->getCharY())) < Settings::$visibilities_range)
                        { //the clients are near each other
                            if (!$socketClient1->isVisible($cid2))
       { //not yet visible -> add
                                 $socketClient1->addVisible($cid2);
                            }
                        }
                        else
                        { //the clients are not near each other
                            if ($socketClient1->isVisible($cid2))
                            { //still visible -> remove
                                $socketClient1->removeVisible($cid2);
                            }
                        }
                    }
                    else
                    { //the client is not logged in
                        if ($socketClient1->isVisible($cid2))
                        { //still visible -> remove
                            $socketClient1->removeVisible($cid2);
                        }
                    }    
               }
         }
     }
}

It works fine. However, so far I've only been playing with 2 players at a time. This function is looping every client for every client. So, with 100 players that would be 100 * 100 = 10.000 loops every time the function is run. This doesn't seem the best or most efficient way to do it.

Now I wonder what you folks think about my current setup and if you have any suggestions on a better way of handling these visibilities.

Update: I forgot to mention that the world is infinite. It is actually "the universe". There are no maps. Also, it is a two dimensional (2D) game.

Thanks in advance.

Answer 1

The most straightforward solution is to partition the world into a uniform grid, like so:

_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |

Then insert your objects into any grid tile that they intersect:

_|____|____|____|_
 | @  |    |    |
_|____|____|____|_
 |    |d d |    |
_|____|____|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

Now to do a query for nearby objects, you only need to look at nearby cells. For example, to see who within one tile from the player (@), you only need to check in 9 tiles, not the whole map:

/|////|////|____|_
/|/@//|////|    |
/|////|////|____|_
/|////|d/d/|    |
/|////|////|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

Depending on your world, however, this technique can be quite wasteful: there could be a lot of empty cells. If this becomes a problem, you may want to implement a more complex spatial index.

Answer 2

Try using a quad tree to represent the players' locations.
The wiki article for this is here.
What it does is keeping the objects you give it in space (users) in a tree which partitions the space (plane) as much as needed. As for the infinity problem - nothing in programming is really infinite, so define a border which cannot be passed by the users (go even for a very large number for a coordinate, something that will take a user 100 years or so to get to).

Answer 3

The first thing I would say is that your code looks inside-out. Why do you have a high level game logic function that has to do the grunt-work of checking which clients are logged in and in the world? All that networking stuff should be removed from the game logic so that it's done on a higher level and the in-game logic only has to handle the players who are currently playing and in the world. This leaves you with a simple question: are these 2 players near enough to each other? A simple distance check suffices here, as you already have.

The next thing is to reduce the amount of looping you do. Distance is generally a commutative property so you don't need to check the distance between A and B as well as between B and A. To do this, whereas your first loop goes through all the clients, the second loop only needs to iterate over all the clients that come after the first one. This halves the number of iterations you need to do.

You also don't have to to do this continuously, as you state. You just have to do it often enough to ensure that the game runs smoothly. If movement speed is not all that high then you might only have to do this every few seconds for it to be good enough.

If this is still not good enough for you then some sort of spatial hashing system as described by ianh is a good way of reducing the number of queries you do. A grid is easiest but some sort of tree structure (ideally self-balancing) is another option.