Estou bem ciente de como detectar se dois ou mais objetos 2D colidem, mas estou interessado em como decidir se deve verificar se há uma colisão. Em projetos anteriores, eu tinha todos os objetos comparados com outros objetos (eu sei, O (n ^ 2) nível de estupidez) e isso criou uma jogabilidade menos do que fluida.
Vários fóruns elogiam a grandeza de Quadtrees, B-Trees e qualquer outro tipo de árvore ou estrutura que você possa imaginar.
Qual é a estrutura mais eficiente para determinar se uma colisão deve ser verificada?
2d
collision-detection
data-structure
Mike Cluck
fonte
fonte
Respostas:
Para um jogo 2D, a menos que os objetos 2D tenham uma distribuição muito pesada em um lado do mapa, uma grade uniforme é quase sempre o caminho a percorrer. A complexidade da memória é direta (proporcional às dimensões do seu mapa) e com uma distribuição razoável, possui O (1) tempo de pesquisa e uma média de log (numberOfObjects / (linhas * colunas)) ^ 2 testes de interseção feito por célula. Você pode decidir verificar apenas as células que tiveram um objeto movido nelas, o que torna a geometria estática muito mais eficiente. É fácil modificar uma grade uniforme em tempo real (muito menos trabalhoso do que em soluções baseadas em árvores) e é mais simples de implementar. A única vez em que eu diria para não usá-lo em um jogo 2D é quando os requisitos de memória de uma grade uniforme se tornam muito grandes (diga um sim espacial onde os níveis são escassos, mas enormes).
fonte
Mecanismos de física 2D, como Box2D e Chipmunk, fazem uso pesado de um mapa de hash espacial
consulte http://chipmunk-physics.net/release/ChipmunkLatest-Docs/#CollisionDetection para referência. As demos dos esquilos incluem um visualizador de hash espacial realmente bom, que deixa muito claro como elas funcionam.
fonte
Se o seu mundo tem uma dimensão muito "longa" (chamada X), em comparação com outras, você pode manter os objetos em uma lista ordenada que pode ser reorganizada à medida que se movem e, em seguida, a detecção de colisão significa apenas verificar objetos que sobreposição no eixo X.
Outra possibilidade é manter listas de objetos ativos / passivos e não se incomodar com os objetos passivos (que não estão se movendo).
Se todos eles são objetos de tamanho médio que são visíveis para o jogador na tela, tudo vs tudo provavelmente não é tão ruim.
Fora isso, estou com Darcy, uma grade uniforme é boa.
fonte