Detecção de colisão MMO

7

Estou construindo um servidor de jogo MMO para um jogo 2D e atualmente estou implementando a detecção de colisão e gostaria de saber o que devo fazer.

Digamos que eu tenho 1000 jogadores jogando e 10.000 objetos, devo apenas iterar sobre todos eles para determinar se colidimos? Isso parece um pouco caro.

Eu poderia separar o mundo em partes e iterar todos os objetos de cada jogador em sua parte.

Eu gostaria de saber algumas outras idéias ou o que é padrão. Qual é a melhor maneira para um servidor MMO lidar com a detecção de colisão static objects?

Patrick Lorio
fonte
Eu só descobri isso, ele acrescenta que a resposta de David: gamedev.stackexchange.com/questions/3884/...
Patrick Lorio

Respostas:

14
  1. O mundo sendo separado em partes é realmente o primeiro passo que você deve dar, com cada parte sendo tratada separadamente.

  2. Objetos estáticos ? Puramente estático no sentido de que eles nunca se movem e nunca desaparecem? Em seguida, você pode simplesmente incorporar esses objetos em qualquer estrutura de dados que estiver usando para a navegação de jogadores no mundo (como uma grade , malha de navegação ou gráfico de visibilidade ). Não é necessário fazer nenhuma detecção de colisão individual. Isso pode ser feito manualmente pelos projetistas ou automaticamente pelo mecanismo como uma etapa de pré-processamento do pipeline de conteúdo.

  3. Se, por outro lado, você deseja realmente executar a detecção de colisão entre entidades dinâmicas dentro de cada pedaço, dependendo da quantidade esperada de entidades simultâneas, você pode se beneficiar do uso de uma estrutura de dados de particionamento espacial (como um quadtree ou uma grade ) para reduzir a quantidade de entidades que precisam ser iteradas. Em geral, pesquise o tópico mais amplo da detecção de colisão em fase ampla (sem trocadilhos), que inclui as técnicas de divisão espacial mencionadas, além de outras abordagens, como varredura e poda .

David Gouveia
fonte
3
Nota lateral: um subconjunto de todos os mecanismos de física é útil para detectar colisões, mesmo que você não use a física para se mover, você ainda pode usar a detecção de colisões se não quiser escrever sua própria.
Patrick Hughes
11
@PatrickHughes True. Há alguns anos, passei horas tentando fazer com que as interseções OBB-OBB funcionassem corretamente usando o teorema do eixo de separação. Então, em 5 minutos, coloquei o Box2D e resolvi o problema.
David Gouveia
Sem mencionar que eles já implementam banda larga para você.
David Gouveia
11
É prático "desativar" todos os outros cálculos em um mecanismo de física para facilitar isso? Frequentemente, você não deseja tentar executar a física adequada em um servidor MMO, porque os objetos se movem regularmente de maneira descontínua.
Kylotan
11
Eu não disse nada sobre espasmos ou 'estranhos', mas os objetos MMO geralmente precisam se mover descontinuamente porque você precisa encaixá-los em determinadas posições, por exemplo. para teletransporte / zoneamento, ou para corrigir previsões ruins e hackers de velocidade, etc. Eu não uso pacotes de física há anos, mas naquela época era tipicamente bastante difícil lidar com movimentos arbitrários como esse, daí a minha pergunta.
Kylotan