23. Februar 2007
Heute bekommt ihr wieder was aus dem Programmierbereich zu lesen: Woher wissen die NPCs eigentlich, wo sie laufen können und wohin? Dafür sind Wegpunkte und das Wegnetz zuständig. Die Wegpunkte sind dabei sozusagen die Eckpunkte der Wege, welche im Leveleditor angemessen verbunden werden und dadurch das Wegnetz entstehen lassen. Will nun ein NPC von einem Punkt A zu Punkt B laufen, dann weiß er genau, welche Wege er ablaufen muss, um den Zielpunkt zu erreichen. Halt, so einfach geht's nicht! Woher weiß der NPC, wann er abbiegen muss? Woher weiß er, welche Wege er gehen muss, um auf kürzestem Weg ohne Umwege zum Ziel zu gelangen? Dafür ist die Wegnetztabelle zuständig, eine Art Routingtabelle. Sie beinhaltet für jeden Punkt die Information, wohin der NPC als nächstes laufen muss, wenn er ein bestimmtes Ziel erreichen will.
Ein einfaches Beispiel:
Will ein NPC von A nach C, so schaut er in der ersten Zeile der Tabelle (Zeile A) und der dritten Spalte (Spalte C) nach, was der nächste Punkt auf seiner Route ist, zu dem er laufen muss. In diesem Fall ist das der Punkt B. Dort angekommen schaut der NPC in der B-Zeile der Tabelle in Spalte C. Dort ist ein C eingetragen, was bedeutet, dass der NPC nur noch einen Wegpunkt vom Ziel entfernt ist und dort also direkt hinlaufen kann. Normalerweise ist die Wegnetztabelle im Spiel natürlich sehr viel größer (mehrere tausend Wegpunkte) und entsprechend mehr Zwischenstationen müssen abgelaufen werden.
Leider fällt die Wegnetztabelle nicht einfach so vom Himmel, sondern muss berechnet werden - und das dauert. Es müssen nämlich die kürzesten Routen von jedem Punkt zu jedem anderen Punkt bestimmt werden. Um die garantiert kürzesten Wege zu erhalten, ist leider ein sehr hoher kubischer Aufwand nötig (für die Experten: O(n^3)). Das bedeutet, wenn man die Wegnetztabelle für doppelt so viele Wegpunkte berechnen will, dauert die Berechnung 8 mal so lange (2^3 = 8). Auf meinem Computer kann ich z.B. eine Wegtabelle für 1000 Wegpunkte in 7 Sekunden berechnen lassen. Wenn ich 2000 Wegpunkte verwende, muss ich schon 56 Sekunden warten. Für eine Tabelle für 8000 Wegpunkte müsste man also z.B. schon eine knappe Stunde einplanen. Zum Glück kann die Wegnetztabelle aber vorberechnet werden, so dass dies nicht zur Laufzeit des Spiels passieren muss und der Spieler von den langen Rechenzeiten gar nichts mitbekommt. Berechnet wird die Tabelle in DicEd mit dem Floyd-Algorithmus, den wir etwas modifiziert haben, um die Zwischenpunkte und nicht nur die minimalen Weglängen zu erhalten, wie eigentlich vom ursprünglichen Algorithmus vorgesehen.
Diese Mechanismen ermöglichen es, dass ein NPC im Spiel z.B. mit dem Skriptbefehl gotoWP("Sternwarte") los läuft und problemlos den Weg dort hin findet. Eigentlich unfair, könnte man jetzt meinen - der menschliche Spieler muss den Weg ja selbst finden, ohne einen eingebauten Routenplaner zu besitzen. Aber: Der Mensch ist schlau und der Computer dumm - letzteres lässt sich aber glücklicherweise mit Techniken wie der heute vorgestellten vertuschen :)
| A | B | C | D | |
| A | A | B | B | D |
| B | A | B | C | D |
| C | B | B | C | D |
| D | A | B | C | D |
Leider fällt die Wegnetztabelle nicht einfach so vom Himmel, sondern muss berechnet werden - und das dauert. Es müssen nämlich die kürzesten Routen von jedem Punkt zu jedem anderen Punkt bestimmt werden. Um die garantiert kürzesten Wege zu erhalten, ist leider ein sehr hoher kubischer Aufwand nötig (für die Experten: O(n^3)). Das bedeutet, wenn man die Wegnetztabelle für doppelt so viele Wegpunkte berechnen will, dauert die Berechnung 8 mal so lange (2^3 = 8). Auf meinem Computer kann ich z.B. eine Wegtabelle für 1000 Wegpunkte in 7 Sekunden berechnen lassen. Wenn ich 2000 Wegpunkte verwende, muss ich schon 56 Sekunden warten. Für eine Tabelle für 8000 Wegpunkte müsste man also z.B. schon eine knappe Stunde einplanen. Zum Glück kann die Wegnetztabelle aber vorberechnet werden, so dass dies nicht zur Laufzeit des Spiels passieren muss und der Spieler von den langen Rechenzeiten gar nichts mitbekommt. Berechnet wird die Tabelle in DicEd mit dem Floyd-Algorithmus, den wir etwas modifiziert haben, um die Zwischenpunkte und nicht nur die minimalen Weglängen zu erhalten, wie eigentlich vom ursprünglichen Algorithmus vorgesehen.
Diese Mechanismen ermöglichen es, dass ein NPC im Spiel z.B. mit dem Skriptbefehl gotoWP("Sternwarte") los läuft und problemlos den Weg dort hin findet. Eigentlich unfair, könnte man jetzt meinen - der menschliche Spieler muss den Weg ja selbst finden, ohne einen eingebauten Routenplaner zu besitzen. Aber: Der Mensch ist schlau und der Computer dumm - letzteres lässt sich aber glücklicherweise mit Techniken wie der heute vorgestellten vertuschen :)
