Como deixar o servidor informar os clientes jogo sobre outros jogadores próximos visíveis de forma eficiente?

Question

Eu estou trabalhando em um jogo flash multiplayer. O servidor informa cada cliente o que outros jogadores estão perto do jogador. Para isso, o servidor tem que verificar quais clientes estão próximos uns dos outros de forma contínua. O seguinte é o que eu estou usando neste momento, como uma solução temporária:

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

Ele funciona muito bem. No entanto, até agora eu só estava jogando com 2 jogadores ao mesmo tempo. Esta função é looping cada cliente para cada cliente. Assim, com 100 jogadores que seria 100 * 100 = 10.000 laços cada vez que a função é executada. Isso não parece o melhor ou mais eficiente maneira de fazê-lo.

Agora eu me pergunto o que as pessoas pensam sobre minha configuração atual e se você tem alguma sugestão sobre a melhor maneira de lidar com estas visibilidades.

Update: Esqueci de mencionar que o mundo é infinito. Na verdade, é "o universo". Não existem mapas. Além disso, é um dimensões (2D) o segundo jogo.

Agradecemos antecipadamente.

Answer 1

A solução mais simples é dividir o mundo em uma grade uniforme, assim:

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

Em seguida, insira seus objetos em qualquer telha grade que eles se cruzam:

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

Agora, para fazer uma consulta para objetos próximos, você só precisa olhar para as células vizinhas. Por exemplo, para ver quem dentro de uma telha do jogador (@), você só precisa verificar em 9 azulejos, e não todo o mapa:

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

Dependendo do seu mundo, no entanto, esta técnica pode ser muito desperdício: poderia haver um monte de células vazias. Se isso se torna um problema, você pode querer implementar uma mais complexa espacial índice .

Answer 2

A primeira coisa que eu diria é que sua aparência código dentro-out. Por que você tem uma função lógica de alta nível de jogo que tem a ver o grunhido com o trabalho de verificação de que os clientes está logado e no mundo? Todas as coisas que a rede deve ser removido da lógica do jogo de modo que ele é feito em um nível mais elevado e a lógica do jogo só tem de lidar com os jogadores que estão atualmente jogando e no mundo. Isso deixa você com uma pergunta simples: são estes 2 jogadores perto o suficiente para o outro? Uma simples verificação distância suficiente aqui, como você já tem.

O próximo passo é reduzir a quantidade de looping que você faz. Distância é geralmente uma propriedade comutativa, assim você não precisa verificar a distância entre A e B, bem como entre B e A. Para fazer isso, enquanto o seu primeiro circuito passa por todos os clientes, o segundo loop só precisa iterar todos os clientes que vêm após o primeiro. Este metades do número de iterações que você precisa fazer.

Você também não tem que fazer isso de forma contínua, como você estado. Você apenas tem que fazê-lo com freqüência suficiente para garantir que o jogo corra bem. Se a velocidade de movimento não é tão alta, então você só pode ter que fazer isso a cada poucos segundos para que seja bom o suficiente.

Se isso ainda não é bom o suficiente para você, então algum tipo de sistema hashing espacial como descrito por ianh é uma boa maneira de reduzir o número de consultas que você faz. A grade é mais fácil, mas algum tipo de estrutura de árvore (o ideal de auto-equilíbrio) é outra opção.

Answer 3

Tente usar uma árvore quad para representar localizações dos jogadores.
O artigo wiki para isso é aqui .
O que ele faz é manter os objetos que lhe dão no espaço (usuários) em uma árvore que partições do espaço (avião), tanto quanto necessário. Quanto ao problema infinito - nada na programação é realmente infinito, então definir uma fronteira que não podem ser passados ??pelos usuários (ir mesmo para um número muito grande de uma coordenada, algo que terá um usuário 100 anos ou mais para chegar ao) .