Assemblerecke: Rempeleien - Kollisionen von Shapes und Sprites

In der ST-Assemblerecke geht es um Kollisionen von Shapes und Sprites

Diesmal wollen wir uns mit Kollisionsabfragen für Shapes usw. beschäftigen. Diese werden ja sehr oft benötigt. So muß z. B. in einem Action-Spiel eine Überprüfung erfolgen, ob man vom Gegner erwischt wurde. Selbst im GEM-Desktop sind solche Tests zu finden, wenn beispielsweise der Mauszeiger in die Menüleiste bewegt und dann das entsprechende Pull-Down-Menü heruntergeklappt wird. Aufgrund dieser verschiedenen Anwendungsgebiete stehen mehrere Methoden zur Kollisionsabfrage zur Verfügung.

Das einfachste Verfahren ist das, welches auch bei unserem GEM-Mauszeiger zum Einsatz kommt. Dort wird einfach nur eine einzige Koordinate stellvertretend für den ganzen Mauspfeil getestet. Dieser eine Punkt liegt normalerweise in der Pfeilspitze. Um nun herauszufinden, ob diese einen Menüknopf oder ein Auswahlfeld berührt, überprüft man einfach, ob sich die erwähnte Koordinate innerhalb eines bestimmten Rechtecks befindet. Allerdings ist dies kein richtiger Kollisionstest; der Schaft des Pfeils kann ja durchaus ein Auswahlfeld berühren, ohne daß dies erkannt wird, da wir nur die Spitze kontrollieren. Deshalb ist diese Methode, die sich sehr einfach realisieren läßt, auch höchstens für Action-Spiele geeignet, bei denen man mit einem Fadenkreuz auf Gegner zielen muß. Auch für Kollisionstests bei Schüssen wird oft nur eine einzige Koordinate überprüft.

Einen Schritt weiter geht nun ein anderes Verfahren, das nicht nur eine, sondern vier Koordinaten kontrolliert. Dabei ziehen wir zunächst um unser Shape ein imaginäres Rechteck, dessen vier Eckpunkte wir dann überprüfen. Bei einem 8 × 8 Pixel großen Shape, das sich an der Position X, Y befindet, ist also für die vier Punkte X, Y, X+7, Y, X, Y+7 und X+7, Y+7 der erwähnte Test durchzuführen.

Leider hat auch diese Methode einige Nachteile. Zunächst muß für jedes Hindernis oder jedes fremde Shape eine eigene Kollisionsabfrage geschrieben werden, da die Größe dieser Objekte ja sehr unterschiedlich sein kann. Außerdem ist es möglich, daß eine ziemlich ungenaue Abfrage entsteht, wenn das Shape eine Form besitzt, die stark von einem Rechteck abweicht. Dann kann es passieren, daß ein Zusammenstoß registriert wird, obwohl keine Berührung einer Spielfigur mit einem Gegner stattfand. Das ist natürlich gerade bei Geschicklichkeits-Games sehr ärgerlich da sich der Spieler nun nicht; mehr auf das verlassen kann ‚ was er sieht. Trotzdem wird diese Abfragemethode am häufigsten eingesetzt, da sie relativ wenig Zeit kostet und auch einfach zu programmieren ist.

Außerdem läßt sie sich noch erheblich verbessern. So ist es oft ratsam, das Rechteck, das man sich um das Shape denkt, etwas kleiner zu wählen. So können zwar einige überhängende Teile ein Hindernis ungestraft berühren, dafür werden aber auch keine Kollisionen registriert, die man auf dem Schirm gar nicht sieht. Ferner ist es auch möglich, bei einem sehr unförmigen Shape mehrere Rechtecke zu bilden und dann den Test für 8, 12 oder mehr Koordinaten durchzuführen. Jedenfalls wird diese Methode bei fast allen geschwindigkeitsabhängigen Spielen benutzt, da sie viel weniger Rechenzeit kostet als die folgende.

Für dieses weitere Verfahren, Zusammenstöße festzustellen, benötigt man zunächst eine Kopie der Hintergrundgrafik im Speicher. Diese darf noch keine Spielfiguren, Gegner oder Hindernisse enthalten. Deshalb sollte ihre Anfertigung sofort nach dem Laden der Grafik erfolgen. Beim Kollisionstest wird dann der Platz, den unser Shape in der Ursprungsgrafik überdeckt, mit dem verglichen, der im aktuellen Bild belegt wird. Tritt dabei ein Unterschied auf, so muß in der Zwischenzeit irgendein anderes Objekt mit dem zu überprüfenden zusammengestoßen sein. Allerdings läßt sich dieser Test immer nur dann durchführen, wenn die Spielfigur das letzte Shape ist, das in der Grafik gesetzt wird. Außerdem muß die Überprüfung vor dem Kopieren des Shapes stattfinden, da ansonsten ja eine Kollision dieser Figur mit sich selbst festgestellt würde.

Der eigentliche pixelgenaue Test funktioniert dann folgendermaßen. Zuerst wird aus den ersten 16 Pixeln des Shapes eine Maske gebildet. In dieser müssen alle Bits gesetzt sein, die im Shape nicht durchsichtig sind. Deshalb nimmt man die ersten vier Wörter und verknüpft sie mit OR, so wie dies auch innerhalb von Shape-Set-Routinen geschieht. Danach rotiert man die Maske zwischen 0- und 15mal, je nachdem, welche X-Koordinate das Shape gerade einnimmt. Bei vorverschobenen Shapes kann dies unterbleiben. Nun verknüpft man die Maske zuerst mit der Kopie der Hintergrundgrafik, und zwar mit AND. Dadurch ist gewährleistet, daß alle Bits, die im Shape gesetzt sind, auch im Ergebnis gleich 0 sind. Die AND-Verknüpfung muß übrigens viermal hintereinander ausgeführt werden (für jede der vier Bitplanes). Erfolgt nun diese Berechnung auch mit dem aktuellen Bildschirminhalt, so läßt sich ohne Probleme feststellen, ob in einem der vier Wörter ein Unterschied gegenüber vorher aufgetreten ist.

Diesen Vergleich führt man dann für alle 16-Pixel-Segmente durch, von denen das Shape beim Setzen berührt wird. Leider ist dieses Verfahren aber sehr zeitaufwendig, da z.B. bei einem 16 x 16 Pixel großen Shape 32mal verglichen werden muß. Dies ist aber zu verschmerzen, da der Kollisionstest ja nur für die Spielfigur zu erfolgen hat. Außerdem kann bei einem sehr großen Shape auch darauf verzichtet werden, alle 16-Pixel-Blöcke zu testen; für die inneren Blöcke kann die Überprüfung ja unterbleiben. Hier muß man also nur die Randbereiche kontrollieren, da eine Kollision im allgemeinen nur dort auftritt. Größere Probleme bereitet da schon die Frage, mit welchem Gegner das Shape denn zusammengestoßen ist. Die Kollisionsabfrage ist dazu nämlich nicht geeignet; sie kann nur eine Berührung an sich feststellen. Deshalb muß man nach einer entsprechenden Meldung auch noch die Koordinaten der übrigen Figuren bzw. Objekte testen, um den Kollisionspartner zu finden. Jedoch ist dieser oft gar nicht wichtig, da diese Methode meistens nur angewandt wird, um zu überprüfen, ob die Spielfigur von Schüssen getroffen wurde oder bewegliche Hindernisse gerammt hat.

Alle drei bisher,besprochenen Methoden sind hauptsächlich dazu gedacht, Kollisionen eines Shapes mit einem anderen zu entdecken. Wie aber läßt sich ein Zusammenstoß mit dem Hintergrund feststellen? Schließlich soll z.B. bei einer „PacMan“-Version die Spielfigur ja nicht durch die Wände laufen können. Hier gibt es zwei grundsätzliche Lösungen. Einmal kann man durch Testen in der Bitmap herausfinden, ob man in der gewünschten Richtung auf eine Wand trifft. Da dies aber bei verschiedenen Wandsymbolen und nicht schwarzen Gängen sehr kompliziert werden kann, benutzt man meist eine ganz andere Methode. Ein „PacMan“-Spielfeld wird beispielsweise intern durch 40 x 25 Blöcke dargestellt, von denen jeder entweder eine Wand oder einen Gang symbolisiert. Wenn wir nun die Spielfigur durch das Labyrinth laufen lassen wollen, stellen wir sie auch als Zeiger auf einen Block dar. Sobald sie sich dann so weit bewegt hat, daß sie einen anderen Block berühren würde, schauen wir dort nach, ob dieser einen Gang oder eine Wand darstellt. Es werden also eigentlich keine Kollisionen ermittelt, sondern verhindert.

Dieses System läßt sich auch bei scrollenden Baller-Games oder Jump-and-Run-Spielen einsetzen, da es sehr einfach ist, die Blockgrößen zu verändern. Auch die Anzahl der verschiedenen Blöcke bereitet dabei keine Probleme, da dann eben mehrere Blöcke berührt werden dürfen bzw. nicht. Diese Methode hat außer ihrer Geschwindigkeit noch den Vorteil, daß man anhand der komprimierten Darstellung der Grafik innerhalb des Speichers auch andere Operationen schneller durchführen kann (Animationen der Blöcke usw.). Die Bitmap dient so nur noch als Anzeigeinstrument, da alle Tests jetzt innerhalb der Tabelle vorgenommen werden. Listing 1: KOLLIS_1.S

; Kollisionstest 1
; testet, ob ein 16*16 Pixel Shape
; mit irgendeinem anderen 16*16 Pixel Shape
; kollidiert und gibt bei einer
; Kollision die Koordinaten des
; fremden Shapes aus.
kollstart:
	move.w	x, d0	 ;x-und y Koor.
	move.w	y, d2
	move.w	d0, d1
	move.w	d2, d3
	add.w	#15, d1	; bei 16 Pixel
	add.w	#15, d3	; Shape
	move.l	#gegnerxy, a0
kollloop:
	move.w	(a0)+, d4	; x-Koor.
	move.w	(a0)+, d6	; Y-Koor.
	move.w	d4, d5
	move.w	d6, d7
	addq.w	#15, d5	; bei 16 Pixel
	addq.w	#15, d7	; Shapes
	cmp.w	d4, d0
	blt.b	nokol1	; links daneben
	cmp.w	d5, d0
	bgt.b	nokol1	; rechts daneben
	cmp.w	d6, d2
	blt.b	nokol1	; oben daneben
	cmp.w	d7, d2
	bgt.b	nokol1	; unten daneben
	bra.b	kollision	; Punkt liegt im Gegner.
nokol1:
	cmp.w	d4, d1	; Das gleiche
	blt.b	nokol2	; fuer Punkt
	cmp.w	d5, d1	; x+15, y
	bgt.b	nokol2
	cmp.w	d6, d2
	blt.b	nokol2
	cmp.w	d7, d2
	bgt.b	nokol2
	bra.b	kollision
nokol2:
	cmp.w	d4, d0	; Jetzt fuer
	blt.b	nokol3	; X, Y+15
	cmp.w	d5, d0
	bgt.b	nokol3
	cmp.w	d6, d3
	blt.b	nokol3
	cmp.w	d7, d3
	bgt.b	noko13
	bra.b	kollision
nokol3:
	cmp.w	d4, d1	; und nun fuer
	blt.b	nokol4	; x+15, y+15
	cmp.w	d5, d1
	bgt.b	nokol4
	cmp.w	d6, d3
	blt.b	nokol4
	cmp.w	d7, d3
	bgt.b	nokol4
	bra.b	kollision
nokol4:		; keine Koll.
	cmp.l	#gegnerxyend, a0	; also weiter
	blt.b	kollloop	; mit naechster Koor.
	rts		; gar keine Kollisionkollision:
	move.w	d4, gegnerx	; Koordinaten
	move.w	d6, gegnery	; des Gegners
	rts		; merken
x:
	dc.w	100
y:
	dc.w	100
gegnerx:
	dc.w	0
gegnery:
	dc.w	0
gegnerxy:
	dc.w	10, 50, 70, 80, 110, 90, 40, 30
gegnerxyend:
	dc.l	0
; als Ergebnis wird hier 110, 90 ausgegeben,
Listing 2: KOLLIS_2.S
; Kollisionstest 2
; testet, ob ein 16*16 Shape
; irgendwo ein anderes berührt.
; Muß vor dem setzen des Shapes aufgerufen werden,
; natuerlich sollte der Test in die Shape-Set Routine
; integriert werden, da dann viel Rechenzeit gespart wird,
kolltest:
	move.w	x, d0	; X-Koor.
	move.w	y, d1	; Y-Koor.
	move.w	d0, d2
	lsr.w	#4, d0	; Startadressen
	lsr.w	#3, d0	; des Shapes
	mulu	#160, d1	; in aktuellen
	move.l	#screen, a0	; Bild und in
	move.l	#kopie, a1	; leerer Kopie
	add.l	d0, a0	; berechnen.
	add.l	d1, a0
	add.l	d0, a1
	add.l	d1, a1
	and.w	#15, d2
	move.l	#shape, a2	; Startadr.
	move.w	#15, d0	; Shape
loop:
	moveq	#0, d1
	movem	(a2)+, d1	; Maske des
	or.w	(a2)+, d1	; Shapes
	or.w	(a2)+, d1	; berechnen.
	or.w	(a2)+, d1
	ror.l	d2, d1	; und rotieren
	move.w	(a1)+, d3	; erstes Wort
	move.w	(a0)+, d4	; der beiden
	and.w	d1, d3	; sitmaps mit
	and.w	d1, d4	; Maske verknüpfen,
	cmp.w	d3, d4	; danach vergleichen
	bne.b	kollision
	move.w	(a1)+, d3	; 2. Wort
	move.w	(a0)+, d4
	and.w	d1, d3
	and.w	d1, d4
	cmp.w	d3, d4
	bne.b	kollision
	move.w	(a1)+, d3	; 3. Wort
	move.w	(a0)+, d4
	and.w	d1, d3
	and.w	d1, d4
	cmp.w	d3, d4
	bne.b	kollision
	move.w	(a1)+, d3	; 4. Wort
	movem	(a1)+, d4
	and.b	d1, d3
	and.w	d1, d4
	cmp.w	d3, d4
	bne.b	kollision
	swap	d1	; Maske 2. 16 Bit
	move.w	(a1)+, d3	; 1. Wort
	move.w	(a0)+, d4	; 2. Block
	and.w	d1, d3
	and.w	d1, d4
	cmp.w	d3, d4
	bne.b	kollision
	move.w	(a1)+, d3	; 2.Wort
	move.w	(a0)+, d4	; 2.Block
	and.w	d1, d3
	and.w	d1, d4
	cmp.w	d3, d4
	bne.b	kollision
	move.w	(a1)+, d3	; 3. Wort
	move.w	(a0)+, d4	; 2. Block
	and.w	d1, d3
	and.w	d1, d4
	cmp.w	d3, d4
	bne.b	kollision
	move.w	(a1)+, d3	; 4. Wort
	move.w	(a0)+, d4	; 2. Block
	and.w	d1, d3
	and.w	d1, d4
	cmp.w	d3, d4
	bne.b	kollision
	add.l	#144, a0	; nächste Zeile
	add.l	#144, a1	; testen.
	dbra	d0, loop
	move.w	#0, kollisionflag	; Flag auf 0
	rts		; Fertig
kollision:
	move.w	#1, kollisionflag	; Flag setzen
	rts		; Ende
kollisionflag:
	de.w	0
x:
	dc.w	100
y:
	dc.w	100
shape:
	blk.b	128, 255
kopie:
	blk.b	32000, 0
screen:
	blk.b	32000, 0