Perfekte KI

Diesen Monat veröffentliche ich den ersten Artikel in einer Reihe, die von fortgeschrittener KI handeln wird. Wenn Sie denken, dass “Perfekte KI” zu schön klingt, um wahr zu sein, hören Sie sich an, was ich plane: ein Feind, der die Position des Spielers kennt und weiß, wie er auf kürzestem Weg dorthin gelangt:

Es ist klar, dass jedes Spiel individuelle Anforderungen an die KI stellt, daher werde ich die Diskussion auf einem Anfänger – Fortgeschrittenen Niveau belassen, damit jeder den hier präsentierten Code modifizieren und neue Features einfügen kann. Vergessen Sie auch nicht den “Acknex User Magazine” Thread auf dem Forum, posten Sie Ihre Ideen dort und einige werden vielleicht wahr. Übrigens sind alle Artikel dieses Magazins auf dem Forum nachgefragt worden.

Also, schauen wir mal, was wir diesen Monat lernen können. Ich habe in früheren Ausgaben schon einiges über KI geschrieben, meistens mit der “Trial and Error”-Methode. Der Feind versucht den Spieler zu erreichen, indem er einfach auf ihn zu geht. Wenn ein Hindernis auftritt, dreht er sich nach links oder rechts, bewegt sich ein Stück in die neue Richtung und versucht dann, erneut den Spieler zu erreichen.

Wenn Sie denken, dass diese KI primitiv ist, dann haben Sie recht! Dennoch erledigt sie ihren Job ganz gut, wenn die Hindernisse klein sind und sie ist sehr leicht zu programmieren. Fortgeschrittenere KI braucht Knoten oder Wegpunkte (ich werde diesen Ausdruck nicht verwenden, damit er nicht mit den Wegpunkten eines Pfades in WED verwechselt wird). Ein Knoten (engl. Node) ist ein interessanter Punkt im Level, schauen Sie sich die Quadrate im ersten Bild an: dies sind die Knoten, die ich für dieses Labyrinth eingefügt habe.

Jeder Knoten sollte mindestens einen Nachbarknoten zum reden haben, also fügen Sie soviele in Ihr Level ein, wie Sie brauchen, aber verwenden Sie keine unnötigen Knoten, denn dies wird Ihr Spiel verlangsamen. Hier ist ein Beispiel für schlechte Plazierung von Knoten:

Wie Sie sehen ist “1” isoliert, kann keine weiteren Knoten sehen. Dasselbe gilt für “3” und “8”, sie können sich gegenseitig sehen, aber keiner der beiden sieht die anderen. Hier ist die korrigierte Version:

Ich habe die Knoten “9” und “10” hinzugefügt und nun können alle Knoten miteinander kommunizieren. Stellen wir uns die folgende Situation vor:

Der Feind möchte den Spieler finden, also macht er Folgendes:
- Er fragt: “Wer von euch Knoten ist nahe am Spieler und kann ihn sehen?”
- “Ich, wähle mich!”, ruft Knoten 2.
- “Soso...”, antwortet der Feind, “aber wie komme ich dorthin?”
- “Nun”, sagt Knoten 2, “ich weiß es nicht, aber ich weiß, dass ich Knoten 10 sehen kann.”
- “Na schön”, sagt der Feind, “Knoten 10, was siehst Du?”
- “Ich sehe Knoten 5”, antwortet Knoten 10.
- “Und Du, Knoten 5?”, fragt der Feind.
- “Ich sehe die Knoten 4 und 7.”
- “Auch ich sehe Knoten 7! Nun weiß ich, wie ich zum Spieler komme”, sagt der Feind, während er sich seine dreckigen Hände reibt. “Ich muß nur zu Knoten 7 gehen, dann zu Knoten 5, 10, 2 und dann werde ich den Spieler finden und töten!”

So funktioniert fortgeschrittene Wegsuche. Es gibt eine Reihe von bekannten Algorithmen dafür: A*, Dijkstra, Breitensuche, etc. Ich werde eine Kombination der ersten beiden benutzen.

Nun, da Sie Informationen über KI haben, schauen wir uns den Code in dem Artikel dieses Monats an:
- Ein Netzwerk von Knoten
- Nur die Knoten nahe am Spieler nutzen wertvolle Rechenressourcen
- Die Knoten nahe am Spieler, die ihn sehen werden ermittelt
- Der nächste Knoten zum Spieler, der ihn sehen kann ist bekannt, ebenso wie sein Abstand zum Spieler

Ich würde sagen, das ist ein guter Anfang, schauen wir uns also den Code an, der dies alles möglich macht. Ich fange mit den Arrays an, die ich in der Demo benutzen will:

var node_distance[50];
var see_player[50];
var nodex[50];
var nodey[50];

Node_distance[50] speichert die Distanz eines bestimmten Knotens zum Spieler, die Einträge sind node_distance[0] bis node_distance[49], aber wir werden aus Gründen der Einfachheit das erste Element nicht nutzen, also können nur 49 Knoten darauf zugreifen. Mein Demo Level benutzt 30 Knoten, aber wenn Sie mehr brauchen, vergrößeren Sie einfach das Array oben.

See_player[50] wird auf 1 gesetzt, wenn der Knoten den Spieler sehen kann und 0, wenn dies nicht der Fall ist. Schauen Sie sich das Bild oben noch einmal an: Knoten 2 kann den Spieler sehen, also ist see_player[2] = 1 und Knoten 10 kann ihn nicht sehen, daher ist see_player[10] = 0.

Nodex[50] und Nodey[50] speichern die Koordinaten der Knoten in x und y Richtung; diese brauchen wir, denn wenn wir möchten, dass der Feind zu Knoten 5 geht (z.B.), können wir die Koordinaten dieses Knotens im Array finden.

Nun ist es Zeit für einen Text und ein Panel:

text ai_txt // displays the texts on the screen
{
font = ai_font;
pos_x = 0;
pos_y = 0;
string = "Target node:\nD.to target:";
flags = visible;
}

panel ai_pan // displays the numerical values on the screen
{
pos_x = 0;
pos_y = 0;
layer = 10;
digits = 240, 0, 3, ai_font, 1, target_node;
digits = 240, 22, 3, ai_font, 1, closest_distance;
flags = overlay, refresh, visible;
}

Ich verwende ai_txt für zwei Textzeilen auf dem Bildschirm und ai_pan für zwei Werte. Die “Target Node” ist der Knoten, der dem Spieler am nächsten ist und “D. to target” ist seine Entfernung zum Spieler. Sehen wir uns nun die Main Funktion an:

function main()
{
fps_max = 60;
clip_size = 0;
level_load(level1_wmb);
wait (3);
camera.z = 2400;
camera.tilt = -90;

Wir beschränken die Framerate auf 60 fps, stellen sicher, dass auch alle Polygone der Models angezeigt werden und laden das Level. Wir warten, bis das geschehen ist und stellen dann sicher, dass wir eine gute Sicht auf die Karte bekommen, indem wir eine günstige Kameraposition auswählen.

while (1)
{
index %= 49; // limit the "index" value
index += 1; // from 1 to 49

Die While-Schleife bestimmt den nächsten Knoten, der den Spieler sehen kann. Wir benutzen eine Variable namens index als Zählvariable; die Werte reichen von 1 bis 49, denn bis zu 49 Knoten können benutzt werden, wenn die Arrays alle 50 Elemente haben.

if ((node_distance[index] < closest_distance) && (see_player[index] == 1))

Wenn die Distanz eines neuen Knotens zum Spieler kleiner ist als die vorher gespeicherte Distanz und wir einen Knoten prüfen, der den Spieler sehen kann (see_player[index] = 1), haben wir einen neuen Gewinner! Dies ist der neue Zielknoten für den Feind!

{
closest_distance = node_distance[index];
target_node = index;
}

Wenn das nicht stimmt, benutzen wir den vorherigen Sieger, der alte Knoten ist immer noch der nächste zum Spieler.

else // haven't found a new winner?
{
closest_distance = node_distance[target_node];
}
wait (1);
}
}

Für den Spieler selbst benutzen wir ein Model, das “walk” und “stand” Animationen besitzt, sehen wir uns den Code an:

action player1
{
player = me; // I'm the player
while (1)
{
my.pan += 4 * (key_cul - key_cur) * time; // rotates with the left / right arrow keys
player_speed.x = 10 * (key_cuu - key_cud) * time; // moves forward / backward with the up / down arrow keys
if (key_cuu + key_cud > 0) // if the player is walking
{
ent_cycle("walk", my.skill46); // play "walk" frames animation
my.skill46 += 7 * time; // "walk" animation speed
my.skill46 %= 100; // loop animation
}
else // the player is standing
{
ent_cycle("idle", my.skill46); // play "stand" frames animation
my.skill46 += 2 * time; // "stand" animation speed
my.skill46 %= 100; // loop animation
}
move_mode = ignore_passable + glide;
ent_move(player_speed, nullvector);
wait (1);
}
}

Der Spieler dreht sich, wenn Sie die Pfeiltasten links oder rechts drücken und bewegt sich vor und zurück mit den Pfeiltasten oben und unten. Ändern Sie die Werte “4” und “10”, wenn Sie die Geschwindigkeit ändern wollen, mit der der Spieler sich dreht bzw. läuft. Wenn der Spieler geht, spielen wir seine “walk” Animation, ansonsten die “stand” Animation. Der Spieler bewegt sich und gleitet an Mauern entlang, wenn er welche trifft.

Der letzte Teil des Codes gehört zu den Knoten:

action node // using 30 nodes in this demo
{
my.skill47 = 1234;
my.passable = on;
my.skin = 1; // red
while (player == null) {wait (1);}
node_number += 1; // get a unique number
my.skill48 = node_number; // and store it in skill48
nodex[my.skill48] = my.x; // store x and y
nodey[my.skill48] = my.y; // for this node

Wir haben einen seltsamen Wert für Skill47 gewählt, um den Knoten eine einzigartige Id zu geben. Knoten sind passierbar, sie sollten weder den Spieler noch die Feinde blockieren und dann wählen wir die erste Skin für den Knoten (rot). Das Knoten Model hat drei Skind, rot grün und blau. Rot ist der Standardwert, grün wird für Knoten verwendet, die nahe am Spieler sind und blau sind die Knoten, die den Spieler “sehen” können.

Wir warten bis der Spieler im Level ist und weisen dann jedem Knoten eine einzigartige Zahl zu, die in Skill48 gespeichert wird. Vielleicht fragen Sie sich, wie dieses System funktioniert, daher hier eine detaillierte Erklärung: alle Entities im Level werden nacheinander geladen. Die erste Knoten Entity, die im Level erscheint addiert 1 zu node_number und speichert diesen Wert (Eins) in skill48. Der zweite Knoten addiert wieder 1 dazu und speichert das Ergebnis (Zwei) auch in Skill48. Dieser Prozeß geht weiter, bis alle Knoten Entities geladen sind. Wenn dies geschehen ist, hat jeder Knoten seine eigene Nummer in skill48 gespeichert.

Die letzten zwei Zeilen speichern die Position der Knoten (x und y) im Level.

while (1)
{
node_distance[my.skill48] = vec_dist(player.x, my.x);

Ich habe Ihnen erzählt, dass node_distance die Entfernung eines Knotens zum Spieler speichert, nicht wahr? Die Codezeile oben erreicht genau das. Wenn der Spieler näher als 500 Quants am Knoten ist

if (node_distance[my.skill48] < 500)
{
trace_mode = ignore_me + ignore_models + ignore_passents;
if (trace (my.pos, player.pos) == 0) // if this node can "see" the player
{
my.skin = 3; // the node changes its color to blue
see_player[my.skill48] = 1; // the node can see the player
}
else
{
see_player[my.skill48] = 0; // this node can't see the player
my.skin = 2; // can't see the player? keep the green color
}
}

Dann führen wir einen “trace” vom Knoten zum Spieler aus und wenn das Ergebnis 0 ist, kann der Knoten den Spieler sehen, also setzen wir seinen Skin auf blau und setzen see_player auf 1. Kann der Knoten den Spieler nicht sehen, bleibt er grün, der Spieler ist nahe, aber der Knoten sieht ihn nicht.

else // far from the player? keep the red color
{
my.skin = 1;
}
sleep (0.1); // trace 10 times a second
}
}

Wenn der Spieler weit weg ist, behalten wir die Grunfarbe (rot) für den Knoten bei. All diese Operationen laufen 10 Mal pro Sekunde, denn die letzte Anweisung der Schleife ist sleep(0.1).

Starten wir das Projekt: öffnen Sie level1.wmp, rechnen Sie es aus und starten Sie es mit ai1.wdl:

Sie werden das Folgende sehen:

Die grünen Quadrate sind die Knoten, die näher als 500 Quants am Spieler sind. Sie können den Spieler bewegen und zusehen, wie die Farben der Knoten sich ändern. Verlassen Sie die Engine und starten Sie das Level erneut, mit der Option “-d traceplayer” wie im Bild unten:

Sie sehen das folgende Bild:

Einige der grünen Knoten sind nun blau, das sind die Knoten, die näher als 500 Quants am Spieler sind und ihn “sehen” können. Es wäre unklug, auch “trace”-Anweisungen für Knoten durchzuführen, die weit weg vom Spieler sind, oder?

Ich ermuntere Sie, noch einen oder mehr Testlevel zu erstellen und lernen, Ihr Netzwerk von Knoten darin zu plazieren. Hier ist ein schlechtes Beispiel eines korrekten Knotennetzes:

Der Feind möchte zum Spieler, also muß er den Pfad 1, 5, 3, 2 benutzen. Wenn ich den fehlenden Knoten eingefügt hätte, wäre der Weg des Feindes zum Spieler viel kürzer, nicht wahr? Vergessen Sie nicht, dass perfekte KI mit perfektem Planen des Weges beginnt.

Nächstes Mal lernen wir, wie der kürzeste Weg zwischen zwei beliebigen Knoten im Level berechnet wird: dem Startknoten (der Feind) und dem Zielknoten (dem Spieler).

Start!

Manchmal müssen wir den Spieler bei dem unterbrechen, was er gerade tut, weil wir eine nette Zwischenszene zeigen wollen. Wenn Sie sich entschieden haben, den Code für Ihr Spiel selbst zu schreiben, dann ist das kein Problem, aber was ist mit dem Rest der User, denen die den Templates treu sind?

Der Code in diesem Artikel erstellt einen Hubschrauber, der auf dem Boden steht und auf den Spieler wartet; sobald dieser nahe genug ist, startet er von selbst.

Ich mußte die gewöhnlichen Kamerasichten entfernen ohne die Templates zu ändern, also habe ich einfach eine neue View definiert:

view cutscene_view
{
layer = 15;
pos_x = 0;
pos_y = 0;
}

Die Action für den Hubschrauber kommt hier:

action chopper
{
my.passable = on;
while (vec_dist (my.x, player.x) > 150) // wait until the player has come closer than 150 quants
{
ent_cycle("fly", my.skill20); // play "fly" animation
my.skill20 += animation_speed * time;
my.skill20 %= 100; // loop the animation
if (!snd_playing(chopper_handle))
{
chopper_handle = ent_playsound (my, chopper_wav, 200);
}
wait (1);
}

Der Hubschrauber ist passierbar; wenn der Spieler weiter als 150 Quants entfernt ist, befindet er sich in seiner “fly” Animationsschleife und spielt den chopper_wav Sound ab.

cutscene_view.size_x = screen_size.x; // has the same width
cutscene_view.size_y = screen_size.y; // and height with "camera"
cutscene_view.x = -1685;
cutscene_view.y = -1240;
cutscene_view.z = 210;
cutscene_view.pan = 20;
cutscene_view.tilt = -15;
cutscene_view.roll = 0;
player.invisible = on; // hide the player
player.shadow = off; // and its shadow (if any)
camera.visible = off; // hide "camera"
cutscene_view.visible = on; // show the new view

Wenn der Spieler näher als 150 Quants ist, benutzen wir dieselbe Bildschirmgröße f+r cutscene_view, setzen eine geeignete Position und einen Winkel für die neue Kamera, verbergen den Spieler und seinen Schatten, die alte View (camera) und zeigen die Neue (cutscene_view). Ich habe diese Werte für cutscene_view gefunden, indem ich zweimal “0” drückte, um fliegen zu können, dann “D” (bzw. “F11”) für das Debugpanel gedrückt habe und auf die xyz bzw. ang Spalten geachtet habe, um die x, y, z, pan, tilt und roll Werte für das Spiel zu erhalten.

while (my.z < 1000) // wait until the chopper has reached a height of 1,000 quants
{
if (animation_speed < 10)
{
animation_speed += 0.05 * time;
}
else // start flying when animation_speed is bigger than 10
{
my.z += 10 * time;
my.x += 30 * time;
}
ent_cycle("fly", my.skill20); // play "fly" animation
my.skill20 += animation_speed * time;
my.skill20 %= 100; // loop the animation
if (!snd_playing(chopper_handle))
{
chopper_handle = ent_playsound (my, chopper_wav, 500); // the sound is louder this time
snd_tune (chopper_handle, 0, 25 * animation_speed, 0);
}

Solange der Hubschrauber die Höhe von 1000 Quants noch nicht erreicht hat, erhöht sich die Geschwindigkeit seiner Animation von 4 auf 10; wenn sie größer ist als 10, hebt der Hubschrauber ab (erhöht seine z Koordinate) und bewegt sich nach vorn (erhöht seine x Koordinate). Dieselbe “fly” Animation wie vorher wird abgespielt, nur schneller und chopper_wav wird entsprechend verändert.

vec_set(temp, my.x);
vec_sub(temp, cutscene_view.x);
vec_to_angle (cutscene_view.pan,temp); // rotate cutscene_view towards the chopper

Diese drei Codezeilen richten die cutscene_view auf den Spieler aus:

wait (1);
}
exit; // shut down the engine
}

Der Hubschrauber hat eine Höhe von über 1000 erreicht, daher beendet sich das Spiel. Sie könnten ein neues Level laden, oder vielleicht Explosionen im alten Level auslösen etc. Das einzig Wichtige ist, dass der Spieler nun in guten Händen ist (solange ich selbst nicht den Hubschrauber steuere).