Ajuda com implementação de Quadtree para tratar colisões

joaovirgili
(usa Ubuntu)

Enviado em 30/10/2016 - 06:32h

Boa noite. Eu entendi teoricamente como funciona a quadtree porém estou perdido em como implementá-la. Tenho um trabalho em que devo tratar as colisões de asteroides (Trabalho: https://imgur.com/a/OTUtW) utilizando quadtree ou bsp, no caso escolhi quadtree. Pesquisei diversas vezes por tutoriais de como implementar quadtree mas não encontrei nenhum na internet. Algumas implementações, mas em outras linguagens e não soube traduzir para o C. Corrijam-me se eu estiver errado:
Quadtree é uma árvore de 4 nós, representando a tela e seus 4 hemisférios (NW, NE, SW, SE). Se algum hemisfério possuir um objeto, o mesmo é subdividido recursivamente em 4 hemisférios até que todos os hemisférios sejam um objeto ou não. É difícil de explicar, devo ter me embolado hahaha. Agora, tratando as colisões. À medida que meus objetos vão se movendo eles se movem dentro da árvore também, então quando um objeto tentar ocupar o mesmo lugar de outro na árvore é quando eles se chocam.
Implementação da quadtree:
Em que consistiria esta estrutura? pensei em algo assim:

struct Node {

	Node* filhos[4];

	int widht;

	int height;

	bool obj;

} 

1-ponteiro para os filhos deste nó, que no caso serão 4.
2-o nó tera um tamanho de altura e largura, seu filho será 1/4 teste tamanho.
3-um booleano para verificar se neste nó se encontra ou não o objeto.
A partir daqui estou perdido, não sei o que fazer..

joaovirgili
(usa Ubuntu)

Enviado em 30/10/2016 - 16:53h

ninguem??? :(