Comment laisser le serveur informer les clients du jeu des autres joueurs visibles à proximité de manière efficace?

Question

Je travaille sur un jeu flash multijoueur. Le serveur informe chaque client de ce que les autres joueurs sont à proximité du joueur. Pour ce faire, le serveur doit vérifier quels clients sont proches les uns des autres en permanence. Voici ce que j'utilise actuellement comme solution temporaire:

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

Cela fonctionne bien. Cependant, jusqu'à présent, je n'ai joué qu'avec 2 joueurs à la fois. Cette fonction boucle chaque client pour chaque client. Donc, avec 100 joueurs, ce serait 100 * 100 = 10.000 boucles à chaque exécution de la fonction. Cela ne semble pas être le meilleur ni le plus efficace des moyens.

Maintenant, je me demande ce que vous pensez de ma configuration actuelle et si vous avez des suggestions pour améliorer le traitement de ces visibilités.

Mise à jour: j'ai oublié de mentionner que le monde est infini. C'est en fait "l'univers". Il n'y a pas de cartes. En outre, il s’agit d’un jeu à deux dimensions (2D).

Merci d'avance.

Answer 1

La solution la plus simple consiste à partitionner le monde en une grille uniforme, comme suit:

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

Ensuite, insérez vos objets dans les carreaux de grille qu'ils intersectent:

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

Maintenant, pour faire une requête sur des objets proches, il vous suffit de regarder les cellules proches. Par exemple, pour voir qui se trouve dans une tuile du joueur ( @ ), il vous suffit d’enregistrer 9 tuiles, pas la carte entière:

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

En fonction de votre monde, toutefois, cette technique peut s'avérer très inutile: il peut y avoir beaucoup de cellules vides. Si cela vous pose problème, vous pouvez implémenter un index spatial plus complexe.

Answer 2

La première chose que je dirais, c’est que votre code est à l’envers. Pourquoi avez-vous une fonction logique de jeu de haut niveau qui doit faire le gros du travail consistant à vérifier quels clients sont connectés et dans le monde? Tous ces éléments de mise en réseau doivent être supprimés de la logique de jeu afin d'être appliqués à un niveau supérieur et la logique de jeu ne doit gérer que les joueurs qui jouent actuellement et qui sont dans le monde. Cela vous laisse avec une question simple: ces 2 joueurs sont-ils assez proches les uns des autres? Un simple contrôle à distance suffit ici, comme vous l'avez déjà fait.

La prochaine étape consiste à réduire le nombre de boucles que vous effectuez. La distance est généralement une propriété commutative, vous n'avez donc pas besoin de vérifier la distance entre A et B, ni entre B et A. tous les clients qui viennent après le premier. Cela réduit de moitié le nombre d'itérations à effectuer.

Vous n’avez pas non plus à le faire continuellement, comme vous le dites. Vous devez juste le faire assez souvent pour que le jeu se déroule bien. Si la vitesse de déplacement n’est pas très élevée, vous devrez peut-être le faire toutes les quelques secondes pour qu’elle soit suffisamment bonne.

Si cela ne vous convient toujours pas, alors une sorte de système de hachage spatial tel que décrit par ianh est un bon moyen de réduire le nombre de requêtes que vous effectuez. Une grille est plus simple, mais une autre forme d'arborescence (idéalement auto-équilibrée) est une autre option.

Answer 3

Essayez d’utiliser un arbre quadruple pour représenter les emplacements des joueurs.
L'article du wiki correspondant est ici .
Cela permet de garder les objets que vous lui donnez dans l'espace (utilisateurs) dans un arbre qui partitionne l'espace (plan) autant que nécessaire. En ce qui concerne le problème de l'infini - rien dans la programmation n'est vraiment infini, définissez donc une bordure qui ne peut pas être passée par les utilisateurs (même pour un très grand nombre pour une coordonnée, quelque chose qui prendra un utilisateur d'environ 100 ans). .