Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C# / VB.NET - XNA & Vb.net 2D ottimizzazione collisioni
Forum - C# / VB.NET - XNA & Vb.net 2D ottimizzazione collisioni

Avatar
Garu (Normal User)
Newbie


Messaggi: 13
Iscritto: 02/08/2011

Segnala al moderatore
Postato alle 21:30
Venerdì, 13/04/2012
Salve a tutti, sto creando un semplice sparatutto in 2D vista dall'alto usando xna.
Il gioco è molto semplice, i nemici ti inseguono e tu gli spari, nulla di più basilare, però è sorto un problema, i nemici mentre ti inseguono spesso si sovrappongono , il che non è molto "professionale".
Ho risolto il problema in questo modo, ma le prestazioni si sono ridotte a un decimo, specialmente se in presenza di molti oggetti, anche perchè se ho 1000 oggetti dovrò fare 1000x999 ( O(n^2) ) cicli per controllarli tutti (o sbaglio).


Codice sorgente - presumibilmente VB.NET

  1. [Code] Private Sub Collisioni_Zombie(ByVal i As Integer)
  2.  
  3.         For i2 As Integer = 0 To Lista_Zombie.Count - 1
  4.             If Lista_Zombie(i2).IsVisible = True Then ' IS visible è una proprietà dell'oggetto calcolata prima del ciclo
  5.                 If Distanza(Lista_Zombie(i).Posizione, Lista_Zombie(i2).Posizione) <= 16 Then 'I nemici sono 32x32 e più o meno tondi, quindi questo è il metodo più performante che ho trovato per rilevare le collisioni
  6.                     Sposta_Zombie(Lista_Zombie(i), Lista_Zombie(i2), Lista_Zombie(i2).Velocità * 2) ' Questo sposta il nemico in base alla posizione del oggetto con cui collide
  7.                 End If
  8.             End If
  9.         Next
  10.     End Sub[/Code]




Il ciclo:
Codice sorgente - presumibilmente VB.NET

  1. [Code]
  2.    For i As Integer = 0 To Lista_Zombie.Count - 1
  3.             Collisioni_Zombie(i)
  4. Next
  5.  
  6.  [/Code]


Ultima modifica effettuata da Garu il 13/04/2012 alle 21:34
PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 22:40
Lunedì, 16/04/2012
Il problema purtroppo non è tra quelli banalmente ottimizzabili.

Come hai ben intuito, si tratta di un'operazione intrinsecamente quadratica.

Esiste però un modo per ottimizzare il calcolo basandosi su una suddivisione in due fasi:

- Broad phase: determino una sottoregione dello spazio contenente il mio oggetto
- Narrow phase: eseguo la collision detection solo nella regione corrente.


Come funziona?

Bisogna inventarsi un modo di suddividere lo spazio, per semplificare ti illustro il metodo con alberi binari.
Mettiamo che il tuo mondo si estende in 2 dimensioni, con X compresa tra 1 e 128 e Y compresa tra 1 e 128 (sono potenze di 2 per semplificare i prossimi calcoli, in realtà puoi avere una scala arbitraria). Un oggetto avrà coordinate (x,y).

Costruisco un albero binario in questo modo:
- La foglia dell'albero è una List di oggetti vuota
- L'albero ha profondità 3
- Ogni nodo intermedio ha esattamente 2 figli
- Ogni nodo ha un numero costante che chiamo "discriminante"
- La discriminante di ogni livello è calcolata come il la media di due valori Min e Max
- La discriminante della radice è la media tra 1 e 128, cioè 64
- La discriminante del figlio a sinistra è la media tra 1 e 64 (32), la discriminante del figlio a destra è la media tra 65 e 128 (96)
- Procedi allo stesso modo per i figli di secondo livello


Riempio l'albero così:
- Prendo un oggetto dall'insieme
- Se x < discriminante del nodo corrente scelgo il nodo a sinistra, altrimenti a destra
- Attraverso tutto l'albero fino alla foglia
- Inserisco l'oggetto corrente nella lista della foglia ottenuta

Procedi così per tutti gli oggetti.

Alla fine dell'inserimento, avrai un certo numero di liste, ad esempio una lista che contiene tutti gli oggetti la cui X è compresa tra 1 e 16, una lista che comprende da 17 a 32, una che va da 33 a 48 e così via…

Quando vai a fare il test delle collisioni, puoi farlo esclusivamente una lista per volta, o al massimo puoi confrontare gli oggetti con quelli della lista corrente e delle due liste di fianco. In questo modo elimini una buona parte degli oggetti che sono sicuramente troppo lontani per collidere.

Quanto pesa tutto questo casino?
La costruzione di un albero costa O(N) dove N è il numero di nodi. L'aggiornamento di un oggetto all'interno dell'albero puoi farla solo quando la sua X esce dal range della sua lista, quindi non è detto che tu debba reinserire gli oggetti ad ogni update, ma puoi limitarti a reinserire solo gli oggetti che si sono spostati oltre il proprio range (prima devi toglierli dalla lista corrente, altrimenti hai dei simpatici bug con oggetti che si moltiplicano per magia).
La ricerca delle collisioni, considerando una sola lista (o un numero costante di liste ragionevolmente piccolo) costa O(log2 N). Tutto il processo, nel caso peggiore, costa N * log2 N, che è un pochino meglio del precedente N^2.

In realtà invece di un albero puoi semplicemente stabilire a priori un numero fissato di liste e fare gli inserimenti semplicemente confrontando i range, ma in questo modo avresti un numero di confronti (per inserire gli oggetti) che è O(N), perciò non avresti una ottimizzazione sostanziale rispetto a quella invece ottenibile con l'albero binario.
Se il numero di liste è piccolo (diciamo poche decine), potresti fare un trick con la manipolazione di bit e ottenere un boost prestazionale notevole, pari a O(1) per l'inserimento, ma non sarebbe un algoritmo scalabile per N oggetti e per mondi di dimensioni arbitrarie.

Per ulteriori ottimizzazioni, potresti considerare un albero 4-ario, cioè invece di avere il solo discriminante per la X, puoi aggiungere il discriminante anche per la Y e i rami dell'albero coprirebbero così una griglia bidimensionale.

In questo modo invece di Log2N hai Log4N che è parecchio più conveniente se hai tanti oggetti.


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM Quote
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Segnala al moderatore
Postato alle 8:25
Martedì, 17/04/2012
Uffa, TheKaneB mi ruba le domande interessanti...


"Infelici sono quelli che hanno tanto cervello da vedere la loro stupidità."
(Fligende Blatter)

"Dubitare di se stessi è il primo segno d'intelligenza."
(Ugo Ojetti)
PM Quote
Avatar
Garu (Normal User)
Newbie


Messaggi: 13
Iscritto: 02/08/2011

Segnala al moderatore
Postato alle 16:42
Mercoledì, 18/04/2012
Testo quotato

Postato originariamente da TheKaneB:

Il problema purtroppo non è tra quelli banalmente ottimizzabili.

Come hai ben intuito, si tratta di un'operazione intrinsecamente quadratica...



Grazie mille, prendendo spunto dal tuo suggerimento ho creato un metodo simile e comunque molto efficace :hail:

PM Quote