¿Cómo permitir que el servidor informe a los clientes de juegos sobre otros jugadores visibles cercanos de manera eficiente?

Question

Estoy trabajando en un juego flash multijugador. El servidor informa a cada cliente qué otros jugadores están cerca del jugador. Para hacer esto, el servidor debe verificar qué clientes están cerca uno del otro continuamente. Lo siguiente es lo que estoy usando en este momento, como una solución temporal:

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);
                        }
                    }       
               }
         }
     }
}

Funciona bien. Sin embargo, hasta ahora solo he jugado con 2 jugadores a la vez. Esta función está enlazando a cada cliente para cada cliente. Entonces, con 100 jugadores, serían 100 * 100 = 10.000 bucles cada vez que se ejecute la función. Esto no parece ser la mejor manera o la más eficiente de hacerlo.

Ahora me pregunto qué piensan ustedes acerca de mi configuración actual y si tienen alguna sugerencia sobre una mejor manera de manejar estas visibilidades.

Actualización: olvidé mencionar que el mundo es infinito. En realidad es " el universo " ;. No hay mapas. Además, es un juego bidimensional (2D).

Gracias de antemano.

Answer 1

La solución más sencilla es dividir el mundo en una cuadrícula uniforme, como la siguiente:

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

Luego inserte sus objetos en cualquier cuadrícula que se intersectan:

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

Ahora para hacer una consulta de objetos cercanos, solo necesitas mirar las celdas cercanas. Por ejemplo, para ver quién está dentro de una ficha del jugador ( @ ), solo necesita registrar 9 fichas, no todo el mapa:

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

Sin embargo, dependiendo de tu mundo, esta técnica puede ser bastante inútil: podría haber muchas celdas vacías. Si esto se convierte en un problema, es posible que desee implementar un índice espacial más complejo.

Answer 2

Lo primero que diría es que su código se ve al revés. ¿Por qué tiene una función de lógica de juego de alto nivel que tiene que hacer el trabajo duro de verificar qué clientes están conectados y en el mundo? Todas esas cosas de redes deben eliminarse de la lógica del juego para que se haga a un nivel superior y la lógica del juego solo tiene que manejar a los jugadores que están jugando actualmente y en el mundo. Esto te deja con una pregunta simple: ¿son estos 2 jugadores lo suficientemente cerca uno del otro? Una simple verificación de distancia es suficiente aquí, como ya lo has hecho.

Lo siguiente es reducir la cantidad de bucles que haces. La distancia es generalmente una propiedad conmutativa, por lo que no necesita verificar la distancia entre A y B, así como entre B y A. Para hacer esto, mientras que su primer bucle atraviesa todos los clientes, el segundo bucle solo debe repetirse. Todos los clientes que vienen después del primero. Esto reduce a la mitad el número de iteraciones que necesita hacer.

Tampoco tienes que hacer esto continuamente, como indicas. Solo debes hacerlo con la frecuencia suficiente para garantizar que el juego se desarrolle sin problemas. Si la velocidad de movimiento no es tan alta, es posible que solo tengas que hacerlo cada pocos segundos para que sea lo suficientemente buena.

Si esto todavía no es lo suficientemente bueno para usted, entonces algún tipo de sistema de hash espacial tal como lo describe ianh es una buena manera de reducir la cantidad de consultas que realiza. Una cuadrícula es la más fácil, pero algún tipo de estructura de árbol (idealmente, el auto-equilibrio) es otra opción.

Answer 3

Intente usar un árbol de quad para representar las ubicaciones de los jugadores.
El artículo wiki para esto es aquí .
Lo que hace es mantener los objetos que le da en el espacio (usuarios) en un árbol que divide el espacio (plano) tanto como sea necesario. En cuanto al problema del infinito, nada en la programación es realmente infinito, por lo tanto, defina un borde que los usuarios no puedan pasar (vaya incluso por un número muy grande para una coordenada, algo que le llevará a un usuario más o menos 100 años). .