Se fossi in te comincerei fuori implementando un (binario partizione di spazio) semplice albero BSP. Dato che stai lavorando in 2D, i controlli bound box sono molto veloci.È fondamentalmente bisogno di tre classi: CBspTree, CBspNode e CBspCut (non proprio necessaria)
- CBspTree ha un'istanza nodo principale della classe CBspNode
- CBspNode ha un'istanza di CBspCut
- CBspCut simboleggiare come si taglia un set in due set disgiunti. Questo può essere risolto con precisione introducendo il polimorfismo (ad esempio CBspCutX o CBspCutY o qualche altra linea di taglio). CBspCut ha anche due CBspNode
L'interfaccia verso il mondo diviso sarà attraverso la classe albero e può essere una buona idea per creare un altro strato in cima a quello, nel caso in cui si vorrebbe sostituire il BSP soluzione con es un albero quadruplo. Una volta che ci stai imparando. Ma nella mia esperienza, un BSP andrà benissimo.
Ci sono diverse strategie su come memorizzare i tuoi oggetti nell'albero. Ciò che intendo è che puoi scegliere di avere ad es. una sorta di contenitore in ogni nodo che contiene riferimenti agli oggetti che occupano quell'area. Ciò significa però (come ti stai chiedendo) che gli oggetti di grandi dimensioni occuperanno molte foglie, cioè ci saranno molti riferimenti a oggetti di grandi dimensioni e oggetti molto piccoli verranno mostrati alle foglie singole.
Nella mia esperienza questo non ha un impatto così grande. Certo che conta, ma dovresti fare dei test per verificare se è davvero un problema o meno. Sareste in grado di aggirare questo lasciando semplicemente quegli elementi ai nodi ramificati nell'albero, cioè non li memorizzerete su "livello foglia". Ciò significa che troverai quegli oggetti veloci mentre attraversi l'albero.
Quando si tratta della prima domanda. Se si utilizzerà questa suddivisione per i test di collisione e nient'altro, suggerisco che le cose che non possono mai scontrarsi non vengano mai inserite nell'albero. Un missile, ad esempio, come dici tu, non può scontrarsi con un altro missile. Il che significherebbe che non devi nemmeno immagazzinare il missile nell'albero.
Tuttavia, si potrebbe voler usare il bsp anche per altre cose, non lo si è specificato, ma tenetelo a mente (per il prelievo di oggetti con, ad esempio, il mouse). Altrimenti, propongo di archiviare tutto nel bsp e di risolvere la collisione in seguito. Basta chiedere al bsp di un elenco di oggetti in una certa area per ottenere un insieme limitato di possibili candidati alla collisione ed eseguire il controllo dopo di ciò (supponendo che gli oggetti sappiano con cosa possono scontrarsi, o qualche altro meccanismo esterno).
Se si vuole accelerare le cose, è necessario anche prendersi cura di merge e dividere, vale a dire quando le cose vengono rimossi dall'albero, un sacco di nodi diventerà vuoto o il numero di elementi di seguito alcune il livello del nodo diminuirà al di sotto di qualche soglia di unione. Quindi si desidera unire due sottoalberi in un nodo contenente tutti gli elementi. La divisione avviene quando si inseriscono oggetti nel mondo. Quindi, quando il numero di elementi supera la soglia di splitting, introduci un nuovo taglio, che divide il mondo in due. Queste soglie di unione e divisione dovrebbero essere due costanti che è possibile utilizzare per ottimizzare l'efficienza dell'albero.
L'unione e la divisione vengono utilizzate principalmente per mantenere l'albero bilanciato e per assicurarsi che funzioni il più efficientemente possibile in base alle sue specifiche. Questo è davvero ciò di cui hai bisogno di preoccuparti. Spostare le cose da una posizione e quindi aggiornare l'albero è imo veloce. Ma quando si tratta di unire e dividere, potrebbe diventare costoso se lo si fa troppo spesso.
Questo può essere evitato introducendo una sorta di lazy merge e split system, cioè si ha qualche tipo di flag sporco o conteggio delle modifiche. Raccogli tutte le operazioni che possono essere dosate, ovvero spostare 10 oggetti e inserire 5 potrebbe essere un lotto.Una volta terminato il gruppo di operazioni, si controlla se l'albero è sporco e quindi si esegue l'operazione di unione e/o divisione.
Invia alcuni commenti se vuoi che spieghi ulteriormente.
Cheers!
Modifica
ci sono molte cose che possono essere ottimizzate nell'albero. Ma come sai, l'ottimizzazione prematura è la radice di tutto il male. Quindi inizia semplice. Ad esempio, è possibile creare un sistema di callback generico che è possibile utilizzare mentre si attraversa l'albero. In questo modo non devi eseguire una query sull'albero per ottenere un elenco di oggetti che corrispondono alla "domanda" della casella associata, ma puoi semplicemente attraversare l'albero ed eseguire quella richiamata ogni volta che colpisci qualcosa. "Se questa casella limite sto fornendo interseca voi, quindi eseguire questo callback con questi parametri"