Die Kollisions-Engine

Wird eine Entity nicht durch direktes Verändern ihrer Position, sondern über die c_move- oder c_rotate-Funktionen oder durch die Physik-Engine bewegt, werden Kollisionen mit anderen Entities oder der Levelgeometrie automatisch ermittelt und können Reaktionen hervorrufen. Mögliche Reaktionen sind automatisches Entlanggleiten am Hindernis oder Skript-Funktionen, die durch Entity-Events wie EVENT_IMPACT, EVENT_BLOCK, EVENT_ENTITY, EVENT_FRICTION, oder EVENT_PUSH ausgelöst werden.

Um zu verhindern, dass Actors sich mit ihren Gliedern oder Waffen verheddern, verwenden Spiele-Engines nicht deren reale Form, sondern eine einfache Hülle für sich bewegende Actors - normalerweise eine Kugel, eine Kapsel oder ein Ellipsoid. Unbewegliche Hindernisse wie Terrain oder Level-Geometrie, Türen oder Lifte verwenden eine poygonale Hülle. Für eine Kollision eines sich bewegenden Actors mit einem Hindernis benutzt die Engine eine Ellipsoid Polygon-Kollisionserkennung. Mit der Ellipsiod-Hülle lassen sich viele Kollisionstypen emulieren, z.B. Zylinder, Kugeln oder flache Scheiben. Für Begegnungen zwischen sich bewegenden Actors benutzt die Engine eine OBB OBB-Kollisionserkennung. OBB bedeutet 'oriented bounding box' (ausgerichtete Begrenzungsbox) und stellt eine rechteckige Box um die Entity dar, die sich mit ihr dreht. Diese beiden Kollisionstypen decken sämtliche möglichen Kollisionen ab, die in einem Spiel vorkommen können.

Die Engine weiß nicht von selbst, ob eine bestimmte Entity ein sich bewegender Actor, ein Hindernis oder überhaupt für Kollisionen irrelevant ist. Per Default nimmt die Engine an, dass sämtliche Objekte für Kollisionserkennung von Bedeutung sind und weist Modellen und Sprites eine einfache Hülle zu; Map-Blocks, Map-Entities und Terrain bekommen eine polygonale Hülle. Wird für ein Objekt in Ihrem Level irgendetwas Anderes gewünscht, müssen Sie dies der Engine mitteilen, indem Sie im Level-Editor oder im Entity-Skript Objektflags setzen. Die folgenden Flags sind hierfür von Bedeutung:

WED Script Kommentar
Detail -

Keine Kollisionserkennung. Verwenden Sie dieses Flag für alle Blocks, die nicht als Hindernis fungieren sollen und den BSP-Tree nicht beeinflussen.

Passable PASSABLE

Keine Kollisionserkennung. Verwenden Sie dieses Flag für alle Entities, die nicht als Hindernis fungieren sollen.

Polygon POLYGON

Für Modelle, die als polygonales Hindernis fungieren sollen. Verwenden Sie es nicht für sich bewegende Actors!

BBox c_setminmax()

Für Entities, die anstelle der Standardgrößen ihre tatsächliche Größe für die einfache Kollisionshülle verwenden sollen.

!! Es funktioniert in den meisten Fällen, wenn man sich gar nicht um Kollisions-Flags kümmert. Wenn Sie aber große Modelle in Ihrem Level verwenden, beispielsweise für Felsen oder Gebäude, die als polygonale Hindernisse fungieren sollen, klappt das nicht. Selbst für kleinere Hindernisse möchten Sie evtl. das POLYGON-Flag setzen. Es ist etwas langsamer, garantiert aber eine genauere Kollision und ein sanfteres Entlanggleiten an den Oberflächen.

Die Kollisionshülle

Abhängig vom Hindernis verwenden die move- und trace-Funktionen verschiedene Kollisionshüllen:

Hindernis
Modell, Sprite Modell (POLYGON) Terrain, Map, Level
c_trace Linie Polygon Linie Polygon Linie Polygon
c_trace (USE_BOX) Ellipsoid Polygon Ellipsoid Polygon Ellipsoid Polygon
c_move OBB OBB Ellipsoid Polygon Ellipsoid Polygon

Ellipsoide oder OBB-Boxen sind orientiert, d.h. sie drehen sich mit der Entity mit. Für eine korrekte OBB-Kollisionserkennung sind Größe und Form der Begrenzungs-Ellipsoiden oder -Boxen von Bedeutung. Per Default bekommen Entities in Abhängigkeit ihrer FAT- und NARROW-Flags eine X/Y-symmetrische Hülle in zwei Standardgrößen. Diese beiden Standard-Größen können getrennt für jeden Level in den Map Compiler -Einstellungen vorgegeben werden. Die Hüllen sind um den Entity-Nullpunkt zentriert; der Nullpunkt muss hoch genug liegen, dass die Entity auf Treppen gehen kann, ohne mit der Hülle den Boden zu berühren. Verwendung von Standardgrößen ist wichtig für Actors in einem Shooter oder RPG, um sicherzustellen, dass sie unabhängig von ihrer tatsächlichen Form stets durch die gleichen Türen passen. Sie können auf diese Weise vermeiden, dass eine Öffnung nur ein wenig größer als die Kollisionshülle eines Actors ist - das kann andernfalls zum Steckenbleiben von Actors führen.

NARROW
FAT

Falls in Spezialfällen erforderlich - z.B. für einen sehr großen Actor - kann die Hülle entweder durch Setzen des BBox-Flags in WED, durch Aufrufen von c_setminmax, oder durch gleichzeitiges Setzen von FAT und NARROW und Setzen der min_x...max_z-Parameter, an die tatsächliche Größe der Entity angepasst werden. Für Objekte wie Autos, Raketen oder Torpedos ist eine schlanke, langgestreckte Hülle die passendste Form. Für Actors eignet sich am besten eine symmetrische Hülle von der Gestalt einer vertikalen Säule. Symmetrie ist wichtig, denn wenn sich eine unsymmetrische Hülle dreht, kann sie auch dann mit Hindernissen kollidieren, wenn sich die Position der Entity nicht verändert. Daher muss, wenn eine unsymmetrische Entity während der Rotation mit etwas kollidieren kann, die Funktion c_rotate zu ihrer Drehung benutzt werden. Hat die Hülle dagegen in X- und Y-Richtung die gleichen Abmessungen, kann die Entity ihren horizontalen Winkel (pan) direkt verändern, ohne sich dabei um c_rotate kümmern zu müssen. Für ein kugelförmiges Ellipsoid wird c_rotate überhaupt nicht gebraucht.

Kollisionserkennung erfordert CPU-Zeit und sollte so wenig wie nötig benutzt werden. Verwenden Sie z.B. kein Kollisionsvolumen (USE_BOX), wenn eine Linienkollision genügen würde. Physik-Kollisionen sind auf nVidia Grafikkarten schneller, da sie dort hardwarebeschleunigt sind. Bei Physikkollisionen haben Sie ebenfalls die Wahl zwischen einfachen Hüllen - Kapseln, Boxes, oder Kugeln - und einer konvexen Polygonhülle der pXent_settype.

Anmerkungen zu c_trace, c_move und c_rotate

Sowohl c_move, als auch c_rotate verwenden intern c_trace, wobei sie automatisch USE_BOX setzen und für zusätzliche Funktionen wie etwa Gleiten sorgen.nIst USE_BOX nicht gesetzt, wird die c_trace-Kollision immer einen Strahl benutzen. Ist der USE_BOX-Modus gesetzt, testet c_trace eine ellipsoide Hülle gegen polygonale Ziele. Die Kollisionsform, die von c_move oder c_rotate verwendet wird, ist entweder ein ausgerichteter Ellipsoid oder eine ausgerichtete Box. Welches von Beidem benutzt wird, hängt davon ab, ob die Kollision mit einem polygonalen oder einen nicht polygonalen Ziel geschieht.

Levelkollisionen werden immer unter Verwendung des Ellipsoiden durchgeführt. Auch Entitykollisionen werden mit der Ellipsoid vs. Polygon-Routine durchgeführt, vorausgesetzt, dass die Zielentity (diejenige, die sich nicht bewegt) das POLYGON-Flag gesetzt hat oder der USE-POLYGON-Modus aktiviert ist. Per Default ist bei Terrains POLYGON auf on und bei sämtlichen anderen Entities POLYGON auf off gestetzt.

Der Grund für das Verwenden unterschiedlicher Kollisionshüllen liegt in Geschwindigkeit und Stabilität. Bei Entities mit einer hohen Polygonzahl ist die Verwendung ihrer Box schneller. Entities, die sich bewegen, können sich nach Ablauf der Kollision mit der Ellipsoid-Polygon-Routine verheddern. Verwenden Sie aus diesem Grund keine Ellipsoid-Polygon-Routine für Kollisionshindernisse, die 'Haken' oder 'Lücken' haben an denen sich eine sich bewegende Entity hängenbleiben kann.

Die Default-Hüllen heissen NARROW und FAT. NARROW ist eine Kugel ums Zentrum der Entity mit einem Radius von 16 Einheiten. FAT ist ein Ellipsoid entlang der X- und Y-, sowie der positiven Z-Achse mit einem Radius von 32 Einheiten. Entlang der negativen Z-Achse dehnt sie sich jedoch nur 16 Quants aus. Die Default-Hüllengrösse aktivieren Sie, indem Sie den passenden Flag auf on und den anderen auf off setzen. Alle nachfolgenden c_trace- / c_move- / c_rotate-Aufrufe werden dann die neue Hüllengrösse benutzen. Zum Aktivieren der NARROW-Hülle in einer Entity-Aktion schreiben Sie somit (s. Abbildungen oben):

set(my,NARROW); 
reset(my,FAT);

Um persönliche Hüllengrössen verwenden zu können, müssen Sie beide Flags, sowohl NARROW, als auch FAT auf on setzen. Dann müssen Sie die Bounding-Box einstellen indem Sie die min_x, min_y, min_z und max_x, max_y, max_z-Parameter der Entity einstellen. Am einfachsten lässt sich dies bewerkstelligen indem man c_setminmax (me) aufruft. Durch zweimaliges Drücken von [F11], sehen Sie im Engine-Fenster die Bounding-Boxen sämtlicher Entities in blau.

c_setminmax() verwendet nur die Vertex-Ausdehnung des ersten Frames eines MDL. Wollen Sie die Ausdehnung eines anderen Frames verwenden, müssen Sie stattdessen c_updatehull (my, N) aufrufen. Dies setzt my.min_xyz / max_xyz gemäss der Bounding-Box bei Frame Nummer N. Die Minimal- und Maximal-Ausdehnung einer Entity wird beim laden / ent_create gesetzt. So kann c_setminmax diese Werte schnell in my.min_xyz/ max_xyz kopieren. Während c_setminmax im wesentlichen frei ist (das Update der Hüllengrösse beansprucht sehr wenig Zeit), kann c_updatehull einige Zeit zur Ausführung brauchen, denn es muss die Vertices des spezifischen Frames neu laden. Daher sollten Sie c_updatehull nicht mit jedem einzelnen Frame aufrufen, sondern lediglich für grössere Animationsänderungen benutzen, wie eine Stehenden Figur, die nun kniet. Aus demselben Grund sollten Sie c_setminmax(my) nicht anstelle von c_updatehull(my,0) aufrufen - beide erzielen dasselbe Ergebnis, aber c_updatehull ist viel langsamer. Wenn Sie die Ausmaße Ihrer Entity kennen, ist am schnellsten Sie setzen my.min_xyz/ max_xyz direkt.

Auch wenn sich die Hülle auf willkürliche Ausmaße setzen lässt, ist es empfehlenswert, dass sie, wann immer möglich symmetrisch ist. Werden entlang der x-, y-, und z-Achsen verschiedene Radien verwendet, kann es bei c_rotate eher passieren, dass Ihr Player beim Drehen stecken bleibt.

Mit einer Ellipsoid-Kollision ist das Entlanggleiten an Wänden und Neigungen ein sehr einfacher Prozess. Geben Sie im Funktionsaufruf lediglich die relative Vorwärtsbewegung an und für die Schwerkraft fügen Sie ausserdem die absolute Abwärtsgeschwindigkeit hinzu. Dadurch kann sich Ihre Figur effizient in seiner Umgebung sowie entlang von Neigungen bewegen. Allerdings müssen die Werte bei der Verwendung von Treppen oder Neigungen auf die spezifische Figurenhöhe und die Framerate maßgeschneidert werden. Wollen Sie eine Entity davon abhalten, sich eine Treppe hinaufzubewegen, müssen Sie entweder ihren Vorwärtsimpuls reduzieren oder ihre Schwerkraft erhöhen. Wollen Sie andererseits, dass eine Entity eine bestimmte hohe Treppe erklimmt, werden Sie ihre Vorwärtsgeschwindigkeit erhöhen oder die Schwerkraft verringern müssen. Mit ausreichend hoher Geschwindigkeit ausgestattet, kann eine Entity jede Stufe, die bis halb so hoch wie sie selbst ist, ersteigen können (vorausgesetzt, c_setminmax wurde dazu benutzt, den Ellipsoiden so hoch wie dei Entity zu setzen.)

Aus diesen Gründen verwenden GameStudios Template-Skripte stattdessen zwei c_move-Aufrufe. Einen für die Schwerkraft, den zweiten zum Umgang mit den Kräften, die auf den Player wirken. Dies ist eine flexiblere Lösung, die mehr Kontrolle ermöglicht, aber langsamer ist als ein einzelner c_move-Aufruf.

Wie Kollision intern funktioniert

Nach den Anfangs-SetUps, machen c_trace und c_move damit weiter, Entities auf mögliche Kollisionen hin zu überprüfen. Ist ACTIVATE_TRIGGER nicht aktiviert, kann die Engine ihren Binärbaum benutzen und nur nahegelegene Entities überprüfen. Ist ACTIVATE_TRIGGER hingegen akriviert, ist es nötig, jede Entity im Level zu überprüfen, denn die Trigger-Reichweite kann beliebig groß sein. Daher sollten Sie ACTIVATE_TRIGGER nur dann benutzen, wenn Sie es auch wirklich brauchen.

Angenommen IGNORE_CONTENT ist für jede Entity im Levelabschnitt (oder, falls ACTIVATE_TRIGGER benutzt wird, im ganzen Level) gesetzt, wird ihr Typ geprüft, um zu sehen, ob ihre Flags IGNORE_MODELS, IGNORE_TERRAIN, IGNORE_SPRITE und IGNORE_MAP passen. Kann die Entity gemäß dieser Flags ignoriert werden, wird die nächste Entity in der Reihe geprüft. Sollte der Entity-Typ gültig sein, wird er mit you und me (vorausgesetzt IGNORE_ME oder IGNORE_YOU ist gesetzt) verglichen. Schliesslich werden die Bounding-Kugeln von me und die gegenwärtige Entity auf ein Überlappen hin geprüft. Deuten all diese Tests darauf hin, dass die Entities kollidieren könnten, wird weiteres Verarbeiten erforderlich.

Ist IGNORE_CONTENT nicht gesetzt, wird eine präzise Kollision mit allen nahegelegenen passable Map- und Terrain-Entities durchgeführt, egal, ob IGNORE_MAP, IGNORE_PASSENT oder IGNORE_TERRAIN gesetzt ist. An dieser Stelle werden in_passable, on_passable und passable_ent auf den neusesten Stand gebracht, um auf die gegenwärtige Entity zu zeigen falls der Startpunkt des Trace innerhalb der an den Achsen der Entity ausgerichteten Boundign Box liegt. Bei Terrains muss sich die Bounding- Box bis ganz hinunter zum Grund des Levels ausdehnen. Befindet sich keine passable Entity am Startpunkt, dafür aber entlang der Trace-Linie, wird passable_ent stattdessen auf diesen gesetzt und on_passable wird ebenfalls gesetzt.

Nachdem sämtliche Entities auf diese Weise bearbeitet wurden, werden die Level-Blocks geprüft. Um diese Prüfung abzustellen, muss IGNORE_MAP gesetzt sein.

Ist dies erledigt, wird ein gründlicher (d.h. langsamer) Test zwischen den angefragten Bounding-Formen (Strahl, Ploygon, OBB oder Ellipsoid) durchgeführt. Alle Schnittpunkte werden gespeichert und nach ihrem Abstand vom Ursprung des Trace sortiert. An dieser Stelle werden Kontakte mit verschieblichen und passablen Entities fallengelassen. Der nächstgelegene Treffer (falls es einen gibt) wird zurückgeliefert.

Gleiten und Drehen

Bewegung und Drehung werden intern durch Aufrufen von c_trace mit gesetztem USE_BOX erreicht.

Im Falle einer Kollision mit gesetztem GLIDE-Flag, berechnet GameStudio einen auf Bewegungsrichtung und Kontakt-Normale basierenden Reflexions-Vektor. Entlang dieses Reflexionsvektors wird ein zweiter Trace durchgeführt. Führt dies zu einer neuerlichen Kollision, wird ein neuer Reflexionsvektor errechnet etc. Nach maximal 3 Kollisionen gibt c_move auf.

Gleiten lässt sich auf die XY-Ebene beschränken indem man disable_z_glide auf 1 setzt. Per Default kann sich der Ellipsoid jede Neigung, egal wie steil, hinaufbewegen. Um diese Bewegung zu beschränken, können Sie die allgemeine Variable move_min_z abändern. Ist die Z-Achse der Kontakt-Normalen niedriger als dieser Minimalwert, wird entlang von Z überhaupt kein Gleiten stattfinden. Das Auftreffen auf der Grundebene ergibt einen Normal.z-Wert von 1.0 (senkrecht nach oben zeigend). Das Treffen der Decke liefert -1.0 (senkrecht nach unten) und eine Kopf-Voraus-Kollision mit einer senkrechten Wand bekommt einen Normal.z-Wert von 0. Der Default-Wert von move_min_z ist -1, was ein Gleiten in allen Winkeln ermöglicht. Haben Sie das stattdessen auf 0.5 gesetzt, werden alle Neigungen, die steiler als 60 Grad sind (=acos[0.5]) die Entity zum Stehen bringen und vom hinaufgleiten abhalten. Dieses Beispiel gilt nur für kugelförmige Hüllen. Bei einem Ellipsoiden ist einiges an Versuch und Irrtum erfordelich, um den richtigen Wert herauszufinden. Es ist eher zu empfehlen, zum Abblocken unsichtbare Entities vor steile Wände zu stellen, als sich auf move_min_z zu verlassen.

c_rotate versucht zunächst eine Rotation auf der Stelle indem die gewünschten Winkel gesetzt werden. Führt dies zu einer Kollision, wird ein Gleitvektor, ähnlich dem obigen berechnet und c_move wird aufgerufen, um die Entity auf einen bestimmten Abstand zur Wand wegzustossen. Wieder wird eine Drehung versucht. Sollte diese gelingen, wird die Entity in Richtung ihres Startpunktes zurückbewegt. Ansonsten wird eine weitere Reflexion berechnet und c_move wird aufgerufen. Im schlimmsten Fall wird c_trace 5 mal und c_move 4 mal von c_rotate aufgerufen, bevor aufgegeben und der Player zu seiner Startposition bzw. -Ausrichtung zurückbewegt wird. Es trägt wesentlich zur Steigerung der Performance von c_rotate bei, Entity-Hüllen meist symmetrisch zu halten und V-förmige Levelgeometrie zu vermeiden.

► Aktuelle Version Online