www.codeworx.org/game-dev/Pixelgenaue 2D-Kollisionsabfrage

Pixelgenaue 2D-Kollisionsabfrage mittels Bitmaske 1997 by Darkvale Hi all, hier bin ich mit einem Tutorial ber 2D-Kollisionsabfrage. Ok, alter Hut, denkt man sich, man mache die "Bounding Box"-Methode, kein Problem. Kurz zusammengefaát: "Bounding Box"-Kollision ist die einfachste Kollisions- methode, bei denen Rechtecke (die sog. "Bounding Boxes") die Umrisse von Objekten bilden. Wenn sich diese Rechtecke berlappen, dann meldet man eine Kollision. Ist rasend schnell, aber ungenau. Diese Ungenauigkeit gibt oftmals Anlaá zum Žrger. Man stelle sich folgendes Szenario vor: der Spieler fliegt ein Raumschiff und muá Aliens killen, alles aus der Vogelperspektive (wow, wie kreativ). Das Rumpf des Schiffes ist eher schmal, doch die Tragfl„chen hinten sind sehr lang. Und jetzt kommt da eine Lasersalve eines Aliens von oben links her und fliegt auf das Schiff zu. Die Salve schl„gt ein - und zwar in der Luft! Fast so, als ob da ein unsicht- bares Hindernis gewesen w„re! Jedenfalls wurde fr das Spiel das Schiff ge- troffen. Na toll. Und wenn die meisten Schsse von oben kommen, sieht der Spieler berhaupt alt aus. Und das bloá wegen der bl”den Kollisionsroutine! Also, was tun? Zun„chst ist anzumerken, daá in den meisten F„llen keine Kollision stattfindet. Daher sollte man die "Bounding Box"-Routine behalten, um schnell herauszufinden, ob zwei Objekte NICHT oder M™GLICHERWEISE kolli- diert sind. Wenn die "Bounding Boxes" sich nicht berlappen, kann man gleich aufh”ren, denn in diesem Fall gibt es sicherlich KEINE Kollision. šberlappen sich aber die "Bounding Boxes" (ich nenne sie ab jetzt "BB"), so kann es m”glicherweise eine Kollision geben. Und jetzt kommen die Bitmasken ins Spiel. Um diese Routine einzusetzen, muá man vorher Bitmasken von jedem Grafikob- jekt, daá sp„ter fr eine Kollision in Frage kommt, berechnen. In dieser Bitmaske entsprechen die Pixel, die mit anderen Pixeln kollidieren k”nnen, einer 1, und durchl„ssige Pixel 0. Beispiel: 00045000 Dies w„re ein 8x5 Pixel-Objekt, wobei die Nummern einer Farbnummer 00045000 entsprechen. 45253415 00054000 00054000 00011000 Und dies w„re die dazugeh”rige Bitmaske, bei der die Pixel der 00011000 Farbe 0 "durchl„ssig" sind, d.h. wenn sich diese Pixel berlappen, 11111111 gibt es KEINE Kollisionsmeldung. 00011000 00011000 11100111 Hier wieder eine Bitmaske, bei der allerdings die Pixel der Farbe 4 11100111 und 5 (und nicht die der Farbe 0) durchl„ssig sind. 00101010 11100111 11100111 Und wie soll die Bitmaske aufgebaut sein? Eine Idee ist, sie als eine Ansammlung von 4-Byte-Variablen (in C w„ren das "long"-Variablen) aufzubauen. 4 byte (=ein longword, ich nenne es von nun an "Lword") k”nnen 32 bit speichern. Wenn wir uns also in der Breite auf ein Lword beschr„nken, kann man bloá bis zu 32 Pixel breite Objekte haben. Daher nimmt man mehrere Lwords fr die Breite. Wenn ein Bild in der Breite nicht ganz in einer Anzahl Lwords paát (d.h. wenn die Bildbreite kein Vielfaches von 32 ist) nimmt man ein Lwords dazu und ignoriert die brigbleibenden Bit. Ein C-Beispiel: long Bitmaske[Breite/32+((Breite % 32) ? 1 : 0)][Hoehe]; Gut, nun haben wir eine Bitmaske, aber wie benutzen wir sie? Wie schon erw„hnt, benutzen wir die BB-Routine, um festzustellen, ob wir eine m”gliche Kollision berhaupt in Betracht ziehen sollen. Wenn ja, nehmen wir die beiden Bitmasken her (wir nehmen hier an, daá eine Kollision zwischen zwei Objekten berprft wird) und berlagern sie mittels Bitverschiebungen. Danach UND-verknpft man die Bitwerte beider Bitmasken. Wenn das Ergebnis nicht 0 ist, gibt es irgendwo eine Kollision. Ok, gehen wir das langsam durch. Zun„chst brauchen wir zwei Bitmasken. Als Beispiel nehmen wir die hier: 1 2 011111110 000011110000 110000011 000110011000 110000011 001100001100 110000011 001100001100 011111110 000110011000 000011110000 Nun haben wir die Wahl: nehmen wir die erste Maske her und vergleichen sie mit der zweiten, oder umgekehrt? Prinzipiell ist das egal, allerdings ist es aus Geschwindigkeitsgrnden klger, die krzere Maske (sprich: die Maske mit der h”heren Y-Gr”áe, welche in diesem Fall Maske Nr. 1 w„re) zu nehmen und die andere mit ihr zu ver- gleichen. Wieso? Weil dann weniger Daten miteinander vergleichen werden mssen. Hierzu ein "Bild": 1 2 011111110 110000011 000011110000 110000011 000110011000 110000011 001100001100 011111110 001100001100 000110011000 000011110000 Wenn wir Maske Nr. 1 mit Maske Nr. 2 vergleichen, dann mssen wir alle Linien von Maske Nr. 1 durchgehen und berprfen, ob sie sich mit Linien von Maske Nr. 2 berlappen. Wir máten also 5 Linien berprfen. Umgekehrt ginge es genauso, allerdings máten wir da 6 Linien (und nicht 5) berprfen, da Maske Nr. 2 gr”áer als Maske Nr. 1 ist. (Ok, Geschwindigkeitsm„áig geht es um fast nichts, aber was solls.) So. Gut. Nun zum eigentlichen šberlappen: 000011110000 01111111110011000 1100000xx00001100 1100000xx00001100 11000001x10011000 01111111011110000 Hier fallen unsere beiden Bitmasken aufeinander und kollidieren in den Bits, die mit "x" gekennzeichnet sind. Zun„chst messe ich die Abst„nde der beiden Bitmasken voneinander relativ zur in Y-Richtung kleineren Maske (in diesem Fall Maske Nr. 1). Das w„re: xd=Maske2.x-Maske1.x; Aus dem Szenario nehme ich, um es einfach zu halten, Linie Nr. 3 heraus: 1100000xx00001100 Die Linie von Maske Nr.1 ist in diesem Fall: 110000011 Die Linie von Maske Nr.2 ist in diesem Fall: 001100001100 Dies w„ren nun beide Linien: 110000011 001100001100 (in Wirklichkeit liegen sie nicht so bereinander, sondern aufeinander, sie sind hier nur zur Verdeutlichung so angeordnet.) Wir nehmen nun Linie #2 (001100001100) her und machen damit eine Bitverschie- bung nach rechts, und zwar um den Faktor xd: Linie2=Linie2 >> xd Das Resultat: 110000011 0011 Dann machen wir eine UND-Verknüpfung: 110000011 UND 0011 --------- 000000011 Ha, das Ergebnis is nicht 0, also haben sich die Bitmasken irgendwo überlappt -> Kollision. Das machen wir nun mit jeder Linie, solange bis irgendwo das Ergebnis nicht 0 ist (oder bis alle Linien überprüft sind). 1997 by Darkvale