Pixelgenaue Kollisionserkennung

Jedes Spiel, welches auf bewegte Elemente setzt, die mit einander in Kontakt treten, benötigt ein Algorithmus um Kollisionen zwischen den Elementen zu erkennen. Für diesen Zweck gibt es dutzende von Algorithmen und sie alle haben ihre Vor- und Nachteile.
Ich möchte hier eine Methode vorstellen, die Kollisionen pixelgenau erkennt.
Bevor wir aber damit anfangen, schauen wir uns zuerst die einfachste 2D-Kollisionserkennung an.

Ansatz 1 – Bounding Box

Bounding Box ist eine virtuelle Box (in 2D – ein Rechteck) die, das zu überprüfende Sprite umschließt.
Im einfachsten Fall ist die BB genau so groß wie das Sprite bzw. die Textur selbst.
Ein Bild sagt mehr als tausend Worte: Das schwarze Quadrat um das Bild ist die Bounding Box (ab hier nur BB).

Bounding Box um einen Sprite

Um eine Kollision zwischen zwei Sprites zu erkennen, schaut man nach, ob die beiden BB sich überschneiden. Alles was dazu benötigt wird, ist die Position und die Größe der beiden BB.
Dazu deklarieren wir eine Bounding Box Klasse, die beim Laden der Textur mit Daten gefüllt wird.

class BBox
{
public:
	BBox(void){}
	BBox(BBox& bb) : pos_x( bb.pos_x ),
						pos_y( bb.pos_y ),
						size_x( bb.size_x ),
						size_y( bb.size_y )
	{}

	BBox(int _x, int _y, 
		 int dx, int dy) : pos_x( _x ),
						pos_y( _y ),
						size_x( dx ),
						size_y( dy )
	{}

	int pos_x;
	int pos_y;
	
	int size_x;
	int size_y;
};

Das Überprüfen selbst beschränkt sich auf vier if – Anweisungen, für jede Rechteckseite eine. Schauen wir uns am Beispiel einer Abfrage an, wie das Ganze funktioniert.

Wir haben beispielsweise zwei BB mit folgenden Daten:

BBox BB1;
BB1.pos_x = 80;
BB1.pos_y = 60;
BB1.size_x = 128;
BB1.size_y = 128;

BBox BB2;
BB2.pos_x = 270;
BB2.pos_y = 40;
BB2.size_x = 64;
BB2.size_y = 64;

Was folgender Darstellung entspricht:
Sprites mit Bounding Box

Die Überprüfungsabfrage dazu lautet:

// BB2 liegt rechts von m_BB (siehe Beispiel oben)
if( (BB1.pos_x + BB1.size_x) <= BB2.pos_x)
	return false;	// keine Kollision

Diese einfache if-Abfrage verrät uns, dass das zweite Sprite auf der X-Achse hinter dem ersten Sprite liegt (ab roter Linie) und das heißt, es gibt keine Kollision.
Das war die Überprüfung einer Bounding Box-Seite, die Überprüfung der restlichen drei Seiten geht nach dem gleichen Prinzip.

// Überprüft ob zwei BB miteinander kollidieren
// gibt true zurück, wenn eine Kollision aufgetreten ist
bool Collision(const BBox& BB1, const BBox& BB2) 
{	
	// BB2 liegt rechts von m_BB (siehe Beispiel oben)
	if( (BB1.pos_x + BB1.size_x) <= BB2.pos_x)
		return false;
	
	// BB2 liegt unter den m_BB
	if( (BB1.pos_y + BB1.size_y) <= BB2.pos_y)
		return false;

	// BB2 liegt links von m_BB
	if( (BB2.pos_x + BB2.size_x) <= BB1.pos_x)
		return false;

	// BB2 liegt über den m_BB
	if( (BB2.pos_y + BB2.size_y) <= BB1.pos_y)
		return false;

	// wenn man hier angekommen ist, dann kollidieren die BBoxen
	return true;
}
2D Kollisionserkennung Beispiel 1
Bounding Box Kollision Beispiel 1
Bounding Box Kollision Beispiel 1

Die von uns implementierte Funktion ist sehr schnell, doch auch sehr unpräzise.
Stellen wir uns eine Spielsituation vor, die auf folgender Abbildung dargestellt ist.

Ungenaue Kollisionserkennung

Laut unserer Funktion gibt es eine Kollision und das Raumschiff explodiert, obwohl der Spieler dem Asteroiden möglicherweise noch ausweichen könnte. Bei so einer Kollisionserkennung ist der Frust beim Spielen garantiert.

Man könnte das Problem verbessern, in dem man die BB etwas kleiner macht oder statt den Rechtecken Kreise verwenden, wenn die Sprites eher rundliche Form haben.
Wie man es aber auch dreht, so richtig optimal ist die Methode nicht.

Schauen wir uns an, wie wir diese Situation verbessern können.

Ansatz 2 – Pixelgenaue Kollisionserkennung

Die pixelgenaue Methode ist die genauste von allen und es gibt dazu unterschiedliche Algorithmen. Ich werde hier nur eine Methode vorstellen, die Arrays nutzt.

Ein digitales Bild oder genauer eine Textur ist ein Feld aus Farbpunkten (Pixeln). Wenn sich zwei Sprites übereinander liegen, können wir auf deren Farbwerte zugreifen und schauen, ob die farbigen Pixel sich irgendwo überlagern. Wenn dies der Fall ist, dann werten wir das als eine Kollision.

Diese direkte Methode würde funktionieren, wäre aber sehr langsam, weil der Zugriff auf die Farbwerte sehr zeitintensiv ist und währenddessen kein Zeichenvorgang möglich ist. Dies ist bei einem Spiel natürlich nicht hinnehmbar.

Man kann dieses Problem umgehen in dem man beim Erstellen von Sprites die Farbwerte ausliest und in einen extra dafür vorgesehen Array speichert.
Da für die Kollisionserkennung nicht entscheidend ist, welche Farbe die Pixel haben, brauchen wir in das Array nicht die ursprüngliche Farbe zu speichern, sondern nur die Information darüber, ob der Pixel farbig ist. Somit wird das Array um einiges kleiner, was sich positiv auf den Arbeitsspeicherverbrauch auswirkt.

Gehen wir alle Schritte durch.
Zuerst erstellen wir ein Array in der Texturgröße. Dann gehen wir alle Pixel der Textur durch und schauen dabei nach, ob das aktuelle Pixel die Farbe hat, die nicht Transparent bzw. nicht als ColorKey definiert ist. Wenn dies der Fall ist, wird an der gleichen Position in dem Array true eingetragen, ansonsten false. Es wird weiter gemacht, bis alle Pixel durchgelaufen sind. Am Ende bekommt man ein Feld, das nur aus false oder true besteht.
Wenn man jetzt das Feld ausgeben würde, wobei false durch weiß und true durch schwarz repräsentiert wären, hätte man folgendes Bild bekommen.

Original und die monochrome Darstellung
Original und die monochrome Darstellung

Für diese true- und false-Informationen benötigen wir ein Feld. Die Frage nach dem Datentyp des Feldes erklärt sich von selbst. Da wir nur zwischen 2 Zuständen zu unterscheiden brauchen, benötigen wir 1-Bit Datentyp, der in C++ mit bool repräsentiert wird (bool belegt leider 8bit). Wir erweitern unsere Bounding Box Klasse um einen Zeiger auf ein Bit-Array. Zeiger deswegen, weil die Größe der Sprites und somit der Felder unterschiedlich sein wird, also muss das Feld zur Laufzeit dynamisch erzeugt werden.

class BBox
{
public:
	BBox(void): pos_x( 0 ),
				pos_y( 0 ),
				size_x( 0 ),
				size_y( 0 ),
				bitField(0)
	{}

	BBox(BBox& bb) : pos_x( bb.pos_x ),
						pos_y( bb.pos_y ),
						size_x( bb.size_x ),
						size_y( bb.size_y ),
						bitField(0)
	{}

	BBox(int _x, int _y, 
		 int dx, int dy) : 
											pos_x( _x ),
											pos_y( _y ),
											size_x( dx ),
											size_y( dy ),
											bitField(0)
	{}

	~BBox(void)
	{
		if(bitField != 0)
			delete[] bitField;
	}

	int pos_x;
	int pos_y;
	
	int size_x;
	int size_y;

	bool *bitField;
};

Die BBox Klasse ist bereits fertig. Beim Laden der Textur für das Sprite müssen die Attribute der Klasse und damit mit auch das bitField mit Daten gefüllt werden. Wie das funktionierst, zeige ich hier an einem Beispiel mit DirectX 9 Texturen.

// lpD3DDevice ist ein Zeiger auf ein gültiges Direct3D Device (LPDIRECT3DDEVICE9)
// man schaue sich am besten den Quelltext der Beispielanwendung 2 an.

// Zeiger auf die Textur
LPDIRECT3DTEXTURE9 lpTexture;

// Höhe und Breite der Textur
unsigned int Width = 0;
unsigned int Height = 0;

// Bounding Box anlegen
BBox BB;

// Inforationen über die Textur holen
D3DXIMAGE_INFO ImgInfo;
D3DXGetImageInfoFromFile(lpFileName,&ImgInfo);

// Textur anlegen
D3DXCreateTextureFromFileEx(m_lpD3DDevice,
                            lpFileName,
                            ImgInfo.Width,
                            ImgInfo.Height,
                            1,0,
                            D3DFMT_UNKNOWN,
                            D3DPOOL_MANAGED,
                            D3DX_FILTER_NONE,
                            D3DX_FILTER_NONE,
                            0x00000000,0,0,
                            &m_lpTexture);

// Breite und Höhe speichern
m_Width  = ImgInfo.Width;
m_Height = ImgInfo.Height;

// BB mit werten belegen
m_BB.pos_x = 0;
m_BB.pos_y = 0;
m_BB.size_x = m_Width;
m_BB.size_y = m_Height;


// Textur sperren
D3DLOCKED_RECT LockedRect;
m_lpTexture->LockRect(0, &LockedRect, NULL, D3DLOCK_READONLY);
	
// Zeiger auf die Pixeln holen
DWORD* pPixels = (DWORD*)LockedRect.pBits;

// Bei 32Bit Modus /=4, bei 16Bit Modus /=2
LockedRect.Pitch /= 4;
	
// Feld von der Größe der Textur erzeugen
m_BB.bitField = new bool[m_Width * m_Height];

// Das Feld füllen
for(unsigned int i=0; i<m_Height; i++)
{		
	for(unsigned int j=0; j<m_Width; j++)
	{			
		// false wenn der Pixel transparent ist
		bool transparens = (((pPixels[i*LockedRect.Pitch + j]>>24) & 0xff) > 0);

		m_BB.bitField[i * m_Width + j] = transparens;	
	}				
}

// Textur freigeben
m_lpTexture->UnlockRect(0);

Jetzt, wo die einzelnen Bitfelder mit Pixeldaten gefüllt sind, können wir mit dem eigentlichen pixelgenauen Kollisionstest beginnen. Wir schauen, ob sich die „schwarzen Pixel“ von beiden Sprites überlagern. Wenn „ja“, dann gibt es eine Kollision.

Zuerst bestimmen wir die Koordinaten der Schnittfläche im Koordinatensystem der ersten Bounding Box.
Bounding Box Schnittfläche

Die Berechnung dazu ist vielleicht auf den ersten Blick etwas verwirrend, lässt sich aber auf einem Blatt Papier schnell nachvollziehen.

// Abmessungen des überlappenden Bereichs berechnen
int start_y = ((BB2.pos_y - BB1.pos_y) > 0) ? (BB2.pos_y - BB1.pos_y) : 0;
int end_y = ((BB2.pos_y + BB2.size_y - BB1.pos_y ) < BB1.size_y) ? (BB2.pos_y - BB1.pos_y + BB2.size_y) : BB1.size_y;

int start_x = ((BB2.pos_x - BB1.pos_x) > 0) ? (BB2.pos_x - BB1.pos_x) : 0;
int end_x = ((BB2.pos_x + BB2.size_x - BB1.pos_x ) < BB1.size_x) ? (BB2.pos_x - BB1.pos_x + BB2.size_x) : BB1.size_x;

Man muss beachten, dass bei der Berechnung implizit angenommen wird, dass die beiden Boxen sich schneiden. Das erreichen wir dadurch, in dem wir vor dem pixelgenauen Test den einfachen Bounding Box-Test durchführen.

Als nächstes werden alle Pixel der Schnittfläche durchlaufen.

// Alle Pixel des überlappenden Beireichs durchlaufen
for(int i = start_x; i < end_x; i++)
{
	for(int j = start_y; j < end_y; j++)
	{		
		// hier kommt noch was rein
	}	
}

Wir schauen für jeden Pixel der Schnittfläche nach, welcher Farbwert an der entsprechenden Position in den Arrays der beiden Sprites liegt. Wenn die beiden Werte mit true belegt sind, dann gibt es eine Überscheidung der beiden Farbbereiche und wir werten dies als eine Kollision.

// Alle Pixel des überlappenden Beireichs durchlaufen
for(int i = start_x; i < end_x; i++)
{
	for(int j = start_y; j < end_y; j++)
	{		
		// true = pixel nicht transparent 
		bool nicht_transparent_b1 = BB1.bitField[j*BB1.size_x + i];
		bool nicht_transparent_b2 = BB2.bitField[(BB1.pos_y + j - BB2.pos_y)*BB2.size_x + (BB1.pos_x + i - BB2.pos_x)];
						
		// wenn beide Pixel nicht transparent sind, gibt es eine Kollision
		if(nicht_transparent_b1 && nicht_transparent_b2)
			return true;
	}	
}

Führt man alle Codefragmente zusammen, so bekommt man eine Funktion für den pixelgenauen Kollisionstest.

// Uberpruft ob zwei BB miteinander kollidieren
// gibt true zuruck, wenn eine Kollision aufgetreten ist
bool Collision(const BBox& BB1, const BBox& BB2) 
{	
	// Bounding Box Kollisionstest
	
	// BB2 liegt rechts von m_BB (siehe Beispiel oben)
	if( (BB1.pos_x + BB1.size_x) <= BB2.pos_x)
		return false;
	
	// BB2 liegt unter den m_BB
	if( (BB1.pos_y + BB1.size_y) <= BB2.pos_y)
		return false;

	// BB2 liegt links von m_BB
	if( (BB2.pos_x + BB2.size_x) <= BB1.pos_x)
		return false;

	// BB2 liegt über den m_BB
	if( (BB2.pos_y + BB2.size_y) <= BB1.pos_y)
		return false;

	// pixelgenauer Kollisionstest

	// Abmessungen des überlappenden Bereichs berechnen
	int start_y = ((BB2.pos_y - BB1.pos_y) > 0) ? (BB2.pos_y - BB1.pos_y) : 0;
	int end_y = ((BB2.pos_y + BB2.size_y - BB1.pos_y ) < BB1.size_y) ? (BB2.pos_y - BB1.pos_y + BB2.size_y) : BB1.size_y;
	int start_x = ((BB2.pos_x - BB1.pos_x) > 0) ? (BB2.pos_x - BB1.pos_x) : 0;
	int end_x = ((BB2.pos_x + BB2.size_x - BB1.pos_x ) < BB1.size_x) ? (BB2.pos_x - BB1.pos_x + BB2.size_x) : BB1.size_x;

	// Alle Pixel des überlappenden Beireichs durchlaufen
	for(int i = start_x; i < end_x; i++)
	{
		for(int j = start_y; j < end_y; j++)
		{		
			// true = pixel nicht transparent 
			bool nicht_transparent_b1 = BB1.bitField[j*BB1.size_x + i];
			bool nicht_transparent_b2 = BB2.bitField[(BB1.pos_y + j - BB2.pos_y)*BB2.size_x + (BB1.pos_x + i - BB2.pos_x)];
		
			// wenn beide Pixel nicht transparent sind, gibt es eine Kollision
			if(nicht_transparent_b1 && nicht_transparent_b2)
				return true;
		}	
	}

	// keine Kollision
	return false;
}

Die Funktionsweise der Methode kann in dem zweiten Beispiel betrachten.
2D Kollisionserkennung Beispiel 2

Pixelgenaue Kollisionserkennung im Beispiel 2
Pixelgenaue Kollisionserkennung im Beispiel 2

Mögliche Optimierung

Um die Funktion noch etwas schneller zu machen, sollte man die Bounding Box und somit auch das Farbfeld nicht in der Größe der Textur, sondern in der Größe der „schwarzen Pixels“ erstellen.

Optimierung

Viel Spaß beim Programmieren! =)

Referenz:

Titel: Jetzt lerne ich Spieleprogrammierung mit DirectX
Autor: Christian Rousselle
ISBN: 978-3827269553
Beschreibung: Siehe Bücherecke

Hinweis: Die beiden Grafiken für den Raumgleiter und den Asteroiden stammen von der CD zu diesem Buch.

7 Gedanken zu „Pixelgenaue Kollisionserkennung“

  1. kann man hier im letzten beispiel die sprite rotation beim kollisions test berücksichtigen, box sowie sprite? oder wirds da probleme geben bezüglich des pixelgenauen test?

    finde keine brauchbare lösung…

  2. Ohne Weiteres ist es mit der oberen Methode nicht möglich. Aber man könnte sie abändern. Man muss die einzelnen Pixel, die man prüfen will unter dem Sprire-Rotationswinkel rotieren lassen und dann testen.
    Der kritische Punkt an dieser Stelle wäre die Performance. Wie schnell das Ganze laufen würde, kann ich dir nicht sagen, das müsste man ausprobieren.
    Wenn du nicht gerade jeden Winkel brauchst, dann könntest du auch für jede benötigte Richtung ein eigenes Sprite erstellen und dann nacheinander anzeigen, also praktisch eine Animationsrotation. Dann könnte man für jeden einzelnen Schritt die obere Methode nehmen.

  3. n1 Tutorial, funktioniert immerhin zuverlässig, habe das oben erwähnte Buch in der ersten Ausgabe auch, und dort funktioniert die pixelgenau Kollisionserkennung nur mit bestimmten Sprites, schade nur das keine animationen und rotationen eingebaut wurden.

    Habe nach langer Zeit nochmal mit C++ und DX angefangen, und bin über dein Tut gestolpert, thx nochma.

Schreibe einen Kommentar