Perfekte KI: "The Making Of"

Ich habe mich entschieden, diesen Monat weniger über den Code zu reden, als viel mehr darüber, wie die “Perfekte KI” funktioniert; dies soll Ihnen helfen, meinen Code an Ihre Bedürfnisse anzupassen. Testen wir zunächst die Demo; öffnen Sie level5.wmp, lassen Sie es ausrechnen und starten Sie es mit dem Skript namens ai5:

Ich würde an Ihrer Stelle anfangen zu laufen! Benutzen Sie “WASD” und die Maus um sich zu bewegen und zu feuern. Es gibt zwei Gegner, die Sie gleich zu Anfang verfolgen und ein Dritter (rechts von Ihnen), der darauf wartet, dass Sie sich ihm auf 1000 Quants nähern, ehe er auch beginnt, Sie zu attackieren. Wenn Sie auf ihn schießen, vergißt er das mit den 1000 Quants und wird Sie verfolgen.

Die Gegner werden schießen, sobald sie Sie sehen können, es sei denn, Sie sagen ihnen, dass sie etwas weniger aggressiv sein sollen, schauen wir uns die Optionen also gleich mal an:

Wir können die “Alert_dist” manipulieren und das “Gentle” Flag setzen – oder auch nicht. Wird die Alert_dist auf 0 gesetzt, beginnen alle Gegner den Spieler zu jagen, sobald das Level geladen ist, ansonsten werden sie warten, bis der Spieler auf die Distanz in Quants herangekommen ist, der durch Alert_dist gegeben wird (1000 Quants in meinem Beispiel). Wird das “Gentle”-Flag angewählt, werden die Gegner versuchen, nahe an den Spieler zu kommen, bevor sie schießen. Ist es nicht gesetzt, schießen sie auf den Spieler, sobald sie ihn sehen können; dies sorgt für mehr Realismus und Spaß.

Wie Sie sehen ist das Level eine Kombination aus Innenräumen und Außenarealen, was im Grunde egal ist, solange Sie die Knoten nur drinnen und draußen plazieren. Ich habe einmal gesagt, dass perfekte KI mit perfektem Pathfinding beginnt; dennoch sollten die Gegner in der Lage sein, den Spieler zu finden, selbst wenn die Knoten nicht besonders gut im Level plaziert wurden. In diesem Monat ist mein Level ein einziges Durcheinander – hier ist ein Beispiel:

Der Gegner möchte den Spieler finden, also sollte er den Pfad nehmen, der durch die roten Pfeile gekennzeichnet ist; allerdings können einige der Knoten einander sehen (der grüne Pfeil), aber der Gegner würde in die Wand laufen, wenn er diesem Weg folgt, denn er ist zu dick! Der Algorithmus sucht den kürzesten Weg zum Spieler, also wird er den Gegner anweisen, den Weg zu nehmen, der den grünen Pfeil beinhaltet! Mein Code in diesem Monat erlaubt es den Gegnern, an den Wänden entlang zu gleiten; falls sie mal steckenbleiben, bleiben sie stehen und suchen einen neuen Weg zum Spieler. Nun können Sie auch Knoten in Ihren Levels plazieren, ohne allzu vorsichtig sein zu müssen, aber vergessen Sie nicht, dass jeder Knoten zusätzliche Ressourcen verbraucht.

Diese Demo kann mit bis zu 100 Knoten und 40 – 50 Gegnern pro Level arbeiten. Bevor Sie jetzt denken, dass ich mit Pinocchio verwandt bin, lassen Sie mich einen Screenshot zeigen, der aufgenommen wurde, als ich den Code mit etwa 40 Gegnern testete; ich verstecke mich gerade hinter diesen Boxen, aber ich bin sicher, dass ich nicht mehr lange durchhalte.

Ich bin davon ausgegangen, dass jeder Pfad zwischen diesen 100 Knoten (falls Sie alle verwenden) maximal 50 Punkte hat, was Ok für ein normales Level ist. Falls Sie mehr Knoten, Gegner, etc. brauchen, erhöhen Sie einfach die Größe der Arrays. Nun ja, ich denke, dass 100 Knoten genug für alle sein sollten, aber was weiß ich schon? Ich bin nicht alle...

Der Algorithmus für die Perfekte KI funktioniert gut, aber kann das Spiel etwas verlangsamen. Wieviel? Meine Tests haben gezeigt, dass die find_path Funktion aus den letzten Artikel die Grenze bei etwa 400 Gegnern gleichzeitig im Level zieht. Ich kann hören, wie Sie lachen... 400 Gegner sind mehr als genug für ein einzelnes Level, aber diese 400 Gegner würden ALLE Ressourcen fressen, wenn Sie also weitere Entities, Panels, etc. in Ihrem Level haben, landen Sie bei vielleicht 50 Gegnern pro Level, was nicht allzu viel ist, wenn Sie ein Strategiespiel schreiben.

Die Lösung ist einfach: ich habe ein separates Skript geschrieben, das nur einmal vom Entwickler ausgeführt wird, nicht mehr vom Spieler. Es heißt compute.wdl und wird alle Pfade zwischen je zwei Knoten im Level berechnen und in eine Datei namens “paths.txt” schreiben (bzw. paths1.txt für Level 1, paths2.txt für Level 2 usw.)
Was gewinnen wir dadurch? Die Gegner müssen sich den korrekten Pfad nicht mehr berechnen lassen, weil dies bereits geschehen ist und die Geschwindigkeit steigt um etwa 800%. Die Mathematik überlasse ich Ihnen...

Dies ist ein kleiner Teil der paths.txt Datei:

1 999 2 1 999 3 1 999 4 1 999 5 1 999 6 3 1 999 7 8 1 999 8 1 999 9 8 1 999 10 5 1 999 11 10 5 1 999 12 13 16 1 999 13 16 1 999 14 1 999 15 16 1 999 16 1 999 17 1 999 .....

Ich habe “999” als Trennung benutzt, um file_var_read etwas schneller ausführen zu können, aber das Beispiel oben sieht ausgeschrieben etwa so aus:

1
2 1
3 1
4 1
5 1
6 3 1
7 8 1
8 1
9 8 1
10 5 1
11 10 5 1
12 13 16 1
13 16 1
14 1
15 16 1
16 1
17 1
...............

Der Pfad von 1 nach 1 geht offensichtlich durch 1; die Knoten 2, 3, 4 und 5 können 1 direkt sehen. Der Pfad von Knoten 6 zu Knoten 1 geht durch Knoten 3 usw. Alle möglichen Pfade zwischen jedem Knotenpaar sind in dieser datei gespeichert. Unser Spielskript lädt all diese Werte in ein riesiges Array namens paths und die Gegner holen sich von dort den kürzesten Pfad, wann immer sie ihn brauchen. Wenn Sie sehen möchten, wie diese Pfade in compute.wdl berechnet werden, werden Sie eine auskommentierte “wait(1);” Zeile dort finden; entfernen Sie den Kommentar und Sie werden sehen, wie find_path alle Kombinationen durchgeht.

Also zurück zum “Making of”. Wie funktioniert all dies?

Wir plazieren unsere Knoten im Level und sie erhalten automatisch eine ID. Ich hätte auch von Hand für den ersten Knoten skill1 auf 1 stzen können, für den zweiten Knoten skill1 auf 2 usw. aber ich dachte, dass meine Methode mich bei Level Designern beliebter macht. Diese Knoten scannen einander: Knoten 1 scannt die Knoten 2, 3, 4, ... , 40 (falls der Level 40 Knoten hat), Knoten 2 scannt die Knoten 1, 3, 4, ... , 40, Knoten 3 scannt die Knoten 1, 2, 4, ... , 40 usw. Wenn alle Knoten einander gescannt haben, wird eine Variable namens distances_computed auf 1 gesetzt und der eigentliche Algorithmus fürs Pathfinding kann laufen.

Aber warum scannen die Knoten einander? Sehen Sie sich das Bild an:

Angenommen Knoten 1 scannt die Knoten in seiner Umgebung (mit Hilfe der goldenen Kreise), das sind die Knoten 2, 5 und 7. Wie Sie wissen gehen die Scans durch Wände, also müssen wir eine Methode finden, die für uns feststellt, ob die Knoten einander direkt “sehen” können. Die Antwort ist leicht: wir tracen von jedem Knoten, der gescannt wurde, zurück zum scannenden Knoten, also Knoten 2 führt einen Trace zu Knoten 1 aus, Knoten 5 und Knoten 7 verfahren ebenso. Die Knoten 2 und 5 können Knoten 1 sehen, aber Knoten 7 nicht; die Funktion trace_back setzt das Array node_to_node[2,1] = 300 und node_to_node[5,1] = 340, was die entsprechenden Abstände sind. Der Wert node_to_node[7,1] bleibt auf 0 stehen, weil Knoten 7 Knoten 1 nicht sehen kann.

Soweit alles klar? Wenn alle Knoten also fertig sind, einander zu scannen, haben wir ein Array (namens node_to_node), in dem steht welche Knoten einander sehen können und die Abstände dazwischen. Was kommt jetzt?

Nun, ich habe Ihnen gesagt, dass distances_computed auf 1 gesetzt wird und der Pathfinding Algorithmus ablaufen kann; dieser ersetzt die 0 Einträge in node_to_node mit einem riesigen Wert: 999.999. Warum mache ich das? Der Algorithmus sucht den kürzesten Weg von einem Knoten zu einem anderen, also würde er sich über den Abstand 0 sehr freuen; wir allerdings wissen, dass node_to_node[x,y] = 0 in Wahrheit bedeutet, dass Knoten x und Knoten y einander nicht sehen können, also kann der Abstand zwischen ihnen sehr groß sein!

Der Algorithmus geht nun alle Knoten Knoten durch und sucht sich den kürzesten Abstand zwischen je zwei Knoten; wenn er fertig ist, steht in node_to_node[x,y] der Abstand zwischen zwei Knoten auf kürzestem Weg, selbst wenn die Knoten sich nicht sehen können. Sehen Sie sich nochmal das Bild oben an; node_to_node[1,7] wäre 700, falls node_to_node[1,2] auf 200 und node_to_node[2,7] auf 300 steht.

Jetzt kennen wir die Abstände aller Knoten im Level voneinander, aber wir haben den eigentlichen Pfad noch nicht – das erledigt die Funktion find_path. Sie ist rekursiv, die den kürzesten Weg zwischen je zwei Knoten findet.

Das Bild oben zeigt den kürzesten Weg von A nach I: ABCI mit Kosten (bzw. Abstand) von 350. Es ist klar, dass ADEC mehr “kostet” als ABC und die Funktion find_path tut genau das: sie ersetzt ADEC mit ABC, falls nötig, weil 100 + 150 < 90 + 110 + 80. Die Funktion find_path liefert die Knoten zurück, die auf dem kürzesten Weg zwischen zwei bestimmten Knoten liegen; und das wird in paths.txt festgehalten.

Es gibt nur eine Sache, die noch nicht diskutiert wurde: woher wissen wir, von welchem Knoten zu welchem wir gehen müssen? Mit anderen Worten, wie ermitteln wir den nächsten Knoten zum Spieler und zu einem gewissen Gegner? Jeder Knoten wartet bis der Spieler näher als 500 Quants herangekommen ist und dann führt er einen Trace zum Spieler aus. Falls Knoten 3 den Spieler sehen kann, setzt er see_player[3] auf 1, ansonsten auf 0. Alle Knoten, die einen Spieler zu einer bestimmten Zeit sehen können werden verglichen und der Knoten, der dem Spieler am nächsten ist, gewinnt: er wird der Zielknoten, der als Ziel für alle Gegner gesetzt wird. Auf der anderen Seite scannen alle Gegner die Knoten in ihrer Umgebung und diese tracen zurück. Der Knoten, der dem Gegner am nächsten ist und ihn sehen kann wird der Startknoten für den Gegner sein.

Ich habe den Spieler in der Demo vom Skript erstellen lassen, weil ich nicht vollte, dass er von den Knoten am Anfang des Spiels gescannt wird. Ändern Sie die Werte von player_pos[3] in ai5.wdl, wenn Sie möchten, dass er woanders startet.

So funktioniert die Perfekte KI! Ich denke, dass Sie jetzt ein brauchbares KI-System in Händen halten; es ist natürlich noch nicht vollendet, aber der KI-Teil ist fertig. Sie brauchen noch Code, damit die Gegner nicht so abgehackt um die Kurven gehen, vielleicht einige Geräusche für Schmerzen, Todesanimationen etc., aber dieser Code hat mit KI nichts zu tun. Keine Sorge, ich werde die Perfekte KI nicht aufgeben, ich habe immerhin etwa einen Monat daran gearbeitet. Posten Sie Ihre Vorschläge im Forum und wenn Sie möchten, dass ich weitere Features hinzufüge, werde ich das dann oder in naher Zukunft tun.

Simulierte Spiegel

Spiegel zu erstellen ist ein Feature, das Benutzern der “Professional”-Version der Engine vorbehalten ist; trotzdem können Sie ganz gut aussehende Spiegeleffekte auch hinbekommen, selbst wenn Sie A5 oder A6 Standard benutzen.

Wie machen wir zum Beispiel einen Effekt, der auf den Boden eines Raumes zu einem Spiegel macht? Hier ist eine Erklärung Schritt für Schritt:

1) Erstellen Sie einen großen Würfel im WED, ändern Sie Größe und Textur;

2) Höhlen Sie ihn aus und löschen Sie den Boden;

3) Speichern Sie das Level und erstellen Sie eine separate WMB Entity, die als Boden Ihres Raumes verwendet wird; geben Sie ihr die “checker1” Textur aus der standard.wad

4) Laden Sie das Level wieder und bauen Sie die Entity als Fußboeden ein.

5) Selektieren Sie den Level mit Ausnahme der Fußbodenentity und gruppieren Sie sie:

6) Duplizieren Sie den Raum und drehen Sie ihn auf den Kopf:

7) Fügen Sie mehr Möbel, etc. hinzu (normal und auf dem Kopf). Diesen Raum habe ich in meiner Demo benutzt:

8) Stellen Sie ein Spieler Model ins Level und geben Sie ihm die player1 Action. Geben Sie der Boden Entity die Action “transparent_floor”. Das wars!

Geschafft: der Spieler kann durch den transparenten Boden sehen und auf beiden Seiten sind die gleichen Dinge zu sehen! Aber was geschieht mit dem Spieler Model? Es ändert seine Position, Animationen, etc. laufend, also braucht es einigen Code!

action player1
{
player = me;
while (1)
{
camera.x = player.x - 100 * cos(player.pan);
camera.y = player.y - 100 * sin(player.pan);
camera.z = player.z + 80;
camera.pan = player.pan;
camera.tilt += 10 * mouse_force.y * time;
player.pan += 4 * (key_a - key_d) * time;
player_distance.x = 10 * (key_w - key_s) * time;
player_distance.y = 0;
player_distance.z = 0;

Die Kamera wird 100 Quants hinter dem Spieler und 80 Quants über seinem Zentrum plaziert; sie übernimmt seinen Pan und ändert den Tilt je nach der Mausbewegung nach oben und unten. Der Spieler kann seinen Pan mit “A” und “D” ändern und sich mit “W” bzw. “S” vorwärts und rückwärts bewegen.

if ((key_w == 1) || (key_s == 1)) // the player is walking
{
ent_cycle("walk", my.skill20); // play "walk" frames animation
my.skill20 += 4 * time; // "walk" animation speed
my.skill20 %= 100; // loop the animation
}
else // the player is standing
{
ent_cycle("stand", my.skill20); // play "stand" frames animation
my.skill20 += 2 * time; // "stand" animation speed
my.skill20 %= 100; // loop the animation
}
move_mode = ignore_passable;
ent_move (player_distance, nullvector);
wait (1);
}
}

Falls der Spieler läuft (“W” oder “S” sind gedrückt), wird seine “walk” Animation in einer Schleife gezeigt, ansonsten seine “stand” Animation. Der Spieler bewegt sich mit der Geschwindigkeit, die in player_distance steht und ignoriert dabei Objekte, die passierbar sind.

Hm, kein Spiegelcode hier; sehen wir uns diese Funktion an:

starter init_mirrors()
{
while (player == null) {wait (1);}
ent_create (fakeplayer_mdl, nullvector, mirror_player);
}

Diese wartet, bis die Entity des Spielers geladen ist und erstellt dann ein Model für die Reflektion des Spielers (fakeplayer_mdl) und gibt diesem die Action mirror_player:

function mirror_player
{
my.passable = on;
while (1)
{
vec_set(temp, player.x);
temp.z -= 500; // trace 500 quants below the player
trace_mode = ignore_me + ignore_passable + ignore_models + ignore_sprites + scan_texture;
trace (player.x, temp); // get tex_name
my.frame = player.frame;
my.next_frame = player.next_frame;
if (str_cmpi ("checker1", tex_name))
{
my.invisible = off; // show the fake player image
my.pan = player.pan;
my.roll = player.roll + 180; // flip it upside down
my.x = player.x;
my.y = player.y;
my.z = player.z - 60;
}
else
{
my.invisible = on;
}
wait (1);
}
}

Das Model für den gespiegelten Spieler ist passierbar; wir tracen vom “echten” Spieler aus 500 Quants nach unten, um den Namen der Bodentextur zu erhalten und setzen den gleichen frame und next_frame für die Reflektion des Spielers. Falls der trace die Textur namens “checker1” unter den Füßen des Spielers findet, wird das Model für die Spiegelung angezeigt, mit demselben pan und einem anderen Roll Winkel (180 Grad stellt das Model auf den Kopf, was uns gut genug ist). Die Reflektion hat denselben x und y Wert wie der Spieler und wird 60 Quants ihm angezeigt (spielen Sie ein wenig mit diesem Wert).

Falls trace die “checker1”-Textur nicht findet, wird das Model für die Reflektion nicht angezeigt. Auf diese Weise können Sie normale Räume haben, mit Fußböden, die nichts spiegeln. In meiner Demo kommt auch ein solcher Raum vor.

Die Action für den Fußboden ist wirklich simpel; ändern sie die “85”, um den Transparenzfaktor für den Spiegel zu ändern:

action transparent_floor
{
my.transparent = on;
my.alpha = 85;
}

Wenn Sie auch Gegner in einem Raum einplanen, der einen spiegelnden Boden hat, brauchen Sie Zeiger und Funktionen, die wie mirror_player() aussehen auch für sie.

Mit einer ähnlichen Methode können Sie vertikale Spiegel erstellen. Wenn Sie möchten, dass ich auch darüber einen Artikel schreibe, dann tun Sie dies im Conitec Forum kund, unter “User Contributions” im AUM 31 Thread. Viel Spaß beim Spiegeln!