Seminarausarbeitung Die Halflife-Engine - Informatik

Universität Paderborn
Fakultät für
Elektrotechnik, Mathematik und Informatik
Seminarausarbeitung
Die Halflife-Engine
Lars Tegeler
vorgelegt bei
Prof. Dr. Hans Kleine Büning
Inhaltsverzeichnis
1 Einleitung
1
2 3D-Spiele-Engines
2.1 Entwicklungsgeschichte . . . . . . . . . . . . . . . . . . . . . .
2.2 Arten von 3D-Engines . . . . . . . . . . . . . . . . . . . . . .
2.3 Modellierung der 3D-Welt . . . . . . . . . . . . . . . . . . . .
2
2
4
5
3 Half-Life
3.1 Besondere Merkmale der Half-Life-Engine
3.2 Die Half-Life Welt . . . . . . . . . . . . .
3.2.1 Objekte . . . . . . . . . . . . . . .
3.2.2 Vektoren . . . . . . . . . . . . . . .
3.2.3 Map . . . . . . . . . . . . . . . . .
3.2.4 Binary Space Partitioning . . . . .
3.2.5 Kollisionserkennung . . . . . . . . .
3.3 Programmstruktur . . . . . . . . . . . . .
3.4 Modifikationen . . . . . . . . . . . . . . .
3.4.1 Entwicklungsumgebung . . . . . . .
3.4.2 Beispiel: Geschwindigkeit der RPG
3.4.3 Beispiel: DropXP . . . . . . . . . .
4 Bot’s
4.1 Bot’s
4.1.1
4.1.2
4.1.3
4.1.4
4.2 Bot’s
4.3 Bot’s
erstellen und kontrollieren
Generierung . . . . . . .
Steuerung . . . . . . . .
Wahrnehmung . . . . . .
Beschränkung . . . . . .
in Modifikationen . . . . .
in Proxy-DLL’s . . . . . .
ii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
7
9
9
10
10
10
13
14
15
16
17
17
.
.
.
.
.
.
.
18
18
18
19
19
21
22
22
INHALTSVERZEICHNIS
iii
5 Vergleichende Darstellung
24
5.1 Tabelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
A Klassendiagramme
26
A.1 Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
A.2 Client . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Abbildungsverzeichnis
2.1 Wolfenstein . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Quake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
Half-Life . . . . . . . . . .
Skeletal Animation System
BSP Beispiel(Schritt 1) . .
BSP Beispiel(Schritt 2) . .
BSP Beispiel(Schritt 3) . .
Bounding-Box . . . . . . .
Achsen-Ausrichtung . . . .
Programmstruktur . . . .
Counter-Strike . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
4
6
8
11
12
12
13
13
14
16
4.1 Bot-Wahrnehmung . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Bot-Proxy-Dll . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
iv
Listings
3.1
3.2
3.3
4.1
4.2
4.3
4.4
Orginal: Rpg.cpp (in FollowThink) . .
Änderung: Rpg.cpp (in FollowThink) .
Player.cpp (in DropPlayerItem) . . . .
Bot-Generieung . . . . . . . . . . . . .
Bot-Steuerung . . . . . . . . . . . . . .
Bot-Sicht . . . . . . . . . . . . . . . .
Engine-Header(common/com model.h)
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
17
17
18
19
20
22
Kapitel 1
Einleitung
In der Projektgruppe Multiagentensysteme in 3D-Umgebungen“ wird durch
”
den Einsatz von 3D-Engines an einer möglichst realistischen Simulationsumgebung für Agenten gearbeitet. Ziel ist es, die Kommunikation, Kooperation
und eine kollektive Zielverfolgung zwischen Agenten zu simulieren. Zu diesem Zweck wurden herkömmliche 3D-Engines der Spiele Quake, Half-Life
und Unreal auf ihre Verwendbarkeit hin überprüft. Als nächster Schritt ist
die Implementation von Agenten in einer dieser Engines geplant.
Weiter Informationen sind auf den Seiten der Projektgruppe zu finden:
http://www.uni-paderborn.de/cs/agklbue/de/courses/ss03/kimas/project/index.html
Im Folgenden gehe ich genauer auf die Untersuchung der 3D-Engines des
Spiels Half-Life ein. Dazu gebe ich zunächst einen kurzen Überblick über die
Entwicklung von 3D-Spiele-Engines und deren Kernmerkmalen. Im Hauptteil werden die Details der Half-Life-Engine, die Möglichkeiten, eine Welt für
unsere Zwecke anzupassen, und die Integration von Agenten1 erörtert. Abschließend zeigt ein Vergleich mit den Spielen Quake und Unreal die Stärken
und Schwächen von Half-Life in kompakter Form.
1
Später auch als Bot bezeichnet, was in Computerspielen ein vom Computer gesteuerter
Spieler ist.
1
Kapitel 2
3D-Spiele-Engines
Die heutigen 3D-Spiele-Engines bieten eine sehr realistische Simulation einer
dreidimensionalen Welt nicht nur im Hinblick auf die grafische Darstellung,
sondern hinsichtlich der Simulation einer Welt, die auf realen physikalischen
Gesetzen basiert. Gerade in den letzten Jahren haben die so genannten First
”
person shooter1“ immer mehr an Realismus dazugewonnen.
2.1
Entwicklungsgeschichte
Als erstes dieser Art von First person shooter“ brachte 1993 id Software
”
das Spiel Wolfenstein 3D[siehe Abb. 2.1] auf den Markt. Hier konnte der
Spieler durch eine Labyrinth laufen und wurde dabei von Gegnern verfolgt.
Allerdings wurde der dreidimensionale Effekt nur durch geschickte Verwendung von zweidimensionalen Bildern erweckt, die je nach Entfernung verschieden groß dargestellt wurden. Von einer wirklichen physikalischen Simulation konnte noch nicht die Rede sein.
Als erste Weiterentwicklung brachte id Software das Spiel Doom im Jahr
1994 auf den Markt. Hierbei wurden die dreidimensionalen Ansichten erstmals wirklich aus einer vorgegeben Karte zur Laufzeit errechnet; und auch
physikalische Effekte, wie zum Beispiel das Rutschen auf glatten Flächen,
wurden erstmals simuliert. Jedoch blieb die Beschränkung auf eine horizontale Ebene bestehen, so das sich der Spieler immer noch nicht wirklich frei“
”
bewegen konnte.
1
Spiel aus Sicht der ersten Person. Später auch als Ego-Shooter bezeichnet.
2
KAPITEL 2. 3D-SPIELE-ENGINES
3
Abbildung 2.1: Wolfenstein
Die Firma 3D Realms entwickelte dann 1995 das Spiel Duke Nukem 3D. In
diesem Spiel ist dann auch die Beschränkung gefallen, dass man sich nur in
einer Ebene bewegen kann. So konnte man mit Düsenpacks“ im Level herum
”
fliegen und dadurch höher gelegene Ebenen erreichen. Abgesehen von dem
fixen horizontalen Blickwinkel konnte man also die Welt von jeder möglichen
Position aus betrachten. Zudem wurden die physikalischen Effekte immer
mehr erweitert; durch die Möglichkeit zu fliegen oder zu schwimmen brauchte
man auch eine Simulation von Auftrieb und Erdanziehung.
Auf diese Entwicklung reagierte id Software dann 1996 mit Quake [siehe Abb.
2.2]. Die Quake Engine ermöglichte dem Spieler erstmals, sich wirklich frei
zu bewegen und auch in jede Richtung zu schauen. Außerdem wurden die
Gegner nicht mehr als 2D-Bilder in die Welt eingeblendet, sondern als 3DModelle berechnet. Damit kam also die erste vollständige 3D-Spiele-Engine
auf den Markt.
Als 1997 Valve Software mit Half-Life, id Software mit Quake II und Epic
mit Unreal weiter Spiele-Engines entwickelten, gab es eigentlich keine bahnbrechenden Neuerungen mehr, nur die Grafische Darstellung wurde etwas
verschönert2 .
2
Quake machte man insgesamt bunter, bei Half-Life wurde die Umgebung düsterer und
bei Unreal mischte man eine düstere Umgebung mit bunten Anzeigen.
KAPITEL 2. 3D-SPIELE-ENGINES
4
Abbildung 2.2: Quake
Die heutige Entwicklung der 3D-Spiele-Engines versucht durch bessere Graphikdarstellung3 und der Simulation von immer mehr physikalischen Gesetzen ein noch realeres Modell der wirklichen Welt im Computer nach zu
bilden.
2.2
Arten von 3D-Engines
Bei den 3D-Engines kann zwischen zwei Arten unterschieden werden, einmal
den Indoor-Engines zur Simulation von Räumen und den Outdoor-Engines
zur Simulationen von offenen Welten.
Outdoor-Engines
Bei den Outdoor-Engines soll eine gesamte Welt mit allen Zusammenhängen
simuliert werden. Gerade da die zu simulierende Welt nicht geschlossen ist,
ergibt sich das Problem der Komplexität einer solchen Welt, wozu die heutigen Outdoor-Engines noch nicht leistungsfähig genug sind.
3
Welche durch immer bessere Grafikkarten ermöglicht wird.
KAPITEL 2. 3D-SPIELE-ENGINES
5
Indoor-Engines
Eigentlich alle gängigen First person Shooter“ basieren auf Indoor-Engines.
”
Jeder Raum wird sozusagen als geschlossenes System betrachtet, das mit anderen Räumen durch Gänge verbunden ist. Mann kann also aus einem Raum
nicht jemanden in einem anderen Raum treffen, und deshalb erspart man
sich die Berechnung entsprechender Kollision und Abhängigkeiten. Daraus
ergibt sich die effiziente Anwendung von Indoor-Engines für First person
”
Shooter“.
2.3
Modellierung der 3D-Welt
Bei den heutigen 3D-Spiele-Engines wird die Welt aus einem dreidimensionalen Modell berechnet, welches in einer Karte gespeichert ist, sowie aus den
einzelnen Objekten, die in dieser Welt existieren, wie z.B. andere Spieler,
Waffen, etc. Dazu verwaltet die Engine, an welcher Stelle in der Karte sich
die einzelnen Objekte befinden, z.B. durch Vektoren4 . Dieses Modell der Welt
wird dann durch verschiedene Computergrafische-Verfahren(Raytracing, Radiositi, Projektion)5 zu einem zweidimensionalen Abbild der dreidimensionalen Welt. So kann jeder mögliche Zustand der Welt zur Laufzeit abgebildet
werden. Die Interaktion der Objekte untereinander und die physikalischen
Gesetze werden mit Hilfe von geeigneten Algorithmen (z.B. zur Kollisionserkennung) umgesetzt.
4
Ein Vektor repräsentieren die X,Y,Z-Koordinate des Objekts vom Nullpunkt aus.
Durch Raytracing und Projektion wird das 3D-Modell nach 2D abgebildet, Radiositi
erzeugt einen realeren Beleuchtungs-Effekt.
5
Kapitel 3
Half-Life
Das Computerspiel Half-Life war das erste Projekt, das von der Firma Valve Software entwickelt wurde. Dabei handelt es sich um einen Ego-Shooter,
bei dem man die Figure des Wissenschaftler Gordon Freeman spielt, der im
Inneren einer staatlichen Forschungseinrichtung an einem Projekt für Dimensionsportale arbeitet. Ein Versuch misslingt und öffnet eine Tor in eine
Dimension voller Monster. Das Spiel wurde dann 1997 von Sierra On-Line
vertrieben und wurde mit seiner düsteren Stimmung, unter Ego-ShooterSpielern beliebt.
Abbildung 3.1: Half-Life
6
KAPITEL 3. HALF-LIFE
7
Dabei ist die 3D-Engine, die Valve Software verwendet, keine alleinige Eigenentwicklung, sondern basiert auf den Quake Engines von Id Software. Sie
ist eine Modifikation der Quake Engine, mit Teilen von Quake II und einigen
eigenen Weiterentwicklungen.
Es wird immer wieder vermutet, dass die Verwendung der Direkt-X Schnittstele1 , und die Tatsache dass das Spiel nur unter Windows läuft2 nicht zuletzt
damit zusammenhängt, dass bei Betrachtung des Softwareteams von Valve
auffällig ist, dass einige der Verantwortlichen (z.B. Gabe Newell) von Microsoft kamen.
3.1
Besondere Merkmale der Half-Life-Engine
Skeletal Animation System Ein System zur realistischen und detaillieren Darstellung der Modelle mit Hilfe von Skelett-Strukturen, die von
Polygone umgeben sind. Werden die Kochen bewegt, so verformen sich
auch die Polygon-Netze [siehe Abb. 3.2]. Die Berechnung der Modelle erfolgt also zur Laufzeit und bringt damit Größere Flexibilität und
auch eine wesentlich höhere Anzahl von Polygonen(6000+) als bei den
bisherigen Engines(600).
Rendering Das Rendering System der Quake Engine wurde auf eine 16bit Farbtiefe erweitert. Außerdem wurden Farbige Lichteffekte hinzugefügt.
Monster AI Das Entwickler Team hat versucht, durch verschiedene und
komplexere Computer-Intelligenztypen, die miteinander agieren können,
die vermeintliche Intelligenz der Gegner zu steigern.
Decal System Ein System zur Änderung der Texturen von Oberflächen
zur Laufzeit. Damit können zum Beispiel Einschusslöcher in Wänden
dargestellt werden.
Real-Time DSP 3 Zur digitalen Audioverarbeitung, damit kann in Echtzeit
ein Klang in der 3D-Welt berechnet werden. So klingen Schüsse in einem
Raum aus Metall ganz anderes als in einem Raum aus Holz, weil Hall
und Entfernung usw. mit einberechnet werden.
1
Schnittstelle von Microsoft zur Grafik-Programmierung.
Obwohl die zugrunde liegende Quake Engine auch unter Linux läuft.
3
Digital Sound Prozessor.
2
KAPITEL 3. HALF-LIFE
8
Abbildung 3.2: Skeletal Animation System
DLL
4
Modularer ausführbarer Code. Dadurch werden Geschwindigkeitsvorteile gegenüber den Quake-Skriptsprachen5 erzielt.
Direct X Durch die Microsoft-Schnittstelle können auch Grafikkarten, die
kein Open-GL unterstützen für die 3D-Darstellung verwendet werden.
Singel/Multiplayer-Sourcen Die Sourcen von Half-Life sind in den Multiplayer- und Singelplayer-Code unterteilt. Beides ist als SDK6 frei verfügbar.
Binaries der 3D-Engine Diese sind auf Grund der Microsoft-Erweiterungen
nur unter Microsoft Windows lauffähig.
4
DLL (Dynamic Link Library): Ermöglicht einem Prozess eine Funktion zu benutzen
die nicht zu seinem Ausführbaren Code gehört.
5
Die Quake-Engines verwenden eine spezielle Skriptsprache die zur Laufzeit interpretiert wird.
6
Software Development Kit
KAPITEL 3. HALF-LIFE
3.2
9
Die Half-Life Welt
Wie im Kapitel Modellierung der 3D-Welt“ [siehe Kap. 2.3] schon beschrie”
ben wurde, erzeugen die 3D-Engines aus einem Modell zur Laufzeit die jeweilige Ansicht des Spielers, um so die Möglichkeit zu schaffen, die Welt
aus jeglichem Blickwinkel betrachten zu können. Darüber hinaus verwaltet
die 3D-Engine die verschiedenen Objekte, deren Eigenschaften und die Interaktion untereinander. In der Half-Life Welt gibt es verschiedene Arten
von Objekten, deren Positionen und Bewegungen durch Vektoren beschrieben werden. Die eigentliche Welt, im Spiel als Level bezeichnet, wird in einer
dreidimensionalen Karte in Form eines Binary Space Partitioning Baums gespeichert [siehe Kap. 3.2.4]. Ob zwei Objekte sich berühren, wird durch eine
Kollisionserkennung mit Boundingboxen [siehe Kap. 3.2.5] überprüft.
3.2.1
Objekte
Die Half-Life Welt besteht aus zwei Arten von Objekten:
• Solids (Wände, Decken, ...)
• Entities
– Point-based (statisch)
– Brush-based (dynamisch)
Die Solids sind feste Objekte wie Wände oder Decken, alle Objekte, die eine
statische Position haben und keinerlei Funktionen erfüllen. Die Level Grundstruktur besteht hauptsächlich aus Solids, also einem Boden, den Wänden
und einer Decke.
Bei den Entities wird noch einmal in zwei Arten unterschieden. Einmal die
Point-based Entities, deren Positionen durch die Karte der Welt fest vorgegebenen sind, z.B. eine Lampe die im Raum unter der Decke hängt und
flackert. Und den Brush-based Entities welche keine feste Position haben, wie
z.B. Waffen, die im Level herumliegen, aufgenommen, benutzt und an anderer Stelle wieder abgelegt werden können. Durch die Half-Life Engine wird
die Maximale Anzahl von Entities7 auf 900 begrenzt [siehe List. 4.4].
7
Point- und Brush-based Entities zusammen.
KAPITEL 3. HALF-LIFE
3.2.2
10
Vektoren
Um die Entities zu positionieren und zu bewegen, werden Vektoren verwendet. Der Ursprungsvektor (0.0, 0.0, 0.0) ist auch zugleich der Ursprung
des Koordinatensystems der Karte eines Levels. Ein Vektor besteht aus drei
Gleitkommazahlen welche die X,Y und Z Werte angeben. Diese können einmal dazu verwendet werden, eine Position (der Punkt, auf den der Vektor
vom Ursprung aus zeigt) oder aber eine Bewegung8 (durch Richtung und
Länge des Vektors) anzugeben.
3.2.3
Map
Die Karte, die das dreidimensionale Model der Welt enthält, wird bei HalfLife Map“ genannt. Dazu werden in der Karte alle festen Positionen(Solids)
”
der Umgebung gespeichert. Desweiteren werden auch die Positionen der Pointbased Entities und die Anfangspositionen der Brush-based Entities in diesen
Karten angegeben. Da diese Daten zur Laufzeit für die Berechnung benötigt
werden, wird das Binary Space Partitioning“ [siehe Kap. 3.2.4] verwendet,
”
um einen effizienten Zugriff zu unterstützen.
Für die Erstellung und Bearbeitung dieser Karten bietet Valve Software direkt im SDK den Hammer Editor“ an. Dies ist ein grafischer Editor, in dem
”
eine dreidimensionale Welt konstruiert und entsprechende Objekte positioniert werden können. Diese so erstellten Karten können direkt mit einem
entsprechenden Tool ins benötigte bsp“-Format übersetzt werden.
”
3.2.4
Binary Space Partitioning
Das Binary Space Partitioning(BSP) bietet eine effiziente Möglichkeit, die
Lage von Objekten in einer 2D/3D Welt zueinander zu bestimmen. Der BSP
ist ein so genannter Objektraum-Algorithmus“, der mit der Aufteilung eines
”
Raumes durch Trennebenen beliebiger Orientierung arbeitet. Das BSP wird
zur Darstellung, Ortsbestimmung und auch Kollisionserkennung verwendet.
Dazu wird aus der Umgebung ein BSP Baum generiert. Da das Generieren
mit einem worst case von O(n2 ) für eine Berechnung zur Laufzeit zu langsam
ist, muss es vorher geschehen und ist somit nur für die statische Szenen
anwendbar.
8
bzw. Beschleunigung oder Gravitaion (negative Beschleunigung).
KAPITEL 3. HALF-LIFE
11
Im Folgenden wird die Erzeugung eines BSP Baum an einem Beispiel verdeutlicht:
Abbildung 3.3: BSP Beispiel(Schritt 1)
Die Szene besteht aus fünf Objekten A bis E und einen Referenzpunkt Ref9 .
Ziel ist es, die Szene so zu unterteilen, dass jedes Objekt allein in einer Region
liegt. Dazu wird als erstes eine Trennebene p1 so gelegt, dass sie die Objekte
möglichst gleichmäßig aufteilt. Wie in Abb. 3.3(links) zu sehen ist, liegen
die Objekte B,C vom Referenzpunkt aus vor p1 und A,D,E dahinter. Somit
erhält man einen Baum mit der Wurzel p1 und den Blättern B,C und A,D,E
[siehe Abb. 3.3(rechts)].
Als nächstes unterteilt man nach dem gleichen Muster die Bereiche vor und
hinter p1 wieder durch neue Trennebenen p2 und p3. Für den Baum bedeutet
das, die Blätter B,C und A,D,E durch neue Knoten p2, p3 zu ersetzen. Als
neue Blätter ergeben sich dann wieder die Objekte die vor oder hinter den
neuen Trennebenen liegen:
9
Das ist z.B. der Punkt von wo die Szene betrachtet wird.
KAPITEL 3. HALF-LIFE
12
Abbildung 3.4: BSP Beispiel(Schritt 2)
Im letzten Schritt braucht man dann nur noch die Objekte A und E durch die
Ebene p4 trennen. Damit ist der BSP-Baum für die gegebene Szene erstellt:
Abbildung 3.5: BSP Beispiel(Schritt 3)
Will man jetzt z.B. überprüfen, welche Objekte für eine Kollision beim Referenzpunkt in Frage kommen, muss man nur den Baum entlang gehen. Der
Referenzpunkt liegt vor p1, also kommen wir zum Knoten p2. Da der Referenzpunkt auch vor p2 liegt, gelangen wir zum Blatt C. Somit ist das einzige
Objekt, mit dem eine Kollision stattfinden könnte, das Objekt C.
KAPITEL 3. HALF-LIFE
3.2.5
13
Kollisionserkennung
Für die Kollisionserkennung werden bei der Half-Life Engine Bounding-Boxen
verwendet. Das bedeutet, dass anstelle der 3D-Objekte nur eine quaderförmige Hülle, welche die Objekte komplett einschließt[siehe Abb.3.6], zur Kollisionserkennung verwendet wird. Dies erleichtert die Berechnungen, da nur noch
überprüft werden muss, ob sich die Kanten zweier Bounding-Boxen schneiden, um eine Kollision festzustellen. Der Nachteil ist, dass dabei schon zwei
Objekte durch ihre Bonding-Boxen kollidieren können, obwohl die Objekte
selbst sich noch gar nicht berühren würden.
Abbildung 3.6: Bounding-Box
Die Bounding-Boxen sind an den Achsen ausgerichtet und können auch nicht
gedreht werden, wodurch die Ebenen aller Boxen immer parallel zu den
Achsen sind, was ein Verkeilen der Boxen verhindert und sicherstellt, dass
Objekte, die sich z.B. in eine Ecke bewegen, diese auch wieder verlassen
können[siehe Abb.3.7].
Abbildung 3.7: Achsen-Ausrichtung
KAPITEL 3. HALF-LIFE
3.3
14
Programmstruktur
Die Half-Life Programmstruktur kann aufgeteilt werden in drei Hauptbestandteile. Die eigentliche Engine, der Server-Teil und die Client-UI [siehe
Abb. 3.8]. Da Valve Software von Anfang an stark auf die Möglichkeit gesetzt
hat, Abänderungen, so genannte Mods [siehe Kap. 3.4] zuzulassen, wurden
der Server- und Client-Teil als DLL implementiert. So können auf einfache
Art Erweiterungen oder Änderungen geschrieben werden, ohne etwas an der
Engine ändern zu müssen.
Abbildung 3.8: Programmstruktur
Beim Spielstart ruft die Engine in der Server DLL eine Funktion GiveFnptrsToDll() auf, der sie die Möglichkeiten, die in der Engine zur Verfügung
stehen, übergibt. Dann stellt die Engine eine Anfrage an eine Funktion in
der Server DLL, die der Engine, mitteilt welche Funktionen in der Server
DLL zur Verfügung stehen. Dies geschieht durch die Funktion GetEntityAPI(). Somit wissen beide Programmteile, wie sie miteinander kommunizieren
können, und die einzige Grundlage dafür ist, dass die beiden genannten Funktionen zur Initialisierung bereit stehen. Auf die Art wird auch die Client DLL
initialisiert und das Spiel kann mit GameDLLInit() gestartet werden.
KAPITEL 3. HALF-LIFE
15
• Engine - hl.exe
Die hl.exe“ enthält die 3D-Engine.
”
• Server - hl.dll (bzw. mp.dll)
Die Server DLL“ steuern die Entities (Monster, Waffen, ...).
”
• Client - cl dll.dll
Die Client DLL“ beinhaltet das gesamte User-Interface.
”
Der Programmcode ist in C++ geschrieben. Und die Objektorientierte Programmierung fördert die Übersichtlichkeit des Quellcodes. Aus dem Quellcode sieht man z.B. das alle Objekte von CBaseEntity 10 abstammen.
Für den Server und Client Teil gibt es im Anhang A und auf den Projektgruppenseiten auch noch Klassendiagramme, welche die Vererbung aufzeigen.
3.4
Modifikationen
Modifikationen (kurz Mod´s genannt) sind Änderungen, die am Spielablauf
vorgenommen werden, z.B. an:
• Waffen
• Monstern
• GUI
• Regeln
• ...
Eine der wohl bekanntesten Modifikationen, welche aus Half-Life hervorgegangen ist, ist Counter-Strike [siehe Abb. 3.9]. Bei diesem Mod wurde der
Spielablauf so geändert, dass man in zwei Teams gegeneinander spielt. Das
eine Team übernimmt die Rolle der Polizei, und das andere die Rolle der
Terroristen. Außerdem ist es rundenbasiert, sobald alle Spieler eines Teams
tot sind, gewinnt das andere Team. Aber nicht nur so etwas ist möglich, man
kann auch so starke Änderungen vornehmen, dass aus dem First Person
”
Shooter“ ein Autorenspiel wird.
10
Zu finden in cbase.cpp
KAPITEL 3. HALF-LIFE
16
Abbildung 3.9: Counter-Strike
3.4.1
Entwicklungsumgebung
Um nun solche Modifikationen am Quellcode vornehmen zu können, benötigt
man als Entwicklungsumgebung:
• SDK 2.3 (Standart oder Full)
• Half-Life 1.1.0.0
• C++ Compiler (der DLL´s erstellen kann, die mit denen von Microsoft
Visual C++ kompatibel sind, z.B. MingW32, MSVC++ 6.0, ...)
Dabei enthält das SDK den gesamten Quellcode und einige Tools, die zur Entwicklung benötigt werden. Dieses SDK gibt es von Valve in zwei Versionen,
einmal der Standart-Version, in der nur der Quellcode für die MultiplayerVariante des Spiels enthalten ist, und einmal in der Full-Version, in welcher
auch die Singelplayersourcen mit enthalten sind. Neben dem SDK, was frei
verfügbar ist, wird auch noch eine Version von Half-Life benötigt, damit man
die 3D-Engine zur Verfügung hat, und so auch seine Modifikationen testen
kann. Um die Änderungen vorzunehmen benötigt man auch noch einen C++
Compiler. Hier empfiehlt sich die Verwendung von Mircosoft Visual C++,
da hierfür im SDK alle Projektdateien enthalten sind.
KAPITEL 3. HALF-LIFE
3.4.2
17
Beispiel: Geschwindigkeit der RPG
Eine einfache Modifikation stellt z.B. das Verändern der Geschwindigkeit einer abgefeuerten Rakete dar. Dazu muss einfach im Quellcode in der Rpg.cpp
der entsprechende Geschwindigkeits-Vektor auf einen niedrigeren Wert gesetzt werden.
1
pev−>velocity=pev−>velocity ∗ 1 0 0 0 ;
Listing 3.1: Orginal: Rpg.cpp (in FollowThink)
Somit wird die Rakete nach dem Abfeuern nicht mehr wie sonst auf das
1000-fache [siehe List. 3.1] sondern nur noch auf das 10-fache [siehe List. 3.2]
beschleunigt.
1
pev−>velocity=pev−>velocity ∗ 1 0 ;
Listing 3.2: Änderung: Rpg.cpp (in FollowThink)
3.4.3
Beispiel: DropXP
Eine weitere einfache Modifikation kann in der Player.cpp vorgenommen werden. Ziel ist es, beim Ablegen eines Objektes, die Position zu beeinflussen, wo
das Objekt abgelegt wird. Dies erreicht man, indem man z.B. beim Ablegen
von Waffen den Aufruf der Create-Funktion der entsprechenden Entity so
abändert, dass sie an bestimmten Koordinaten erzeugt wird.
1
CWeaponBox ∗ pWeaponBox = ( CWeaponBox ∗ ) CBaseEntity : : ←Create ( . . . , Koordinaten , . . . ) ;
Listing 3.3: Player.cpp (in DropPlayerItem)
Normalerweise wird die Waffenbox beim Ablegen einer Waffe immer direkt
vor dem Spieler erzeugt. Diese Koordinaten in der Create-Funktion [siehe
List. 3.3] der Waffenbox können aber durch die Angabe von festen Koordinaten ersetzt werden. Die Waffenbox wird dann immer an dieser, durch die
festen Koordinaten bestimmten Stelle erzeugt.
Kapitel 4
Bot’s
Da Half-Life, im Gegensatz z.B. zu Quake oder Unreal, von Haus aus keine
Schnittstelle für die Unterstützung von Bot’s bietet, muss die Einbindung
eines Bot’s durch einen Trick erfolgen:
• Einbettung des Bot’s in ein Mod.
• DLL’s ausnutzen, um eine Bot.dll zwischen die Engine und den Server
(hl.dll) zu setzen.
Welche der beiden Methoden man wählt, sollte ganz vom Einsatzgebiet
abhängig sein. So kann ein Bot in einem Mod recht einfach realisiert werden, jedoch ist der Bot dann auch an dieses Mod gebunden. Hingegen kann
ein dazwischen gesetzter“ Bot auch in verschiedene Spiele eingebunden wer”
den, jedoch ist dann der Aufwand höher. Die Prinzipielle Vorgehensweise
zum Erstellen und Steuern eines Bot’s im Spiel ist jedoch gleich.
4.1
4.1.1
Bot’s erstellen und kontrollieren
Generierung
Um einen Bot in ein laufendes Spiel zu bringen, kann einfach die Funktion CreateFakeClient verwendet werden, welche einen virtuellen Clienten erzeugt. Dieser virtuelle Client wird dann von der Engine wie der Client des
menschlicher Spieler behandelt.
18
KAPITEL 4. BOT’S
1
2
3
4
19
BotEnt=g_engfuncs . pfnCreateFakeClient ( ” Bot ” ) ;
...
ClientConnect ( BotEnt , ”BotName” , ” 1 2 7 . 0 . 0 . 1 ” , ptr ) ;
ClientPutInServer ( BotEnt ) ;
Listing 4.1: Bot-Generieung
Dazu wird als erstes die Funktion CreateFakeClient [List. 4.1, Zeile 1] der
Engine-Funktionen aufgerufen. Dann verbindet man den Virtuellen Clienten
mit ClientConnect [Zeile 3] zum Server, was dem Hinzukommen eines Netzwerkspielers entspricht. Und schließlich wird mit ClientPutInServer [Zeile
4]der Bot dann zum Spiel hinzugefügt.
4.1.2
Steuerung
Da der Bot wie ein normaler Spieler gehandhabt wird, kann er auch genauso
gesteuert werden. Dies geschieht über die Engine-Funktion RunPlayerMove.
1
pfnRunPlayerMove ( BotEntitie , BlickRichtung , ←VorwärtsGeschwindigkeit , RechtsGeschwindigkeit ,
HochGeschschwindiskeit , Taste , Impuls , Dauer ) ;
←-
Listing 4.2: Bot-Steuerung
Bei dem Aufruf dieser Funktion wird der Engine vom Server mitgeteilt, in
welche Richtung der Spieler schaut, wohin er geht, ob er eine Taste gedrückt
hat, einen Impuls1 ausgelöst hat und wie lange diese Anweisung von der
Engine für den betreffenden Spieler ausgeführt werden soll [List. 4.2].
4.1.3
Wahrnehmung
Um zu Ermitteln, was der Bot im Spiel sehen kann, gibt es viele mögliche
Umsetzungen. Da durch die Änderungen am Code auch die Möglichkeit zur
Verfügung steht, einfach alle Positionen der Gegner dem Bot direkt mitzuteilen, egal, ob er sie sehen kann oder nicht, muss man selbst das Sichtfeld
des Bot’s bestimmen:
1
Z.B. das Einschalten der Taschenlampe.
KAPITEL 4. BOT’S
1
2
3
4
5
6
7
f or ( i = 1 ; i <=gpGlobals−>maxClients ; i++)
{
edict_t ∗ pPlayer = INDEXENT ( i ) ;
vec2LOS = ( pPlayer−>v . origin { pEdict−>v . origin ) . ←Make2D ( ) ;
...
flDot = Dotproduct ( vec2LOS , gpGlobals−>v . forward . ←Make2D ( ) ) ;
i f ( flDot > 0 . 5 0 ) {
//im S i c h t f e l d
9
11
12
13
14
20
UTIL_TraceLine { . . . }
}
else
{ ...}
// Line zum Z i e l
// a u s s e r h a l b d e s S i c h t f e l d s
}
Listing 4.3: Bot-Sicht
In der Schleife[siehe List. 4.3] wird für alle Gegner geprüft, ob sie im Sichtfeld
eines Bot’s sind. Dazu wird der Vektor, der sich aus der Differenz der Koordinaten des Bot´s und seines Gegners ergibt, ins Zweidimensionale übertragen
[Zeile 4]. Würde man die Szene von oben betrachten, wäre der entstehende Vektor VA die direkte Verbindung zwischen dem Bot und seinem Gegner. Dann wird auch der Richtungsvektor VBot , welcher die Blickrichtung des
Bot´s angibt, ins Zweidimensionale übertragen. So hat man jetzt zwei Vektoren [siehe Abb. 4.1] und je nachdem, wie groß der Winkel zwischen ihnen ist,
kann man bestimmen, ob der Gegner noch im Gesichtsfeld liegt oder nicht.
Dazu wird einfach das Kreuzprodukt der Vektoren gebildet [Zeile 6]. Das
Kreuzprodukt beschreibt die Fläche zwischen den beiden Vektoren. Ist diese
klein genug, liegen die Vektoren auch nahe beieinander. Ist das Kreuzprodukt
kleiner 0.5, entspricht das einem Sichtfeld von 120 Grad. Ist bestimmt, ob
der Gegner überhaupt im Sichtfeld liegt, so wird eine Linie vom Bot bis zum
Gegner gezogen. Trifft die Linie auf keine Hindernisse, so kann der Bot den
Gegner sehen.
KAPITEL 4. BOT’S
21
Abbildung 4.1: Bot-Wahrnehmung
4.1.4
Beschränkung
Da der Bot mit FakeClient als virtueller Client erzeugt wird, zählt der Bot
auch wie ein richtiger Spieler und unterliegt somit auch denselben Beschränkungen. Ein Auszug aus den Engine-Headerdatein [siehe List. 4.4] zeigt, dass
sich maximal 32 Spieler an ein Spiel verbinden dürfen, und somit auch nur
32 Bot’s erzeugt werden können. Aber was ist, wenn 32 Agenten nicht genug
sind? So wäre für unser Projekt, ein Multiagentensystem zu realisieren, eine
wesentlich höhere Anzahl von Bot’s wünschenswert. Da ergeben sich dann
zwei Alternativen:
KAPITEL 4. BOT’S
22
Bot als eigene Entity Hier hätte man keine Einschränkungen, da man alle
Gegebenheiten der Entity selbst bestimmen kann. Jedoch ergibt sich
hierbei ein erheblich größer Programmieraufwand, weil man alles, was
einem durch die Spielersteuerung beim FakeClient vorgegeben ist, neu
implementieren muss.
Bot als Monster Es würden sich kleine Einschränkungen durch das Erben
von CMonster ergeben, wie z.B. begrenzte Rechenzeiten zum Überlegen. Ein Monster bekommt von der Engine eine geringere Rechenzeit
zum Nachdenken“ als ein Client. Dafür könnte man auf viele Funk”
tionen der Monster zurückgreifen, und muß nicht alles neu implementieren.
1
2
#define MAX_CLIENTS 3 2
#define MAX_EDICTS 9 0 0
Listing 4.4: Engine-Header(common/com model.h)
4.2
Bot’s in Modifikationen
Wie schon erwähnt kann man einen Bot in einer Modifikation implementieren. Ob man alles selbst implementiert, den Bot von CMonster erben lässt,
oder den FakeClient verwendet, ist dabei unerheblich. Wichtig ist, dass man
bei dieser Methode an seine eigene Modifikation gebunden ist, und deshalb
ein entwickeltes Multiagentensystem nicht in einer anderen Umgebung getestet werden kann. Als Beispiel für einen Bot in einer Modifikation kann man
die im Kapitel Bot’s erstellen und kontrollieren“ [siehe Kap. 4.1] beschrei”
benden Kommandos in den Sourcecode des SDK einfügen. Da diese Methode
keine weiteren Kenntnisse erfordert und für die Zwecke der Projektgruppe
ungeeignet scheint, werde ich hier nicht weiter darauf eingehen.
4.3
Bot’s in Proxy-DLL’s
Verwendet man nun eine Proxy-DLL, so macht man sich zu Nutzen, dass
die Programmteile über die DLL-Aufrufe kommunizieren. Das im Kapitel
Programmstruktur“ [siehe Kap. 3.3] beschriebenen Verfahren, wird mit einer
”
neuen Proxy-DLL erweitert, welche den Bot enthält [siehe Abb. 4.2].
KAPITEL 4. BOT’S
23
Abbildung 4.2: Bot-Proxy-Dll
Der Aufruf der Funktion GiveFnptrsToDll() wird jetzt anstelle von der ServerDLL von der neu eingefügten Proxy-DLL entgegengenommen. Diese erhält
hierdurch die Engine Funktionen die zur Verfügung stehen, und teilt sie durch
einen weiteren Aufruf der GiveFnptrsToDll() Funktion der Server-DLL mit.
Als nächstes fragt die Engine durch den Funktionsaufruf von GetEntityAPI() die Proxy-DLL nach den von der Server-DLL zur Verfügung gestellten
Funktionen. Da die Proxy-DLL diese noch nicht kennt, stellt sie die GetEntityAPI() Anfrage an die richtige Server-DLL und kann dann der Engine die
Rückgabewerte der echten Server-DLL mitteilen. Somit ist die Initialisierung
der DLL’s abgeschlossen. Da jetzt alle Kommunikationen zwischen Engine
und Server-DLL über die Proxy-DLL ablaufen, kann diese somit alles beeinflussen was zwischen den beiden Programmteilen ausgetauscht wird. So kann
dann auch die Initialisierung des Bot’s [siehe Kap. 4.1] geschehen, so wie die
Steuerung oder jegliche andere Änderung.
Kapitel 5
Vergleichende Darstellung
Um nun die Vor- und Nachteile der einzelnen, in unserer Projektgruppe untersuchten 3D-Engines aufzuzeigen, sind die Hauptmerkmale in der folgenden Tabelle zusammengefasst. Auf die Modifizierbarkeit der Engines wird im
Fazit näher eingegangen, weil sie die subjektive Bewertung unserer Projektgruppe wiederspiegelt.
5.1
Tabelle
24
KAPITEL 5. VERGLEICHENDE DARSTELLUNG
5.2
25
Fazit
Wie schon aus der Tabelle ersichtlich ist, unterscheiden sich die 3D-Engines
in ihren Hauptmerkmalen nur unwesentlich. Für Half-Life spricht die Verwendung von DLL’s, was einen Geschwindigkeitsvorteil gegenüber den VirtuellenMaschinen von Unreal und Quake bringt. Außerdem hat man so den Vorteil das man Bot’s über die Proxy-DLL-Methode einfügen kann. Für Quake
spricht hingegen die Möglichkeit mehr als 32 Bot’s zu verwenden, was gerade für unsere Projektgruppe von belang ist. Da für die Unreal-Engine kein
wesentlicher Grund spricht, und auch die zur Verfügung stehende Literatur/Internetartikel nicht unseren Erwartungen entsprechen, sollten wir von
der Verwendug absehen.
Gerade weil Half-Life auf den Quake-Engines basiert, ergibt sich kein großer
Unterschied. Da jedoch die schon angesprochenden Vorteile der DLL-Architektur
von Half-Life, und der Portierung nach C++ eine einfachere und übersichtlichere objektorientiert Programmierung erlauben, sollte für unsere Projektgruppe Half-Life als 3D-Engine die beste Basis liefern.
26
ANHANG A. KLASSENDIAGRAMME
Anhang A
Klassendiagramme
A.1
Server
27
ANHANG A. KLASSENDIAGRAMME
28
ANHANG A. KLASSENDIAGRAMME
29
ANHANG A. KLASSENDIAGRAMME
A.2
Client
30
ANHANG A. KLASSENDIAGRAMME
31
ANHANG A. KLASSENDIAGRAMME
32
Literaturverzeichnis
[PHS] Half-Life FAQ, Steve Cook,
http://www.planethalflife.com/hlsdk2/sdk2 articles.htm
[PHP] Half-Life programming,
http://www.planethalflife.com/hlprogramming/tutorials.asp
[RSC] Gamedesign and programming resources,
http://www.resourcecode.de
[PHB] Botman´s Homepage, http://www.planethalflife.com/botman/
33