Qualunque sia il gioco che intendete sviluppare, una sua parte fondamentale è la collision-detection, ovvero riconoscere quando due oggetti si stanno sovrapponendo. È scontato dirlo, ma ciò è indispensabile ad esempio per gestire un evento del personaggio che incontra un ostacolo, o di un proiettile che colpisce un avversario e così via. Rilevare una collisione non è un'operazione semplicissima, se le figure in gioco fossero semplicemente rettangoli allora non avremmo grosse difficoltà, è facile lavorare con essi e il framework .Net stesso offre la funzione Rectangle.Intersects, tuttavia nella quasi totalità dei casi si ha a che fare con oggetti ben più complessi (nel nostro caso stelline) e per di più dalla loro forma originale essi vengono in genere trasformati, ovvero ruotati, ridimensionati e spostati come abbiamo visto nel precedente articolo, su cui questo si basa.
Illustriamo rapidamente la soluzione che abbiamo qui adottato:

• creare per ogni texture una maschera di bit per pixel, il cui corrispondente valore sarà impostato su 0 se esso è trasparente o 1 altrimenti;
• ogni volta che si genere un frame bisogna effettuare un controllo se c'è stata collisione tra tutti gli elementi in campo;
• per effettuare questi controlli bisogna calcolare i rettangoli che contengono completamente le due figure in gioco così da avere una prima indicazione per sapere se le figure collidono o meno;
• calcolare l'intersezione tra questi due rettangoli;
• se l'intersezione non è nulla allora dobbiamo passare a controllare pixel per pixel questa intersezione per verificare se vi sono due pixel non trasparenti (consultando la maschera di bit inizialmente creata) che si sovrappongono;

Se l'ultimo controllo risulta vero allora possiamo dire che i due oggetti (rappresentati dalla classe Character) stanno collidendo.

COME PREPARARE ED ESEGUIRE I CONTROLLI
Cosa serve fare preliminarmente e come effettuare il controllo.

È la classe Animation quella che contiene informazioni sullo stato corrente dell'animazione e sulla texture dei frame da disegnare, per cui è qui che dobbiamo creare la nostra maschera di bit per la trasparenza. Ovviamente potremmo usare anche direttamente i colori della bitmap originale e controllare se il canale alpha è nullo, ma l'implementazione che si serve di un BitArray è estremamente più rapida, e l'efficienza è fondamentale in questo tipo di controlli dato si tratterà di un'operazione da ripetere migliaia e migliaia di volte per frame disegnato. Si pensi che un Color è un dato ARGB e come minimo occupa 32 bit, un bit invece occupa solo un bit, ovviamente.

private void BuildBitmask()
{
    // Creiamo un array di Color per memorizzare temporaneamente
    // l'intera bitmap della texture
    Color[] colorMap = new Color[this.Frames.Width * this.Frames.Height];
    // Copiamo tutte le informazioni della texture nell'array
    this.Frames.GetData<Color>(colorMap);
    // Creiamo il BitArray, con le stesse dimensioni dell'immagine
    BitMask = new System.Collections.BitArray(this.Frames.Width * this.Frames.Height);
    
    // Iteriamo tutti gli elementi dell'array di Color
    for (int pos = 0; pos < this.Frames.Width * this.Frames.Height; pos++)
        // Se il canale Alpha è a 0 (il pixel è trasparente)
        // impostiamo il valore della bitmask su false
        BitMask[pos] = (colorMap[pos].A != 0);

}

Questa funzione viene chiamata dal costruttore della classe Animation. Per prima cosa copiamo tutti i dati contenuti della Texture2D chiamando il metodo Texture2D.GetData e passandogli come argomento un array (unidimensionale) di Color, nel quale ci troveremo ad avere il valore del colore di tutti i pixel riga per riga. Dunque creiamo un BitArray delle stesse dimensioni (in quanto a numero di elementi, in memoria occupa 32 volte meno) e quindi impostiamo i suoi bit a seconda che il corrisponde colore di colorMap abbia il canale alpha (proprietà Color.A) non nullo o meno. Ci ritroveremo quindi ad avere una mappa di bit con 0 per ogni pixel trasparente e 1 per ogni pixel almeno parzialmente visibile.

Abbiamo poi detto che ogni volta che viene disegnato un frame (nel metodo Game.Draw nel nostro caso) bisogna effettuare un controllo tra tutti i componenti del gioco di tipo Charcter per verificare se stanno collidendo tra loro, questa è un'operazione O(n^2/2), infatti non è necessario confrontare tutti gli elementi con tutti gli elementi, poiché la relazione "collide con" è simmetrica; dunque il primo elemento andrà confrontato con tutti gli altri, il secondo con tutti meno il primo, il terzo con tutti meno i primi due e così via fino all'ultimo che non ha bisogno di essere confrontato con nessuno. 

for (int c1 = 0; c1 < this.Components.Count - 1; c1++)
    for (int c2 = c1 + 1; c2 < this.Components.Count; c2++)
        // Ci assicuriamo che si tratti di un Character
        if (this.Components[c1] is Character && this.Components[c2] is Character)
        {
            // Variabile in cui verrà salvato il rettangolo di
            // intersezione tra i due rettangoli che includono
            // le figure che stiamo confrontando
            Rectangle intersection;
            // Effettuiamo un controllo per vedere se c'è stata collisione
            if (Character.CheckCollision((Character)this.Components[c1], 
                (Character)this.Components[c2], out intersection))
            {
                // C'è collisione, disegniamo il rettangolo di intersezione
                // in rosso
                spriteBatch.Draw(redPixel, (Rectangle)intersection, Color.White);
            }
            else
            {
                // Non c'è collisione: le due figure non hanno pixel
                // non trasparenti sovrapposti.

                // I rettangoli che contengono le due figure potrebbero
                // intersecarsi comunque, li disegniamo in verde
                if (intersection.Width > 0)
                    spriteBatch.Draw(greenPixel, (Rectangle)intersection, Color.White);
            }
        }

Sostanzialmente abbiamo due cicli, quello più esterno itera su tutti gli elementi fino al penultimo, quello più interno su tutti a partire dal successivo di quello più esterno. Ogni volta si effettua un controllo che il componente sia un Character e non altro, altrimenti non si potrebbe procedere. Quindi viene chiamato il metodo statico Character.CheckCollision a cui si passano i due Character che vogliamo controllare e come terzo parametro dove vogliamo sia restituito il rettangolo ottenuto dall'intersezione dei due rettangoli che contengono le figure. Se c'è collisione disegniamo questo rettangolo in rosso, altrimenti in verde, ammesso che almeno il rettangolo di intersezione non sia nullo.
Una breve nota per redPixel e greenPixel, argomenti passati a Draw: in sostanza si tratta di texture create all'inizio del gioco (in Game.LoadContent) di dimensione 1 pixel per 1 pixel del colore specificato che viene poi ridimensionato di volta in volta a seconda della necessità per disegnare i rettangoli che ci servono per chiarire i concetti di questo tutorial.
Arriviamo ora al vero cuore del tutorial: come rilevare la collisione.

CALCOLO DELLE INTERSEZIONE DEI RETTANGOLI
Una prima verifica sui rettangoli che contengono completamente le figure.

public static bool CheckCollision(Character obj1, Character obj2, out Rectangle BoundingRectangleIntersection);

Come si può vedere della definizione, CheckCollision, è una funzione che restituisce true se c'è stata collisione tra obj1 e obj2, false altrimenti. BoundingRectangleIntersection è un parametro in uscita che serve per far avere al chiamante il rettangolo in cui si intersecano i bounding-rectangle (rettangoli che contengono le figure) dei due Character.
Ed è proprio su di essi che si effettua la prima parte del controllo:

BoundingRectangleIntersection = Rectangle.Empty;

// Prendiamo il rettangolo di intersezione tra i due rettangoli
// che contengono le figure di cui si sta cercando l'intersezione
Rectangle? getIntersectionResult = Character.GetBoundingRectanglesIntersection(obj1, obj2);

// Se neppure i rettangoli delle figure si intersecano sicuramente
// non c'è collisione
if (getIntersectionResult == null)
{
    return false;
}

// C'è intersezione tra i rettangoli che contengono le figure
Rectangle intersection = (Rectangle)getIntersectionResult;
BoundingRectangleIntersection = intersection;

In sostanza se l'intersezione tra i rettangoli è vuota restituiamo false in quanto sicuramente non c'è collisione, altrimenti copiamo il rettangolo risultante in una variabile non Nullable per comodità, impostiamo inoltre la variabile di ritorno BoundingRectangleIntersection sul risultato. Vediamo ora il metodo che calcola l'intersezione tra questi due rettangoli, Character.GetBoundingRectanglesIntersection:

public static Rectangle? GetBoundingRectanglesIntersection(Character obj1, Character obj2) {
    return GetRectanglesIntersection(obj1.GetBoundingRectangle(), obj2.GetBoundingRectangle());
}

Esso restituisce al chiamante il risultato della funzione GetRectanglesIntersection che non fa altro che trovare l'intersezione tra due rettangoli che si intersecano:

public static Rectangle? GetRectanglesIntersection(Rectangle rect1, Rectangle rect2)
{
    if (rect1.Intersects(rect2)) {
        Vector2 ul = Vector2.Max(new Vector2(rect1.Left,rect1.Top), new Vector2(rect2.Left, rect2.Top));
        Vector2 dr = Vector2.Min(new Vector2(rect1.Right, rect1.Bottom), new Vector2(rect2.Right, rect2.Bottom));
        return new Rectangle((int) Math.Round(ul.X), (int) Math.Round(ul.Y), 
            (int) Math.Round(dr.X - ul.X), (int) Math.Round(dr.Y - ul.Y));
    } 
    else { return null; }
}

GetRectanglesIntersection restituisce il rettangolo di intersezione calcolando il suo angolo in alto a sinistra e in basso a destra: per il primo prende le coordinate massime (ovvero più in basso a destra) tra gli angoli in alto a sinistra dei due rettangoli, mentre per il secondo quelle minime (ovvero più in alto a sinistra) degli angoli in basso a destra.
Ma come vengono calcolati i bounding-rectangle? Se ne occupa la funzione GetBoundingRectangle la quale parte dal rettangolo originale di partenza e gli applica tutte le trasformazioni (rotazione, ridimensionamento e spostamento). Tuttavia in questo modo potremmo ottenere un rettangolo ruotato, ovvero con i lati non paralleli agli assi e quindi non gestibile tramite la classe Rectangle, quindi calcoliamo a sua volta il rettangolo a lati paralleli allo schermo in cui esso è contenuto:

public Rectangle GetBoundingRectangle() {
    // Rettangolo prima delle trasformazioni
    Rectangle dest = new Rectangle(0, 0, this.CurrentAnimation.FrameWidth, this.CurrentAnimation.Frames.Height);
    
    // Prendiamo la matrice di trasformazione
    Matrix transformation = this.currentTransformation;

    // Creiamo i vettori dei punti dei 4 angoli del rettangolo
    Vector2 ul = new Vector2(dest.Left, dest.Top), 
        ur = new Vector2(dest.Right, dest.Top),
        dl = new Vector2(dest.Left, dest.Bottom), 
        dr = new Vector2(dest.Right, dest.Bottom);

    // Applichiamo a tutti gli angoli la trasformazione
    ul = Vector2.Transform(ul, transformation);
    ur = Vector2.Transform(ur, transformation);
    dl = Vector2.Transform(dl, transformation);
    dr = Vector2.Transform(dr, transformation);

    // Prendiamo il rettangolo spostato, scalato e ruotato ottenuto 
    // e ne calcoliamo il rettangolo che a sua volta lo contiene.
    // Questo ci serve perché dobbiamo lavorare con un rettangolo
    // con i lati paralleli agli assi (ovvero allo schermo).

    // Calcoliamo l'angolo in alto a destra e in basso a sinistra
    // prendendo le coordinate minime e massime dei punti traslati
    Vector2 ulb = Vector2.Min(Vector2.Min(ul, ur), Vector2.Min(dl, dr));
    Vector2 drb = Vector2.Max(Vector2.Max(ul, ur), Vector2.Max(dl, dr));

    // Creiamo e restituiamo il rettangolo ottenuto
    return new Rectangle((int) Math.Round(ulb.X), (int) Math.Round(ulb.Y), 
        (int) Math.Round(drb.X - ulb.X), (int) Math.Round(drb.Y - ulb.Y));
}

Dato un rettangolo grande come la figura e situato nell'origine, applichiamo a tutti i suoi angoli la matrice di trasformazione corrente (vedremo tra poco quando e come ottenuta), ottenendo quindi 4 punti che rappresentano un rettangolo scalato, spostato e ruotato. Come già detto, lavorare con un rettangolo ruotato è però difficoltoso, perciò includiamo questo rettangolo ruotato in uno più grande definito tramite il suoi angoli in alto a sinistra e in basso a destra: il primo ottenuto dalle coordinate minime tra tutti i punti coinvolti, e il secondo dalle coordinate massime.
La matrice di trasformazione è memorizzata in Character.currentTransformation, che viene aggiornata ogni volta che viene chiamato Update:

this.currentTransformation = 
    Matrix.CreateTranslation(new Vector3(-this.CurrentAnimation.RotationPoint, 0))
    * Matrix.CreateScale(this.CurrentAnimation.Scale)
    * Matrix.CreateRotationZ((float)this.CurrentAnimation.CurrentRotation)
    * Matrix.CreateTranslation(new Vector3(this.Position, 0));

Si tratta in sostanza per prima cosa di centrare la figura nel suo centro di rotazione tramite una traslazione, poi si effettua il ridimensionamento, quindi si ruotia e infine si sposta il tutto al punto in cui si deve trovare il Character. Il tutto si ottiene moltiplicando le singole matrici che rappresentano le singole trasformazioni.

IL CUORE DEL PROBLEMA
Cambio del sistema di riferimento e controllo pixel per pixel.

Abbiamo dunque visto come trovare le intersezioni tra i rettangoli che contengono le figure, torniamo ora a CheckCollision:

// Invertiamo la matrice di trasformazione
Matrix invertedTransform1 = Matrix.Invert(obj1.currentTransformation);
// Prendiamo il primo punto dell'intersezione dei rettangoli
// e lo calcoliamo nel sistema di riferimento del Character
// con cui stiamo lavorando
Vector2 rowPos1 = Vector2.Transform(new Vector2(intersection.X, intersection.Y), invertedTransform1);
// Calcoliamo i vettori unitari X e Y (ovvero verso destra e verso il basso)
// nel sistema di riferimento del Character
Vector2 xUnit1 = Vector2.TransformNormal(Vector2.UnitX, invertedTransform1);
Vector2 yUnit1 = Vector2.TransformNormal(Vector2.UnitY, invertedTransform1);
// Memorizziamo in variabili locali alcune informazioni sul Character
// in modo da avere le massime prestazioni durante le iterazioni sotto
int textureWidth1 = obj1.CurrentAnimation.Frames.Width,
    frameLeft1 = obj1.CurrentAnimation.CurrentRectangle.Left,
    frameTop1 = obj1.CurrentAnimation.CurrentRectangle.Top,
    frameWidth1 = obj1.Width,
    frameHeight1 = obj1.Height;

Abbiamo ottenuto un rettangolo dove si trova, se c'è, la collisione. Questo rettangolo ha però le coordinate riferite allo schermo, quindi se diciamo la posizione (3, 3) del rettangolo dovremo convertirla in quello della figura che stiamo analizzando, prima l'una e poi l'altra. Per fare questo dobbiamo prendere la matrice invertita e applicarla alle coordinate X e Y del rettangolo, ma questo non basta. Il secondo pixel che andremo ad analizzare sarà "a destra" del primo, ma "a destra" è un'indicazione valida nel sistema di riferimento dello schermo ma non delle figure che potrebbero essere ruotate, lo stesso vale per la coordinata Y e "andare in basso". Per questo dobbiamo applicare la matrice inversa anche al vettore "freccia destra" (Vector2.UnitX) e "freccia giù" (Vector2.UnitY); si noti l'utilizzo di TransformNormal invece di Transform per questi due vettori in quanto il risultato viene normalizzato.
A questo punto definiamo una serie di variabili per rendere più veloce l'esecuzione del controllo pixel per pixel, e ripetiamo tutto questo anche per il secondo oggetto con cui stiamo effettuando il confronto.

for (int row = 0; row < intersection.Height; row++)
{
    // Riportiamo la coordinata X all'inizio
    // della riga del rettangolo (sempre nei
    // sistemi di riferimento dei Character)
    Vector2 pos1 = rowPos1;
    Vector2 pos2 = rowPos2;

    for (int col = 0; col < intersection.Width; col++)
    {
        // Calcoliamo il punto corrente in cui ci troviamo
        // dal punto di vista dei due Character
        Point pt1 = new Point((int) Math.Round(pos1.X), (int) Math.Round(pos1.Y));
        Point pt2 = new Point((int) Math.Round(pos2.X), (int) Math.Round(pos2.Y));

        // Se il punto cade all'interno dell'area della figura
        // di entrambi i Character
        if (0 <= pt1.X && pt1.X < frameWidth1 &&
            0 <= pt1.Y && pt1.Y < frameHeight1 &&
            0 <= pt2.X && pt2.X < frameWidth2 &&
            0 <= pt2.Y && pt2.Y < frameHeight2)
        {
            // Controlliamo che l'n-esimo pixel non sia 
            // trasparente in entrambe le figure.
            // Per fare questo ci serviamo della maschera
            // di bit creata in precedenza (si veda 
            // Animation.BuildBitmask).
            // La maschera di bit è unidimensionale perciò
            // calcoliamo la posizione tramite la formula:
            // CoordinataX + LarghezzaDiUnaRiga * CoordinataY
            if (obj1.CurrentAnimation.BitMask[frameLeft1 + pt1.X + 
                (frameTop1 + pt1.Y) * textureWidth1] &&
                obj2.CurrentAnimation.BitMask[frameLeft2 + pt2.X + 
                (frameTop2 + pt2.Y) * textureWidth2])
                return true;

        }

        // Avanziamo verso destra (di una colonna) in entrambi i Character
        pos1 += xUnit1;
        pos2 += xUnit2;
    }

    // Avanziamo verso il basso (di una riga) in entrambi i Character
    rowPos1 += yUnit1;
    rowPos2 += yUnit2;
}

return false;

Prima di osservare il cuore del controllo, vediamo come ci si comporta per muoversi lungo il rettangolo d'intersezione e i pixel delle due texture coinvolte. Abbiamo due cicli, uno più esterno che si muove lungo le righe e uno più interno che si muove lungo le colonne del rettangolo di intersezione. Le variabili rowPos1 e rowPos2 tengono conto della posizione in cui ci troviamo nei sistemi di riferimento dei Character su cui stiamo lavorando quando ci troviamo all'inizio di una riga del rettangolo di intersezione. Al primo ciclo rappresenteranno la posizione del rettangolo (sempre nei rispettivi sistemi di riferimento), al secondo la posizione in giù di 1, la seconda di 2 e così via. In sostanza gestisce l'avanzamento sull'asse Y tramite le istruzioni:

rowPos1 += yUnit1;
rowPos2 += yUnit2;

Le variabili pos1 e pos2 invece tengono conto anche della posizione X, che viene incrementata man mano dal ciclo più interno tramite le seguenti istruzioni:

pos1 += xUnit1;
pos2 += xUnit2;

Ora che abbiamo analizzato il meccanismo con cui ci muoviamo lungo il rettangolo da analizzare non resta che vedere come viene implementato il confronto. Prima di tutto vengono create due variabili pt1 e pt2 che contengono le coordinate su cui effettuare il confronto all'interno delle texture. Usiamo dei Point piuttosto che dei Vector2 perché in questo caso ci servono delle coordinate in forma di numeri interi per poter cercare il pixel corrispondente sulla bitmap originale (si noti infatti l'uso di Math.Round per arrotondare opportunamente il numero).
Per via della rotazione potrebbe darsi che il punto che ci è uscito non rientri all'interno dell'area della texture e quindi controlliamo che le sue coordinate siano maggiori di zero e non eccedano la lunghezze/larghezza del singolo frame. Se così è ci resta l'ultima verifica da fare, ovvero controllare sulla maschera di bit se i pixel corrispondenti nelle due texture sono entrambi non trasparenti. Poiché il BitArray è unidimensionale per raggiungere un coordinata (X, Y) ci serviamo della formula: CoordinataY * LarghezzaTexture + CoordinataX. Quindi controlliamo: se entrambe le bitmask nei punti corrispondenti sono true, significa che entrambi i pixel non sono trasparenti, ciò significa che c'è sovrapposizione di due pixel e quindi collisione.