Pixelgenaue Kollision (Tutorial)

Einleitung

Das ist eines meiner alten Tutorials, kopiert von hier.

In 2D-Spielen muss man immer wieder überprüfen, ob ein Objekt bzw. Bild mit einem anderen Kollidiert. Man kann dazu einfach überprüfen, ob die Rechtecke der Objekte sich überlappen. Meist ist dies jedoch viel zu ungenau.

Dieses Tutorial erklärt in Pseudo-Code (an Basica angelehnt ;) ) wie man herausfindet ob zwei Bilder WIRKLICH miteinander kollidieren.

Wir brauchen erstmal folgendes:
- zwei Bilder (oder eines, das zweimal auf den Screen gezaubert wird) welche eine Hintergrundfarbe haben, die man als transparent markieren kann. Meist ist das Pink (RGB 255,0,255), da diese Farbe nur sehr selten als "Farbe" benutzt wird.
- Die X und Y Positionen sowie die Grössen der Bilder. (X,Y, Width, Height)
- Eine Funktion mit der man den Farbwert eines Pixels auf dem Bild herausfinden kann. (Windows API: GetPixel(Bild_DC, PosX,PosY))

In diesem Bild sehen wir, wie man sich das Ganze vorzustellen hat. Die grauen Linien zeigen die Relation der angegebenen Werte zum Spielfeld. Natürlich gilt dies auch für das UFO, ich habe hier nur die Werte des Baumes angeschrieben.

Der kleine, rot angemalte Ausschnitt zwischen UFO und Baum ist das, was wir rausfinden wollen: Ob das UFO "wirklich" mit dem Baum kollidiert.

Ich werde die Werte hier in objektorientierter schreibweise angeben: Baum.X ist also zum Beispiel die X Position des Baum-Bildes.

Ueberlappungstest

Erstmal prüfen wir, ob die Bilder sich überhaupt schneiden - ansonsten wird viel Performance für nichts verbraucht.

IF(((UFO.X >= Baum.X AND UFO.X <= Baum.X+Baum.Width) OR
(Baum.X >= UFO.X AND Baum.X <= UFO.X+UFO.Width)) AND
((UFO.Y >= Baum.Y AND UFO.Y <= Baum.Y+Baum.Height) OR
(Baum.Y >= UFO.Y AND Baum.Y <= UFO.Y+UFO.Height))) THEN...

Das sieht komplizierter aus, als es ist. Man könnte die ganze Abfrage auch mit mehreren IF's realisieren aber so ist es schneller. Man muss einfach genauestens auf die Klammern achten, deshalb sind sie hier rot.

Es wird hier einfach geprüft, ob irgend ein Bereich eines Bildes sich im Bereich des anderen Bildes befindet. Wenn ihr euch den Code ein paar mal anguckt werdet ihr ihn verstehen...

Offsets berechnen

Gut, wir haben also geprüft, ob sich die Bilder überlappen. Wir gehen jetzt davon aus, dass das so ist und fahren innerhalb dieses IF-Blockes fort. Wir müssen nun jedes Pixel des überlappten Bereiches prüfen. Dazu müssen wir erst rausfinden, wo die Ueberlappung im jeweiligen Bild beginnt, und wo sie aufhört.

Dazu werde ich einige neue Werte einführen und auf 0 setzen. Die Breite und Höhe wird NICHT auf 0 sondern auf die Höhe bzw. Breite des KLEINEREN Bildes gesetzt.. (Erinnert euch, wir sind nun INNERHALB des obigen IF-Blockes)

OffsetXUFO=0
OffsetXBaum=0
OffsetYUFO=0
OffsetYBaum=0

OffsetWidth=UFO.Width
OffsetHeight=UFO.Height

IF(OffsetWidth > Baum.Width) THEN OffsetWidth = Baum.Width
IF(OffsetHeight > Baum.Height) THEN OffsetHeight = Baum.Height

Diese Offset-Werte sind die Startpositionen der Ueberlappung auf den Bildern. (Nicht auf dem Spielfeld, sondern auf den Bildern selber. Dies seht ihr in Bild 2 hier:

OffsetWidth und OffsetHeight müssen nur einmal angegeben werden, da die Grösse der Ueberlappung bei beiden Bildern gleich gross ist.

OffsetX und OffsetY brauchts eigentlich auch nur einmal, da diese bei einem Bild immer gleich 0 sind. Da wir aber wissen müssen, von WELCHEM Bild die Werte sind, müssen wir sie trotzdem doppelt haben. Im Beispielbild hier ist OffsetX vom Baum gleich 0 und OffsetY vom UFO gleich 0.

Es gibt nun zwei Fälle, die jeweils anders überprüft werden müssen. Im obigen Bild sind beide Fälle eingezeichnet: Der erste Fall wird durch die X-Positionen gekennzeichnet: Das eine Bild hat eine Position ausserhalb des anderen Bildes. Der zweite Fall wird durch die Y-Positionen gekennzeichnet: Die Y-Position UND die Y-Position plus Höhe liegt komplett im anderen Bild.

Das folgende Bild veranschaulicht die zwei Fälle noch einmal:

Fall 2 wurde sozusagen schon berechnet. Das ist der jeweilige Wert der Breite und Höhe des kleineren Bildes. Fall 1 wird nun berechnet, wenn das Bild teilweise ausserhalb des anderen Bildes liegt.

Wir berechnen nun also die jeweiligen Offset-Werte (immer noch im "grossen" IF-Block):

IF(UFO.X < Baum.X) THEN   UFO.OffsetX = Baum.X - UFO.X   IF(Baum.X+Baum.Width > UFO.X+UFO.Width) THEN
    OffsetWidth=UFO.X+UFO.Width-Baum.X // FALL 1
  ENDIF
ELSE
  Baum.OffsetX = UFO.X - Baum.X
  IF(UFO.X + UFO.Width > Baum.X + Baum.Width) THEN
    OffsetWidth=Baum.X+Baum.Width-UFO.X // FALL 1
  ENDIF
ENDIF

Hier wird geprüft, welcher X-Offset berechnet werden soll, der von Bild 1 oder der von Bild 2. Der jeweilig andere X-Offset-Wert ist 0. Die Breite wird dann auch gleich berechnet, wie gesagt aber nur wenn Fall 1 eintritt. Ansonsten ist die Breite ja schon definiert worden. Das selbe muss nun noch mal mit dem Y-Offset gemacht werden:

IF(UFO.Y < Baum.Y) THEN   UFO.OffsetY = Baum.Y - UFO.Y   IF(Baum.Y+Baum.Height > UFO.Y+UFO.Height) THEN
    OffsetHeight=UFO.Y+UFO.Height-Baum.Y // FALL 1
  ENDIF
ELSE
  Baum.OffsetY = UFO.Y - Baum.Y
  IF(UFO.Y + UFO.Height > Baum.Y + Baum.Height) THEN
    OffsetHeight=Baum.Y+Baum.Height-UFO.Y // FALL 1
  ENDIF
ENDIF

Kollision prüfen

Zu guter letzt müssen wir nur noch durch unseren Bereich durchgehen und prüfen, ob ein Pixel auf einer Position in BEIDEN Bildern nicht gleich der transparenten Farbe ist:

FOR(XPos = 0 TO OffsetWidth)
  FOR(YPos = 0 TO OffsetHeight)
    Pixel1 = GetPixel(UFO.Bild, UFO.X + UFO.OffsetX + XPos, UFO.Y + UFO.OffsetY + YPos)
    Pixel2 = GetPixel(Baum.Bild, Baum.X + Baum.OffsetX + XPos, Baum.Y + Baum.OffsetY + YPos)
    IF(Pixel1 NOT TRANSPARENTE_FARBE AND Pixel2 NOT TRANSPARENTE_FARBE) THEN
      // KOLLISION: Wir sollten nun die Schleifen verlassen, um Performance zu sparen.
    ENDIF
  NEXT YPos
NEXT XPos

Ich hoffe mal, das hilft...