Wie behält die Zwergenfestung den Überblick über so viele Entitäten, ohne an Leistung zu verlieren?

In der Zwergenfestung können Sie Hunderte von Zwergen, Tieren, Goblins usw. gleichzeitig im Spiel haben, von denen jede ihre eigenen komplexen KI- und Pfadfindungsroutinen hat. Meine Frage ist, wie dies nicht zu einer merklichen Verlangsamung führt. Läuft jeder Zwerg in einem eigenen Thread?

Jedem System, das einen Thread für so viele Zeichen hatte, würden die Ressourcen sehr schnell ausgehen. Über Threads erhalten Sie möglicherweise Zugriff auf zusätzliche Prozessorkerne, aber sie machen nichts an sich effizienter und sind mit Overhead verbunden.

Die einfache Antwort ist, jede Entität im Spiel effizient zu verarbeiten.

• Verarbeiten Sie nicht jede Entität in jedem Frame.
• Teilen Sie die Verarbeitung in Aufgaben auf, die häufig ausgeführt werden müssen, und Aufgaben, die nicht häufig ausgeführt werden müssen.
• Verteilen Sie Algorithmen mit langer Laufzeit auf mehrere Frames, damit sie die Verarbeitung in anderen Systemen nicht blockieren.
• Stellen Sie sicher, dass effiziente Algorithmen und Datenstrukturen verwendet werden.
• Zwischenspeichern Sie die Ergebnisse teurer Berechnungen, wenn sie voraussichtlich erneut verwendet werden.

Dwarf Fortress ist kein Open Source-Produkt, und obwohl es eine Menge Vermutungen und Reverse Engineering gibt, die dazu beitragen können, dass alles funktioniert, werde ich mich stattdessen auf einige grundlegende Techniken zur Optimierung eines 3D-Roguelike (keine 3D-Grafik, 3D-Welt) des konzentrieren gleichen Typs.

Wie bei allen Videospielen gibt es viel Rauch und Spiegel, die durch einfache Regeln und Systeme die Illusion von Komplexität erzeugen. Diese reichen von der Verwendung einfacher Zufallszahlen für ziellose Bewegungen bis hin zum Vorbacken eines hochrangigen Netzes von Knoten für die Wegfindung.

Bewegung

Apropos Pfadfindung: Dieses Problem kann für große Räume oft sehr schwierig zu lösen sein, wie es bei einer DF-Karte der Fall ist (bis zu 768 x 768 x 64 IIRC). Das Problem kann jedoch auf folgende Weise vereinfacht und beschleunigt werden:

• Vorgefertigtes Knotennetzwerk: Wenn die Karte erstellt wird, kann die Welt in Blöcke unterteilt werden, und für jeden Block können die Ausgänge und Eingänge zugeordnet werden. Wenn ein Block aktualisiert wird, z. B. wenn eine Wand erstellt wird, muss nur das Netzwerk dieses Blocks aktualisiert werden.
• Etappenweise Pfadfindung: Das Ausführen eines Pfads über die gesamte Karte, Zelle für Zelle, würde viel Zeit in Anspruch nehmen. Stattdessen würden Sie über das größere Chunk-Netzwerk, das die gesamte Verbindung zwischen Chunks zuordnet, nach Pfaden suchen und dann nur einen Pfad innerhalb eines Chunks ausführen, wenn dies der Fall ist von Stück zu Stück bewegen. Dies macht 2 Dinge für Sie. Es beschleunigt die Wegfindung, indem es sich über viele kleinere Teile aufteilt, und es ermöglicht dem Gerät auch, die Richtung auf einem Teil des Weges zu ändern, wenn ein Block aktualisiert wird. Es würde den Pfad über das große Netzwerk ändern, wenn einer der Knoten aktualisiert werden muss.
• Zufallssteuerung: Wenn sich die Einheit nicht zu einem Ziel bewegt, muss sie nur ziellos gehen. Viele Roguelikes bewegen das Gerät nur in eine zufällige Richtung, was sich unnatürlich anfühlt. Es können verschiedene Lenktechniken verwendet werden. Einfache bevorzugen es, sich in einer geraden Linie zu bewegen und haben immer weniger Chancen, sich in die nach hinten strahlenden Richtungen zu bewegen, was nur eine Chance von etwa 1% hätte. Daher kehrte das Gerät manchmal die Richtung vollständig um, aber nur selten.

Ich werde nicht auf die Grundlagen der Wegfindung eingehen. Die meisten Roguelikes verwenden A *, aber es gibt andere Methoden, um die Katze zu häuten. Mmmm Katzenleder ..

Persönliche Aufgaben

Eines der wichtigsten Dinge, die DF-Einheiten zum Platzen bringen und sich lebendig fühlen lassen, ist ihre persönliche Zielliste. In Wahrheit haben viele Roguelike-Spiele dies auf einer grundlegenden Ebene. Grundsätzlich hat jede Einheit eine Liste von Wünschen (und für deine Dörfer Aufgaben, die sie möglicherweise annehmen, um die du bittest) und sie werden sie basierend auf ihrer Persönlichkeit auswählen (Statistiken).

Einige Aufgaben haben Anforderungen. Um einen Lederrock herzustellen, muss das Dorf in einem Geschäft mit X Artikeln sein. Also werden diese alle überprüft und als Aufgaben zu ihrer Liste hinzugefügt. So einfach ist das.

Da eine Einheit die meiste Zeit unterwegs ist, können die Überprüfungen, welche Einheiten gerade aktiv sind, sehr schnell vonstatten gehen. Nur wenige Einheiten treffen zu einem bestimmten Zeitpunkt eine Auswahl, sodass es insgesamt auch für Hunderte oder gar keine Verlangsamung gibt Tausende von Einheiten. Und denken Sie daran, dass in DF alles, von Bienen über Höhlenbewohner bis hin zu Bäumen, Einheiten sind.

Bei einigen zusätzlichen Nachforschungen wird deutlich, dass DF eine schreckliche Arbeit bei der Suche nach Wegen im Allgemeinen leistet. Es zerlegt die Karte nicht in Teile, es zerlegt die Karte in Segmente oder Bereiche, die miteinander verbunden sind (was besser ist als nichts sicheres), so dass meine obige Einschätzung noch weniger ein Beispiel dafür ist, wie DF funktioniert, als ich gedacht habe. :) Was nicht heißt, dass DF aus einer Million anderer Gründe alles andere als verblüffend ist.

Es zeigt, dass in einem Spiel das Spielgeschehen wichtig ist. Keine Grafik, keine großartige Programmierung, kein großartiges Schreiben, keine großartige Musik, nicht einmal die Benutzeroberfläche; nichts anderes ist sogar 1% so wichtig wie das Spiel selbst.

Von dieser Seite :

Nun, [die Wegfindung] sieht von meinem Ende her erstaunlich aus, da es eine Tonne Zeichen gibt, die alles auf einmal tun.

TA: Die Zwerge selbst bewegen sich meistens mit A *, mit der regulären alten Straßen-Distanz-Heuristik. Der schwierige Teil ist, dass es A * nicht wirklich anrufen kann, wenn sie nicht wissen, dass sie im Voraus dorthin gelangen können, oder es wird die Karte überfluten und den Prozessor töten.

Ich weiß nicht, ob er auf diese Weise definitiv das "Überfluten der Karte" verhindert , aber der übliche Weg, dies in Spielen zu tun, ist die Verwendung einer A * -Änderung namens Hierarchical Path-Finding A * oder HPA *. Die Idee ist, das Gitter in viele kleinere, aber größere Abschnitte zu unterteilen und dann mit A * den besten Pfad von jedem Abschnitt zu den benachbarten Abschnitten zu finden. Sie können dies verwenden, um ein viel kleineres Diagramm zu erstellen, über das A * für jede Einheit ausgeführt werden soll.

Sie können diese Chunks auch in noch größere Chunks gruppieren, von denen die "Hierarchie" stammt.

Dieser Algorithmus findet nur annähernd optimale Pfade, aber für Spiele wie Dwarf-Fortress ist das normalerweise in Ordnung. Es ist immer noch garantiert, einen Pfad zu finden, falls einer existiert. und wenn es keinen Pfad gibt, wird nur das kleinere Diagramm überflutet, was enorm viel Zeit spart.

Es gibt auch eine Abstraktion von HPA *, die sich mit Einheiten befasst, die über ein bestimmtes Terrain gehen können, aber nicht über andere (z. B. Klippen, über die Lufteinheiten fahren können, Bodeneinheiten jedoch nicht) . Es heißt HAA * , und es gibt einen sehr zugänglichen Artikel es zu erklären hier .

Sie können mehr über verschiedene Wegfindung Algorithmen lesen hier .

Wenn überhaupt, ist es das Gegenteil - das Ganze läuft auf einem Thread und es erreicht jetzt den Punkt, an dem das zum Sperrfaktor wird (das letzte Mal, als ich es überprüft habe!)

Der Grund dafür ist, dass es keine ausgefallenen Grafiken gibt. Es täuscht, aber die Hauptsache, die Sachen verlangsamt, ist das Zeichnen von Dingen (denken Sie bei AAA-Titeln über zwei Drittel eines Bildes nach oben). Da die Zwergenfestung recht einfach ist, widmet sie sich in der restlichen Zeit interessanten Dingen.

Ich weiß nicht, wie DF codiert ist, aber die Menge der AIs beeindruckt mich nicht wirklich, da die Leute oft übersehen, dass KI keine Präzision benötigt . Es ist durchaus möglich, die meisten Dinge nur alle paar Sekunden zu erledigen. Es ist auch sinnvoll, ungenaue Berechnungen zu verwenden. Unvollkommenheit spart viel Leistung . Sie können die Entscheidungsroutine mit 100 Einheiten alle 100 ms oder 1000 Einheiten pro Sekunde ausführen. Die CPU-Zeit ist gleich lang, aber Sie haben das 10-fache der Einheiten.

Hier ist ein einfaches Beispiel, wie man mit vielen Einheiten umgehen kann:

int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

Die KI wird immer weniger ansprechend sein, je mehr es gibt, aber der Spieler wird es wahrscheinlich nur in extremen Fällen bemerken.