Come gestisci gli oggetti che si spostano tra i quad quando si usano i quadrifili?

Question

Sto provando a utilizzare quadtrees per il rilevamento delle collisioni in un gioco che sto realizzando, ma non sono sicuro di come gestire gli oggetti che potrebbero spostarsi tra diversi quad?

L'unico modo in cui riesco a pensare è deselezionando l'intero albero ogni fotogramma, e quindi aggiungendo tutto di nuovo lì, ma sembra che possa ottenere cpu intensivo e non molto efficiente. Controllate ogni oggetto ogni fotogramma per vedere se si è spostato al di fuori del suo quad attuale, e in tal caso rimuoverlo e leggerlo? Anche in questo caso sembra che possa essere piuttosto inefficiente perché dovresti eseguire controlli di collisione su ogni oggetto in movimento su ogni fotogramma.

Inoltre, per quanto riguarda i quadriflessioni ma non correlati agli oggetti che si muovono in essi, come gestisci più oggetti nello stesso quadrante? La maggior parte dei siti che ho letto su di loro dicono che dovresti avere solo uno, forse due, oggetti in un quad, e se ne ottieni di più, spingili giù nell'albero. Cosa succede se hai avuto una situazione come this? Hai tre cerchi e sono tutti ai bordi del livello sotto di loro in modo che non possano andare più in basso, ma ce ne sono tre tutti nello stesso livello, che la gente dice che non dovresti avere.

Answer 1

Non penso che sia particolarmente inefficiente implementare il tuo suggerimento: controlla se un oggetto si è spostato all'esterno del suo quadruplo, e in tal caso rimuovilo e aggiungilo nuovamente. Qualunque oggetto che si muova da un fotogramma all'altro dovrà avere un rilevamento di collisione su di esso, sicuramente? E le operazioni quadrifoglio vengono eseguite solo se si muove in quad, e il tempo di CPU speso là è probabilmente oscurato dal tempo della CPU facendo più preciso "Does object A touch object B?" calcoli. Quindi non so che puoi fare di meglio.

Sulla tua seconda domanda: non so come altre persone implementino quadree, ma consento agli oggetti di occupare più di un quadruplo, proprio per la ragione che hai dato nel tuo diagramma (quando un oggetto si trova a cavallo di un confine) . Quindi un oggetto ha un "elenco corrente di quad" invece di un "quad corrente".

Answer 2

La rimozione/riaggiunta può essere ottimizzata spostando il quad albero invece di rimuovere completamente l'oggetto dall'albero e quindi aggiungere nuovamente, ovvero passare al quad "padre" e quindi aggiungere il "genitore" se non si adatta al "genitore", vai al "nonno", ecc.

Per quanto riguarda la seconda preoccupazione, avrai bisogno di una certa flessibilità - se tutti e tre sono su un margine, allora puoi li abbassa, ma dovrebbe essere (perdonare il gioco di parole) un caso limite.