Letzte Woche haben wir in unserem Blog über Änderungen gesprochen, die es Feinden (Bitern) ermöglichen würden, nicht ineinander zu laufen, aber dies war nicht das einzige Update im Zusammenhang mit Bitern. Zufälligerweise enthielten die Aktualisierungen dieser Woche das, woran wir in den letzten Wochen gearbeitet haben - die Aktualisierung des Suchsystems für Feinde.
Suche nach einem Weg
Wenn eine Einheit irgendwohin ziehen möchte, muss sie zuerst verstehen, wie sie dorthin gelangt. Im einfachsten Fall können Sie direkt zum Ziel gelangen, aber manchmal treten unterwegs Hindernisse auf - Steine, Bäume, feindliche Nester (Spawner), Spielereinheiten. Um den Weg zu ebnen, müssen wir der Pfadfinderfunktion die aktuelle und endgültige Position mitteilen, und der Pfadfinder gibt uns (möglicherweise nach vielen Maßnahmen) einen
Pfad zurück , der einfach eine Reihe von Wegpunkten ist, zu denen sich das Gerät bewegen muss, um zu gelangen Ziel
Um seine Arbeit zu erledigen, verwendet Pathfinder einen Algorithmus namens A * (ausgesprochen "A star"). Ein einfaches Beispiel für das Finden eines Pfades mit A * wird im Video gezeigt: Beißer möchte einen Pfad um Felsen finden. Die Pfadfindungsfunktion beginnt, die Karte um den Beißer herum zu erkunden (die Studie wird durch weiße Punkte dargestellt). Zuerst versucht sie, direkt zum Ziel zu gelangen, aber sobald sie die Klippen erreicht, „verschüttet“ sie sich in beide Richtungen und versucht, eine Position zu finden, von der aus es wieder möglich ist, zum Ziel zu gelangen.
Der Algorithmus in diesem Video ist verlangsamt, damit Sie besser sehen können, wie es funktioniert.Jeder Punkt in der Animation repräsentiert einen
Knoten . Jeder Knoten merkt sich die Entfernung vom Beginn der Suche und eine Schätzung der Entfernung von diesem Knoten zum Ziel (diese Schätzung wird durch die
heuristische Funktion berechnet). Dank der heuristischen Funktion funktioniert A * - es lenkt den Algorithmus in die richtige Richtung.
Im einfachsten Fall berechnet diese Funktion einfach den Abstand in einer geraden Linie vom Knoten zur Zielposition - dies ist der Ansatz, den wir in Factorio von Beginn der Entwicklung an verwendet haben, und dank dessen bewegt sich der Algorithmus zunächst in einer geraden Linie. Dies ist jedoch nicht die einzige Option. Wenn die heuristische Funktion einige der Hindernisse kennt, kann sie den Algorithmus um sie herum lenken, was die Suche beschleunigen würde, da Sie die zusätzlichen Knoten nicht untersuchen müssten. Je intelligenter die Heuristik ist, desto schwieriger ist es natürlich, sie umzusetzen.
Eine einfache heuristische geradlinige Entfernungsschätzfunktion ist gut geeignet, um Pfade über relativ kurze Entfernungen zu finden. Es passte zu uns in früheren Versionen von Factorio - fast immer bewegten sich Beißer über große Entfernungen, nur weil sie durch Verschmutzung wütend wurden, und dies geschah nicht sehr oft. Wir haben jetzt jedoch Artillerie. Artillerie kann leicht auf eine große Anzahl von Beißern auf der anderen Seite eines großen Sees schießen (und sie "bewirtschaften"), wonach sie versuchen, den Weg um den See herum zu ebnen. Das folgende Video zeigt, wie der einfache A * -Algorithmus, den wir zuvor verwendet haben, versucht, den See zu umgehen.
Dieses Video zeigt die Geschwindigkeit des Algorithmus in der Realität; er wird nicht verlangsamt.Blockreduzierung
Das Finden eines Pfades ist eine lange Geschichte, und es gibt viele Techniken, um ihn zu verbessern. Einige dieser Techniken gehören zur Kategorie der
hierarchischen Pfadsuche : In diesem Fall wird die Karte zunächst vereinfacht, der Pfad befindet sich auf dieser vereinfachten Karte, die dann zum Auffinden des realen Pfades verwendet wird. Ich wiederhole, es gibt mehrere spezifische Implementierungen einer solchen Technik, aber alle erfordern eine Vereinfachung des Suchraums.
Wie können Sie die Welt von Factorio vereinfachen? Unsere Karten werden zufällig generiert und ändern sich ständig: Das Platzieren und Löschen von Objekten (z. B. Sammlern, Wänden oder Türmen) ist wahrscheinlich die grundlegendste Mechanik des gesamten Spiels. Wir möchten nicht jedes Mal, wenn wir eine Entität hinzufügen oder entfernen, die gesamte vereinfachte Karte neu erzählen. Wenn wir die Karte jedes Mal neu vereinfachen, wenn wir einen Weg finden müssen, können wir gleichzeitig leicht den gesamten Leistungsgewinn verlieren.
Eine der Personen mit Zugriff auf den Quellcode des Spiels (Allaizn) hatte eine Idee. was ich als Ergebnis implementiert habe. Nun scheint diese Idee offensichtlich.
Das Spiel basiert auf Blöcken von 32x32 Plättchen. Der Vereinfachungsprozess ersetzt jeden Block durch einen oder mehrere
abstrakte Knoten . Da unser Ziel darin besteht, die Suche nach einem Pfad um die Seen herum zu verbessern, können wir alle Entitäten ignorieren und nur Kacheln berücksichtigen: Sie können sich nicht auf dem Wasser bewegen, an Land können Sie. Wir trennen jeden Block in separate
Komponenten . Eine Komponente ist ein Kachelbereich, in dem eine Einheit von einer Kachel innerhalb einer Komponente zu einer anderen Kachel derselben Komponente gelangen kann. In der Abbildung unten ist der Block in zwei separate Komponenten unterteilt: Rot und Grün. Jede dieser Komponenten wird zu einem abstrakten Knoten - tatsächlich wird der gesamte Block auf zwei „Punkte“ reduziert.
Der wichtigste Gedanke von Allaizn war, dass wir nicht für jede Kartenkachel eine Komponente speichern müssen - denken Sie nur an die Kachelkomponenten entlang des Umfangs jedes Blocks, da wir nur daran interessiert sind, mit welchen anderen Komponenten (in benachbarten Blöcken) jeder Komponente verbunden ist, und dies hängt nur von den Kacheln ab, die sich am Rand des Blocks befinden.
Hierarchische Pfadsuche
Wir haben also herausgefunden, wie man die Karte vereinfacht, aber wie man damit Pfade findet. Wie gesagt, es gibt viele hierarchische Pfadsuchtechniken. Die einfachste Idee ist, den Pfad mithilfe abstrakter Knoten vom Anfang bis zum Ziel zu finden. Das heißt, der Pfad ist eine Liste der Blockkomponenten, die Sie besuchen müssen. Dann verwenden wir die Reihe guter alter Suchvorgänge A *, um genau herauszufinden, wie man von einer Komponente des Blocks zu einer anderen wechselt.
Das Problem hierbei ist, dass wir die Karte zu stark vereinfacht haben: Was ist, wenn ein Wechsel von einem Block zum anderen nicht möglich ist, weil einige Objekte (z. B. Felsen) den Pfad blockieren? Beim Reduzieren von Blöcken ignorieren wir alle Entitäten, daher wissen wir nur, dass die Kacheln zwischen den Blöcken irgendwie miteinander verbunden sind, aber wir wissen absolut nichts darüber, ob es möglich ist, von einem zum anderen zu wechseln.
Die Lösung besteht darin, die Vereinfachung einfach als „Empfehlung“ für eine echte Suche zu verwenden. Insbesondere werden wir damit eine intelligente Version der heuristischen Suchfunktion erstellen.
Als Ergebnis haben wir das folgende Schema erhalten: Wir haben zwei Pfadfinder: den
Basispfadfinder , der den realen Pfad findet, und den
abstrakten Pfadfinder , der die heuristische Funktion für den Basispfadfinder bereitstellt. Jedes Mal, wenn der Basispfadfinder einen neuen Basisknoten erstellt, ruft er einen abstrakten Pfadfinder auf, um eine Schätzung der Entfernung zum Ziel zu erhalten. Der abstrakte Pfadfinder verhält sich in umgekehrter Reihenfolge - er beginnt mit dem Suchziel und ebnet den Weg zum Anfang, wobei er sich von einer Komponente des Blocks zur anderen bewegt. Wenn eine abstrakte Suche den Block und die Komponente findet, in denen ein neuer Basisknoten erstellt wird, verwendet sie die Entfernung vom Beginn der abstrakten Suche (die, wie gesagt, die Zielposition der gesamten Suche ist), um eine Schätzung der Entfernung vom neuen Basisknoten zum allgemeinen Ziel zu berechnen.
Die Ausführung des gesamten Pfadfinders für jeden einzelnen Knoten ist jedoch alles andere als schnell, selbst wenn sich der abstrakte Pfadfinder von einem Block zum anderen bewegt. Daher verwenden wir stattdessen ein Schema namens "Reverse Resumable A *". "Umkehren" bedeutet, dass es, wie ich oben sagte, vom Ziel bis zum Anfang ausgeführt wird. "Erneuerbar" bedeutet, dass wir nach dem Auffinden eines Blocks, der für den Basispfadfinder interessant ist, alle seine Knoten im Speicher speichern. Wenn der Basispfadfinder das nächste Mal einen neuen Knoten erstellt und eine Entfernungsschätzung benötigt, sehen wir uns nur die abstrakten Knoten an, die bei der vorherigen Suche gespeichert wurden. Gleichzeitig besteht eine hohe Wahrscheinlichkeit, dass sich der erforderliche abstrakte Knoten noch im Speicher befindet (am Ende deckt ein abstrakter Knoten den größten Teil des Blocks und häufig den gesamten Block ab).
Selbst wenn der Basispfadfinder einen Knoten erstellt, der sich in einem Block befindet, der von keinem der abstrakten Knoten abgedeckt wird, müssen wir nicht die gesamte abstrakte Suche erneut durchführen. Ein praktisches Merkmal des A * -Algorithmus ist, dass er die Ausführung fortsetzt, selbst nachdem er die Arbeit beendet und einen Pfad gefunden hat, und die Knoten um die bereits untersuchten Knoten herum untersucht. Und genau das tun wir, wenn wir eine Entfernungsschätzung für einen Basisknoten benötigen, der sich in einem Block befindet, der noch nicht von der abstrakten Suche abgedeckt wird: Wir setzen die abstrakte Suche von den im Speicher gespeicherten Knoten fort, bis sie zu dem von uns benötigten Knoten erweitert wird.
Das folgende Video zeigt ein neues Pfadfindungssystem in Aktion. Blaue Kreise sind abstrakte Knoten; weiße Punkte - einfache Suche. Der Pfadfinder im Video ist viel langsamer als das Spiel, um zu zeigen, wie es funktioniert. Bei normaler Geschwindigkeit dauert die gesamte Suche nur wenige Ticks. Beachten Sie, dass die einfache Suche, die immer noch den alten Algorithmus verwendet, den wir immer verwendet haben, einfach auf magische Weise „weiß“, wie man sich um den See bewegt.
Da der abstrakte Pfadfinder nur zum Erhalten einer heuristischen Schätzung der Entfernung verwendet wird, kann die Basissuche leicht von dem von der abstrakten Suche vorgeschlagenen Pfad abweichen. Dies bedeutet, dass das Blockreduktionsschema zwar alle Entitäten ignoriert, der grundlegende Pfadfinder sie jedoch fast problemlos umgehen kann. Da Entitäten bei der Vereinfachung der Karte ignoriert werden, müssen wir sie nicht jedes Mal wiederholen, wenn eine Entität hinzugefügt oder entfernt wird. Es reicht aus, nur die Kacheln abzudecken, die geändert wurden (z. B. bei einer Mülldeponie), was viel seltener vorkommt als beim Platzieren von Entitäten.
Darüber hinaus bedeutet dies, dass wir im Wesentlichen denselben Pfadfinder verwenden, den wir seit Jahren verwenden. Nur die heuristische Funktion wurde aktualisiert. Das heißt, diese Änderung wirkt sich nicht auf viele andere Systeme aus und wirkt sich nur auf die Suchgeschwindigkeit aus.