Collision Detection
Questo articolo tratta di un'importante quanto fondamentale componente della programmazione di giochi, ovvero la rilevazione delle collisioni (in english: collision detection).Spieghiamo subito. Le collisioni, in un gioco, avvengono quando due oggetti si toccano; pensate, ad esempio, ad un'astronave che viene a contatto con una nave nemica o un meteorite, la collisione di questi due oggetti provocheranno l'innesco di un evento, ad esempio un'esplosione. La questione mi si e' posta durante la stesura del codice di un gioco, il DarkBattle, (lo trovate in darkbattle.php) che e' pero' rimasto ad un livello embrionale. Con questo articolo spieghero' perche' decidere se due oggetti si stanno toccando, non sia cosi' semplice come dirlo. Le librerie grafiche che utilizzo sono le SDL ma il discorso e' generale, per cui puo' essere applicato a tutte le librerie grafiche che permettono di leggere singoli pixel di un'immagine. Comunque non e' detto che in futuro non debba scrivere qualche articolo proprio sulle SDL. Utilizziamo l'esempio di un'astronave e di una nave nemica. I due oggetti in questione avranno una forma ben definita, magari un po' complessa, ad ogni modo, qualunque forma abbiano, le due immagini saranno sempre contenute dentro dei rettangoli che non vediamo in quanto riempiti di colore neutro (che diverra' poi, nel gioco, trasparente). Perche' c'e' questo rettangolo?? Perche' le immagini, di qualunque formato esse siano, sono definite da un'area (o canvas) rettangolare. Se disegnate un cerchio con Gimp, ad esempio, non potete salvare solo il cerchio, ma dovete salvare il rettangolo che contiene il cerchio, proprio perche' i formati di immagini prevedono solo immagini rettangolari. Torniamo alla nostra astronave, poniamo che sia questa (in ASCII Art): W Questo rettangolo di larghezza W e altezza H contiene l'immagine dell'astronave. Ovviamente, in un esempio piu' reale, la scelta di W e H e' tale da ridurre al minimo l'area del rettangolo. Come dicevo, il colore di sfondo del rettangolo verra' utilizzato come Key Color e non verra' visualizzato. Le due problematiche fondamentali in un algoritmo che rilevi la collisione tra due spite sono:
Passiamo subito ad analizzare la prima questione. Come facciamo, cioe', a capire quando due sprite si toccano "veramente"?? A noi interessa sapere se e' avvenuta una collisione tra le immagini che sono _dentro_ i rettangoli, non ci basta constatare la collisione dei rettangoli, altrimenti il gioco dara' l'impressione di essere parecchio impreciso e vedremmo, ad esempio, la nostra astronave esplodere "inutilmente" solo perche' un missile e' passato di fianco! Allora ho implementato un algoritmo abbastanza semplice ma molto efficace, e -a parte le ottimizzazioni- credo che sia lo stesso algoritmo utilizzato dai programmatori di giochi "seri". Iniziamo ad illustrare lo schema teorico di tale algoritmo. Poniamo che il Key Color sia il nero, il nostro sprite utilizzera' percio' tutti i colori del mondo _tranne_ il nero, altrimenti, durante la fase del gioco, le parti nere diverranno trasparenti! Possiamo quindi costruirci una matrice WxH dove W e H rappresentano la largezza e l'altezza dell'immagine in pixel. Questa matrice sara' percio' composta da un numero di elementi che e' uguale al numero di pixel dell'immagine. Adesso associamo il valore 0 ad ogni pixel nero dell'immagine e il valore 1 ad ogni pixel diverso dal colore nero. La nostra matrice sara' quindi fatta cosi': Immagine Matrice W Dal punto di vista della programmazione la matrice sara' un doppio array, di dimensioni [W][H]. Adesso che abbiamo questa matrice cosa ne facciamo? Poniamo che la matrice di una nave nemica sia questa: Immagine Matrice W e che la posizione dell'astronave nemica e della mia sia questa: La zona contrassegnata da "#" e' la parte di piano delimitata dalla sovrapposizione delle due immagini. Questa zona, come si deduce (spero) dal disegno, e' larga "a" pixel e alta "b". Determinare i valori di "a" e di "b" e' piuttosto semplice, lo vedremo in un altro articolo. Cio' che ci interessa e' capire se si sono sovrapposte anche le immagini _dentro_ i rettangoli. Siamo al nocciolo della questione, attenzione quindi... Prendo le mie due matrici, quella associata alla nostra astronave e quella associata alla nave nemica. Di ogni matrice prendo la relativa sottomatrice axb calcolando i giusti offset (dati dalle coordinate degli sprite). Adesso inizio a prendere ogni elemento "i" di ogni matrice e li sottopongo all'AND logico. Le possibilita' sono le seguenti: Legenda: i_N -> elemento "i" della nave nemica Possibilita': 1. Se i_N = 0 e i_A = 0 Allora: i_N AND i_A = 0 Che non e' altro che il risultato della tabellina dell'AND: Spiegando i vari casi: 1. I pixel "i" dell'immagine della nave nemica e della mia astronave sono entrambi neri ...ma se quindi, come nel caso 4, i pixel nel punto "i" sono entrambi colorati, cio' significa che gli sprite si toccano (sporcaccioni...) e la collisione e' avvenuta! Per fiketteria mostriamo l'operazione con le matrici dell'ultimo caso. Non ridisegno le astronavi che cozzano perche' tanto avete capito.... 1111110 0001000 0001000 la prima matrice potrebbe essere l'ala di un'astronave mentre la seconda un "proiettile". Comunque sia, dopo l'AND logico, la matrice risultante possiede ben due "1", cio' significa che ci sono 2 collisioni, per cui possiamo innescare l'evento piu' appropriato (tipo un esplosione o un fumetto dell'astronave colpita che dice "ma chi t'e' muort!"). Il concetto quindi non e' di per se' complicato, ma come dicevo riguardo alle problematiche di questo algoritmo, sara' bene che l'utilizzo sia ottimizzato, in quanto ogni AND logico tra matrici costa cicli di processore. Per cui, ottimizzare l'uso dell'algoritmo significa: 1. Utilizzarlo solo quando ce n'e' effettivo bisogno. Quindi, se un oggetto non entra mai in collisione con altri, come ad esempio un pianeta di sfondo, e' inutile processarne l'immagine ed eseguire test sulla sua posizione, puo' -anzi, deve- essere ignorato. 2. Quando si testa una sovrapposizione, al primo "1" che risulti da un AND logico il test deve fermarsi. Infatti che utilita' ha sapere in quanti punti e' avvenuta la collisione?? A noi basta un punto solo (a meno che il vostro gioco non richieda diversamente) in modo da poter subito innescare l'evento e risparmiare quindi inutili giri di processore. 3. Non so se sia fattibile, non conosco ancora bene l'algebra delle matrici, ma potrebbe essere possibile evitare addirittura l'AND logico in base al determinante di ogni matrice. Sicuramente approfondiro' l'argomento, per ora l'algo rimane cosi'. 4. Ovviamente e' molto piu' conveniente se le matrici di ogni sprite vengono create all'inizio del gioco ed una volta per tutte, piuttosto che calcolare ogni volta i vari "0" e "1". Infatti se abbiamo gia' la nostra matrice possiamo ricavarci la sottomatrice semplicemente spostandoci di tanti pixel/unita' quanto la differenza tra le coordinate delle due immagini. Direi che con questo e' praticamente tutto. Se mi verranno in mente altre cose le aggiungero', fermo restando che potrebbero arrivare presto altri articoli sul Game Programming, magari partendo proprio dalle "origini".
byez all
|