A resposta certa depende um pouco do jogo real que você está projetando, e escolher um sobre o outro realmente exigirá a implementação de ambos e a criação de perfis para descobrir qual é mais eficiente em termos de tempo ou espaço em seu jogo específico.
A detecção de grade parece se aplicar apenas à detecção de colisões entre objetos em movimento e um fundo estático. A maior vantagem disso é que o plano de fundo estático é representado como uma matriz de memória contígua e cada pesquisa de colisão é O (1) com boa localidade se você precisar fazer várias leituras (porque as entidades cobrem mais de uma célula na grade). A desvantagem, se o fundo estático for grande, é que a grade pode ser um desperdício de espaço.
Se, em vez disso, você representar o plano de fundo estático como quadtree, o custo de pesquisas individuais aumentará, mas como grandes blocos de plano de fundo ocupam uma pequena quantidade de espaço, os requisitos de memória diminuem e, portanto, mais fundo pode ficar no cache. mesmo que sejam necessárias 10 vezes mais leituras para fazer uma pesquisa nessa estrutura, se estiver tudo no cache, ainda será 10 vezes mais rápido que uma única pesquisa com uma falta de cache.
Se eu tivesse que escolher? Eu iria com a implementação da grade, porque é simples e estúpido, é melhor gastar meu tempo com outros problemas mais interessantes. Se eu perceber que meu jogo está um pouco lento, farei alguns perfis e verei o que poderia ser útil. Se parece que o jogo está gastando muito tempo detectando colisões, eu tentaria outra implementação, como um quadtree (depois de esgotar todas as correções fáceis primeiro) e descobrir se isso ajudou.
Edit: Eu não tenho idéia de como a detecção de colisão de grade está relacionada à detecção de colisões de várias entidades móveis. Em vez disso, responderei como um índice espacial (Quadtree) melhora o desempenho da detecção em relação à solução iterativa. A solução ingênua (e normalmente perfeitamente bem) é mais ou menos assim:
foreach actor in actorList:
foreach target in actorList:
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Obviamente, isso tem desempenho em torno de O (n ^ 2), com n o número de atores que estão atualmente vivos no jogo, incluindo balas, naves espaciais e alienígenas. Também pode incluir pequenos obstáculos estáticos.
Isso funciona extraordinariamente bem, desde que o número de itens seja razoavelmente pequeno, mas começa a parecer um pouco ruim quando há mais do que algumas centenas de objetos a serem verificados. 10 objetos resultam em apenas 100 verificações de colisão, 100 resultados em 10.000 verificações. 1000 resulta em um milhão de cheques.
Um índice espacial (como quadras) pode enumerar com eficiência os itens que coleta de acordo com as relações geométricas. isso mudaria o algoritmo de colisão para algo como isto:
foreach actor in actorList:
foreach target in actorIndex.neighbors(actor.boundingbox):
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
A eficiência disso (assumindo uma distribuição uniforme de entidades): geralmente é O (n ^ 1,5 log (n)), uma vez que o índice leva em torno das comparações log (n) para percorrer, haverá cerca de sqrt (n) vizinhos para comparar , e não há atores para verificar. Realisticamente, porém, o número de vizinhos é sempre bastante limitado, pois se ocorrer uma colisão, na maioria das vezes um dos objetos é excluído ou movido para longe da colisão. assim você obtém apenas O (n log (n)). Para 10 entidades, você faz (aproximadamente) 10 comparações, para 100, você faz 200, para 1000, você faz 3000.
Um índice realmente inteligente pode até combinar a pesquisa de vizinhos com a iteração em massa e executar um retorno de chamada em cada entidade de interseção. Isso fornecerá um desempenho de aproximadamente O (n), pois o índice está sendo verificado uma vez em vez de consultado n vezes.
Desculpe por ressuscitar o fio antigo, mas as grades antigas simples do IMHO não são usadas com frequência suficiente para esses casos. Há muitas vantagens em uma grade, pois a inserção / remoção de células é muito barata. Você não precisa se preocupar em liberar uma célula, pois a grade não tem como objetivo otimizar representações esparsas. Eu digo que, tendo reduzido o tempo para selecionar uma série de elementos em uma base de código herdada de mais de 1200ms para 20ms, basta substituir o quad-tree por uma grade. Para ser justo, porém, esse quad-tree foi realmente mal implementado, armazenando uma matriz dinâmica separada por nó de folha para os elementos.
O outro que eu acho extremamente útil é que seus algoritmos clássicos de rasterização para desenhar formas podem ser usados para fazer pesquisas na grade. Por exemplo, você pode usar a rasterização de linha de Bresenham para procurar elementos que cruzam uma linha, a rasterização da linha de varredura para descobrir quais células cruzam um polígono etc. Como eu trabalho muito no processamento de imagens, é muito bom poder usar exatamente o mesmo código otimizado que uso para plotar pixels em uma imagem, como para detectar interseções contra objetos em movimento em uma grade.
Dito isto, para tornar uma grade eficiente, você não precisa de mais de 32 bits por célula da grade. Você poderá armazenar um milhão de células em menos de 4 megabytes. Cada célula da grade pode apenas indexar o primeiro elemento na célula e o primeiro elemento na célula pode indexar o próximo elemento na célula. Se você estiver armazenando algum tipo de container completo com cada célula, isso torna explosivo o uso e as alocações de memória rapidamente. Em vez disso, você pode simplesmente fazer:
Igual a:
Ok, vamos aos contras. Estou admitindo isso com uma tendência e preferência em relação às grades, mas a principal desvantagem é que elas não são escassas.
O acesso a uma célula específica da grade, dada uma coordenada, é de tempo constante e não requer a descida de uma árvore que é mais barata, mas a grade é densa, não esparsa; portanto, você pode precisar verificar mais células do que o necessário. Em situações em que seus dados são muito escassamente distribuídos, a grade pode exigir uma verificação muito maior para descobrir os elementos que se cruzam, como uma linha ou um polígono preenchido, um retângulo ou um círculo delimitador. A grade precisa armazenar essa célula de 32 bits, mesmo que esteja completamente vazia, e quando você está fazendo uma consulta de interseção de forma, precisa verificar essas células vazias se elas interceptarem sua forma.
O principal benefício do quad-tree é, naturalmente, sua capacidade de armazenar dados esparsos e subdividir apenas o necessário. Dito isto, é mais difícil de implementar muito bem, especialmente se você tiver coisas se movendo em todos os quadros. A árvore precisa subdividir e liberar nós filhos em tempo real de maneira muito eficiente, caso contrário, ela se degrada em uma grade densa que desperdiça sobrecarga para armazenar links pai> filho. É muito viável implementar um quad-tree eficiente usando técnicas muito semelhantes às que descrevi acima para a grade, mas geralmente será mais demorado. E se você fizer da mesma maneira que eu faço na grade, isso também não é necessariamente ideal, pois isso levaria a uma perda na capacidade de garantir que todos os quatro filhos de um nó quad-tree sejam armazenados contiguamente.
Além disso, tanto uma árvore quádrupla quanto a grade não fazem um trabalho magnífico se você tiver vários elementos grandes que abrangem grande parte da cena inteira, mas pelo menos a grade permanece plana e não se subdivide no enésimo grau nesses casos . A árvore quádrupla deve armazenar elementos nos galhos e não apenas nas folhas para lidar razoavelmente com esses casos; caso contrário, ela deseja subdividir-se como louca e degradar a qualidade extremamente rapidamente. Existem mais casos patológicos como esse que você precisa resolver com uma árvore quádrupla, se quiser que ele lide com a maior variedade de conteúdo. Por exemplo, outro caso que pode realmente tropeçar em uma árvore quádrupla é se você tiver um monte de elementos coincidentes. Nesse ponto, algumas pessoas simplesmente recorrem ao estabelecimento de um limite de profundidade para suas árvores quádruplas para evitar que elas se subdividam infinitamente. A grade tem um apelo de que ele faz um trabalho decente,
A estabilidade e a previsibilidade também são benéficas no contexto do jogo, já que às vezes você não quer necessariamente a solução mais rápida possível para o caso comum, se ocasionalmente pode levar a soluços nas taxas de quadros em cenários de casos raros, em comparação a uma solução razoavelmente rápida. mas nunca leva a esses soluços e mantém as taxas de quadros suaves e previsíveis. Uma grade possui esse tipo de qualidade posterior.
Com tudo isso dito, eu realmente acho que depende do programador. Com coisas como grade x quad-tree ou octree x kd-árvore x BVH, meu voto é sobre o desenvolvedor mais prolífico com um histórico de criação de soluções muito eficientes, independentemente da estrutura de dados que ele / ela usa. Também há muito no nível micro, como multithreading, SIMD, layouts de memória compatíveis com cache e padrões de acesso. Algumas pessoas podem considerar esses micro, mas eles não necessariamente têm um micro impacto. Tais coisas podem fazer uma diferença de 100x de uma solução para a outra. Apesar disso, se eu recebesse alguns dias pessoalmente e me dissessem que eu precisava implementar uma estrutura de dados para acelerar rapidamente a detecção de colisão de elementos que se movem por todos os quadros, seria melhor nesse curto espaço de tempo implementar uma grade do que um quad -árvore.
fonte