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

79

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?

RSH1
quelle
6
Interessante Frage. Obwohl ich die Formulierung nicht mag, wäre es nur eine Spekulation, diese Frage als formuliert zu beantworten. Vielleicht haben Sie gesehen, wie dieser Artikel mit Tarn Adams gesprochen hat. Wo sie sich kurz mit der Wegfindung befassen.
MichaelHouse
25
Es absolut produziert spürbare Verlangsamung , wenn Sie eine komplexe Tunneltopologie und 100+ Zwerge haben.
Russell Borogove
3
Ja, DF ist meiner Erfahrung nach in dem von Ihnen beschriebenen Szenario unglaublich langsam.
Argentage
4
Zerstöre ein primäres Treppenhaus und beobachte einen Moment, wie deine Framerate wie ein Stein fällt, während sich jeder Zwerg plötzlich zur gleichen Zeit zurückzieht.
Mooing Duck
2
Ich stimme zu, dass DF nicht das beste Beispiel ist. DF leidet bekanntermaßen unter Leistungsproblemen.
Robert S.

Antworten:

110

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.
Kylotan
quelle
2
+1 dafür, um tatsächlich zu erklären, was los ist, anstatt über Grafiken wie mich herumzuspielen. :)
Matt Kemp
4
Um fair zu sein, ich habe dir auch +1 gegeben, weil ich diesen Aspekt vergessen habe, und es ist sehr wahr - nimm gfx aus der Gleichung und es ist, als würde man Computer sofort 2x oder 3x schneller machen.
Kylotan,
Ich habe gehört, dass DF jetzt Multithread-fähig ist, aber zumindest bis vor kurzem wurde alles in einem einzigen Thread erledigt. (Es kann immer noch sein, nicht sicher)
Mooing Duck
@MooingDuck Ist es immer noch nicht.
Tharwen
63

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.

DampeS8N
quelle
1
1024X1024X32? Vertikal ist 128 oder 256, glaube ich. Es ist weit größer als 32.
Lawton
@Lawton Ich glaube, ich bin falsch in Bezug auf die maximale Größe, aber die Höhe ist nicht so falsch. Ich korrigiere es. Ich habe das Spiel geladen und die Einschiffung, auf der ich mich befinde, ist nur etwa 45 Level hoch. Es könnte sein, dass mehr simuliert wird, aber ich habe keinen Zugang zu ihnen zum Graben oder Bauen.
DampeS8N
@ DampeS8N Ich habe gerade eine unmodifizierte, mittelgroße Karte geladen und konnte von +16 bis -156 sehen, ungefähr 180 Level. 40 Level Maps sind die Ausnahme, nicht die Regel. Selbst wenn Sie nur 40 davon graben können, weil sie von einem Grundwasserleiter oder einer Lava blockiert wurden, ist dies nicht relevant, da der Bereich darunter immer noch mit simuliertem Spaß besiedelt ist.
Lawton
@Lawton, auf meiner Karte kann ich nur durch 45 Ebenen blättern. Sie sind absolut variabel, aber ich war nicht leicht in der Lage, Nummern zu finden, auf die von jeder Karte zugegriffen werden kann. Es kann auch davon abhängen, welche Version des Spiels wir verwenden. Am Ende ist es nicht so wichtig für meine Antwort.
DampeS8N
Es ist ein alter Posten, aber die Tiefen der Zwergenfestung hängen von Sedimentschichten ab. Wie die Erdkruste ist an einigen Stellen dicker. DF ist nicht ganz geologisch korrekt, aber man lernt es wie die Profis: D.
Madmenyo
50

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.

Hierarchische Wegfindung

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 .

BlueRaja - Danny Pflughoeft
quelle
3
Ich fand dieses Video des RimWorld-Entwicklers sehr aufschlussreich. Es ist ein ähnliches Spiel, wenn auch nur in 2D. Er erklärt die Grundlagen der Wegfindung und die Vorteile der Unterteilung der Karte in Regionen. youtube.com/watch?v=RMBQn_sg7DA
Sire
18

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.

Matt Kemp
quelle
8
Ein Datenpunkt, der dafür spricht, ist das OpenGL-Rewrite aus einer früheren Zeit, an das ich mich erinnere, dass es eine massive Steigerung der Framerate gebracht hat. So macht sich auch die einfache Sprite-Grafik bemerkbar, die DF effizient gemacht hat.
Millimoose
3
+1 Grafikstreifen =
enorme
2
Es ist erwähnenswert, dass die Grafiken von DF ungefähr so ​​anspruchsvoll sind wie jedes moderne Indie-2D-Spiel. Es gibt viele Texturen, auch wenn sie klein und einfach sind, und sie können auf Full-HD-Monitoren von Immobilien verteilt werden. Es gibt keine auffälligen Partikeleffekte oder was haben Sie, aber die rohe "Farbe all diese Pixel" Arbeit ist immer noch vorhanden und aufgrund der Anzahl der Zeichnungsaufrufe, die für die winzigen Kachelgrößen erforderlich sind, ist es eine ziemlich große Herausforderung, die Leistung zu verbessern.
DampeS8N
Auf den ersten Blick mag es wie eine alberne Antwort aussehen, aber das ist richtig. Stellen Sie sich vor, was Sie mit 4 bis 12 GB und 4 bis 12 TB GPU-Leistung tun können, wenn Sie keine komplexen Grundelemente zeichnen, auspacken, Texturen erstellen und 3D-Vektoren in transformieren müssen ein 2D-Array von Pixeln, Shadern usw.
Felype
10

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.

API-Biest
quelle
Es gibt viel zu sagen, wenn Sie durch Stapel von Aufgaben treten möchten, die nicht bildgenau sind. Bei AAA-Spielen wird jede einzelne Abteilung häufig explizit in Prozentsätzen von Frames zeitlich eingeteilt, sodass eine Abteilung anderen Abteilungen nicht auf die Zehen treten kann. Wenn die Methode zum Animieren der Baumbewegung basierend auf Windgeschwindigkeit und -richtung langsam ist, werden weniger Bäume verarbeitet, anstatt das Budget anderer Teams zu verschlingen.
DampeS8N