Collisioni pixel-perfect con canvas HTML5

Prendendo il codice di Space Trash come spunto vado ora ad analizzare come rilevare le collisioni tra due oggetti di qualsiasi forma.

Prepariamo un canvas d’appoggio che useremo successivamente.

var canvas = document.createElement('canvas');
var context = canvas.getContext('2d');

Prima di andare effettivamente a verificare al pixel se c’è una collisione è bene, per questioni di performance fare un controllo più blando; normalmente il controllo di collisione va fatto ad ogni frame e, vista la complessità, può far benissimo crollare il frame rate.

Quindi per prima cosa controlliamo se i bounding box si intersecano.

In base delle figure in gioco potrebbe convenire fare altri tipi di controlli preliminari, ad esempio guardare l’intersezione dei bounding circle degli oggetti; in generale però, una volta superato il controllo, conviene calcolare l’intersezione dei bounding box in quanto un rettangolo è la figura più semplice da gestire.

var collisionRect = rectIntersect(boundingBox1, boundingBox2)
if(collisionRect){
   /* ... */
}

Adesso passiamo al controllo vero e proprio.

Trasliamo il contesto grafico in modo che la zona dove si intersecano i bounding box sia sicuramente visibile e puliamola per non falsare il risultato. Poi disegniamo con colori diversi le zone di collisione di ogni oggetto, grazie al valore di globalCompositeOperation quelle in comune verranno evidenziate.

context.translate(-collisionRect.x, -collisionRect.y);
context.clearRect(collisionRect.x, collisionRect.y, collisionRect.w, collisionRect.h);
context.fillStyle = '#00FF00';
drawCollisionBounding1(context);
context.fillStyle = '#FF0000';
drawCollisionBounding2(context);

Ora preleviamo dal contesto l’array di pixel che ci interessa.
E’ importante prendere subito un puntatore al campo data,  metterlo all’interno di un ciclo farebbe crollare le prestazioni a causa delle enormi dimensioni.

var imageData = context.getImageData(0, 0, collisionRect.w, collisionRect.h);
var data = imageData.data;

Il campo data è un array monodimensionale che descrive ogni pixel con 4 celle adiacenti : R, G, B e Alpha. Una volta ottenuto non ci resta che scorrerlo per verificare la presenza di pixel con collisioni. La scelta dell’algoritmo è molto importante per le performance e dipende dalle figure in gioco.

La più banale è una scansione lineare:

var pixel_grain = 2
for(var i = 0; i < data.length; i += 4 * pixel_grain){
   if(data[i] == 255 && data[i+1] == 255)return true;
}

Da notare la variabile pixel_grain che stabilisce la precisione/velocità del controllo. A causa della complessità del procedimento è’ difficile che si riesca effettivamente ad avere una precisione al pixel , però si possono trovare buone approssimazioni.

Nel gioco ho usato una scansione a spirale con partenza dal centro.

var detected = false;
var x = Math.round(collisionRect.w/2);
var y = Math.round(collisionRect.h/2);
var step_grain = 5;
var step = step_grain; 			
var pixel_grain = 5;

while(!detected && step < Math.max(collisionRect.w, collisionRect.h)){
      //Up    
   if(x > 0)
      linearScan(x, Math.min(y, collisionRect.h), x, Math.max(0, y - step));
   y -= step;

   //Right
   if(y > 0)
      linearScan(Math.max(x, 0), y, Math.min(x + step, collisionRect.w), y);
   x += step;

   //Down
   step+=step_grain;
   if(x < collisionRect.w)
      linearScan(x, Math.max(0, y), x, Math.min(y + step, collisionRect.h));
   y += step;

   //Left
   if(y < collisionRect.h)
      linearScan(Math.min(x, collisionRect.w), y, Math.max(0, x - step));
   x -= step;

   step+=step_grain;
}
return detected;

Alla fine di tutto è importante riportare il contesto allo stato iniziale, per evitare che le trasformazioni si accumulino.

context.translate(collisionRect.x, collisionRect.y);

Sono possibili molte varianti ma la base è questa.
Ad esempio, nel caso in cui non ci siano rotazioni degli oggetti, si potrebbero precalcolare gli array image data di entrambi e poi confrontarli con le dovute traslazioni.