So verbessern Sie die Leistung für teure Funktionen in 2d City Builder

9

Ich habe bereits nach Antworten gesucht, konnte jedoch nicht den besten Ansatz für die Handhabung teurer Funktionen / Berechnungen finden.

In meinem aktuellen Spiel (ein auf 2 Kacheln basierendes Stadtgebäude) kann der Benutzer Gebäude platzieren, Straßen bauen usw. Alle Gebäude benötigen eine Verbindung zu einer Kreuzung, die der Benutzer am Rand der Karte platzieren muss. Wenn ein Gebäude nicht mit dieser Kreuzung verbunden ist, wird über dem betroffenen Gebäude ein Schild mit der Aufschrift "Nicht mit der Straße verbunden" angezeigt (andernfalls muss es entfernt werden). Die meisten Gebäude haben einen Radius und können auch miteinander verwandt sein (z. B. kann eine Feuerwehr allen Häusern in einem Radius von 30 Kacheln helfen). Das muss ich auch aktualisieren / überprüfen, wenn sich die Straßenverbindung ändert.

Gestern bin ich auf ein großes Leistungsproblem gestoßen. Schauen wir uns das folgende Szenario an: Ein Benutzer kann natürlich auch Gebäude und Straßen löschen. Wenn ein Benutzer jetzt direkt nach der Kreuzung die Verbindung unterbricht, muss ich viele Gebäude gleichzeitig aktualisieren . Ich denke, einer der ersten Ratschläge wäre, verschachtelte Schleifen zu vermeiden (was in diesem Szenario definitiv ein wichtiger Grund ist), aber ich muss überprüfen ...

  1. Wenn ein Gebäude noch mit der Kreuzung verbunden ist, falls eine Straßenkachel entfernt wurde (das mache ich nur für betroffene Gebäude auf dieser Straße). (Könnte in diesem Szenario ein kleineres Problem sein)
  2. die Liste der Radiuskacheln und erhalten Gebäude innerhalb des Radius (verschachtelte Schleifen - großes Problem!) .

    // Go through all buildings affected by erasing this road tile.
    foreach(var affectedBuilding in affectedBuildings) {
        // Get buildings within radius.
        foreach(var radiusTile in affectedBuilding.RadiusTiles) {
            // Get all buildings on Map within this radius (which is technially another foreach).
            var buildingsInRadius = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);  
    
            // Do stuff.
        }
    }
    

Dies alles bricht meine FPS für eine Sekunde von 60 auf fast 10 herunter .

Könnte ich auch tun. Meine Ideen wären:

  • Verwenden Sie nicht den Haupt-Thread (Update-Funktion) für diesen, sondern einen anderen Thread. Wenn ich Multithreading verwende, kann es zu Problemen beim Sperren kommen.
  • Verwenden einer Warteschlange für viele Berechnungen (was wäre in diesem Fall der beste Ansatz?)
  • Bewahren Sie mehr Informationen in meinen Objekten (Gebäuden) auf, um weitere Berechnungen zu vermeiden (z. B. Gebäude im Radius).

Mit dem letzten Ansatz könnte ich stattdessen eine Verschachtelung in dieser Form entfernen:

// Go through all buildings affected by erasing this road tile.
foreach(var affectedBuilding in affectedBuildings) {
    // Go through buildings within radius.
    foreach(var buildingInRadius in affectedBuilding.BuildingsInRadius) {
        // Do stuff.
    }
}

Aber ich weiß nicht, ob das reicht. Spiele wie Cities Skylines müssen viel mehr Gebäude bewältigen, wenn der Spieler eine große Karte hat. Wie gehen sie mit diesen Dingen um?! Möglicherweise gibt es eine Aktualisierungswarteschlange, da nicht alle Gebäude gleichzeitig aktualisiert werden.

Ich freue mich auf Ihre Ideen und Kommentare!

Vielen Dank!

Yheeky
quelle
2
Die Verwendung eines Profilers sollte dabei helfen, festzustellen, welches Bit des Codes das Problem aufweist. Es könnte die Art und Weise sein, wie Sie die betroffenen Gebäude finden, oder vielleicht die // Dinge tun. Nebenbei bemerkt, große Spiele wie City Skylines lösen diese Probleme, indem sie räumliche Datenstrukturen wie Quad-Bäume verwenden. Daher sind alle räumlichen Abfragen weitaus schneller als das Durchlaufen eines Arrays mit einer for-Schleife. In Ihrem Fall könnten Sie beispielsweise ein Abhängigkeitsdiagramm aller Gebäude haben und durch Befolgen dieses Diagramms sofort erkennen, was sich ohne Iterationen auf was auswirkt.
Exaila
Vielen Dank für die detaillierten Informationen. Ich mag die Idee von Abhängigkeiten! Ich werde mir das ansehen!
Yheeky
Ihr Rat war großartig! Ich habe gerade den VS-Profiler verwendet, der mir zeigte, dass ich für jedes betroffene Gebäude eine Pfadfindungsfunktion hatte, um zu überprüfen, ob die Verbindungsverbindung noch gültig ist. Das ist natürlich höllisch teuer! Es sind nur 5 FPS, aber besser als nichts. Ich werde das loswerden und Straßenkacheln Gebäude zuweisen, damit ich diese Wegfindungsprüfung nicht immer wieder durchführen muss. Vielen Dank! Nein, ich muss nur die Probleme mit dem größeren Radius der Gebäude beheben.
Yheeky
Ich bin froh, dass Sie es nützlich fanden: D
Exaila

Antworten:

3

Caching-Gebäudeabdeckung

Die Idee, die Informationen zwischenzuspeichern, welche Gebäude sich in Reichweite eines Effektorgebäudes befinden (die Sie entweder vom Effektor oder vom Betroffenen zwischenspeichern können), ist auf jeden Fall eine gute Idee. Gebäude bewegen sich (normalerweise) nicht, daher gibt es wenig Grund, diese teuren Berechnungen zu wiederholen. "Was wirkt sich dieses Gebäude aus?" Und "Was beeinflusst dieses Gebäude?" Müssen Sie nur überprüfen, wenn ein Gebäude erstellt oder entfernt wird.

Dies ist ein klassischer Austausch von CPU-Zyklen gegen Speicher.

Umgang mit Abdeckungsinformationen nach Region

Wenn sich herausstellt, dass Sie zu viel Speicher verwenden, um diese Informationen zu verfolgen, prüfen Sie, ob Sie diese Informationen nach Kartenregionen verarbeiten können. Teilen Sie Ihre Karte in quadratische Bereiche von n*nFliesen. Wenn eine Region vollständig von einer Feuerwehr abgedeckt ist, werden auch alle Gebäude in dieser Region abgedeckt. Sie müssen also nur Abdeckungsinformationen nach Region speichern, nicht nach einzelnen Gebäuden. Wenn eine Region nur teilweise abgedeckt ist, müssen Sie auf die Bearbeitung von Verbindungen in dieser Region zurückgreifen. Die Update-Funktion für Ihre Gebäude würde also zuerst prüfen, ob die Region, in der sich dieses Gebäude befindet, von einer Feuerwehr abgedeckt wird. und wenn nicht "Wird dieses Gebäude individuell von einer Feuerwehr abgedeckt?". Dies beschleunigt auch Aktualisierungen, da Sie beim Entfernen einer Feuerwehr die Abdeckungsstatus von 2000 Gebäuden nicht mehr aktualisieren müssen, sondern nur noch 100 Gebäude und 25 Regionen aktualisieren müssen.

Verzögerte Aktualisierung

Eine andere Optimierung, die Sie durchführen können, besteht darin, nicht alles sofort und nicht alles gleichzeitig zu aktualisieren.

Ob ein Gebäude noch mit dem Straßennetz verbunden ist oder nicht, müssen Sie nicht bei jedem einzelnen Frame überprüfen (Übrigens finden Sie möglicherweise auch Möglichkeiten, dies speziell zu optimieren, indem Sie sich ein wenig mit der Graphentheorie befassen). Es wäre völlig ausreichend, wenn Gebäude dies nur alle paar Sekunden nach dem Bau des Gebäudes regelmäßig überprüfen würden (UND wenn sich das Straßennetz ändern würde). Gleiches gilt für Gebäudebereichseffekte. Es ist durchaus akzeptabel, wenn ein Gebäude nur alle paar hundert Frames überprüft. "Ist mindestens eine der mich betreffenden Feuerwehren noch aktiv?"

Sie können also Ihre Update-Schleife nur diese teuren Berechnungen für jeweils ein paar hundert Gebäude für jedes Update durchführen lassen. Möglicherweise möchten Sie Gebäuden, die derzeit auf dem Bildschirm angezeigt werden, Voreinstellungen geben, damit die Spieler sofort Feedback zu ihren Aktionen erhalten.

In Bezug auf Multithreading

Städtebauer sind in der Regel rechenintensiver, insbesondere wenn Sie den Spielern erlauben möchten, wirklich große Gebäude zu bauen, und wenn Sie eine hohe Simulationskomplexität wünschen. Auf lange Sicht ist es also möglicherweise nicht falsch, darüber nachzudenken, welche Berechnungen in Ihrem Spiel asynchron gehandhabt werden können.

Philipp
quelle
Dies erklärt, warum es eine Weile dauert, bis SimCity auf dem SNES wieder mit Strom versorgt wird. Ich denke, dies geschieht auch mit seinen anderen flächendeckenden Effekten.
Lozzajp
Vielen Dank für Ihren nützlichen Kommentar! Ich denke auch, dass das Speichern von mehr Informationen mein Spiel beschleunigen könnte. Ich mag auch die Idee, die TileMap in Regionen aufzuteilen, aber ich weiß nicht, ob dieser Ansatz gut genug ist, um mein anfängliches Problem langfristig loszuwerden. Ich habe eine Frage zur verzögerten Aktualisierung. Nehmen wir an, ich habe eine Funktion, mit der meine FPS von 60 auf 45 sinken. Was ist der beste Ansatz, um die Berechnungen aufzuteilen, um die perfekte Menge zu verarbeiten, die die CPU verarbeiten kann?
Yheeky
@Yheeky Hierfür gibt es keine universell einsetzbare Lösung, da es stark situationsabhängig ist, welche Berechnungen Sie verzögern können, welche nicht und welche sinnvolle Berechnungseinheit.
Philipp
Ich habe versucht, diese Berechnungen zu verzögern, indem ich eine Warteschlange mit Elementen mit dem Flag "Aktuell aktualisiert" erstellt habe. Nur dieses Element mit diesem Flag auf true wurde behandelt. Nach Abschluss der Berechnung wurde der Artikel aus der Liste entfernt und der nächste Artikel bearbeitet. Das sollte funktionieren, oder? Aber welche Art von Methode könnte verwendet werden, wenn Sie wissen, dass eine Berechnung selbst Ihre FPS senken würde?
Yheeky
1
@ Yheeky Wie gesagt, es gibt keine universell einsetzbare Lösung. Was ich normalerweise versuchen würde (in dieser Reihenfolge): 1. Sehen Sie, ob Sie diese Berechnung mithilfe geeigneterer Algorithmen und / oder Datenstrukturen optimieren können. 2. Sehen Sie, ob Sie es in Unteraufgaben aufteilen können, die Sie einzeln verzögern können. 3. Überprüfen Sie, ob Sie dies in einer separaten Bedrohung tun können. 4. Befreien Sie sich von der Spielmechanik, die diese Berechnung benötigt, und prüfen Sie, ob Sie sie durch etwas ersetzen können, das weniger rechenintensiv ist.
Philipp
3

1. Doppelte Arbeit .

Sie affectedBuildingssind vermutlich nahe beieinander, sodass sich die verschiedenen Radien überlappen. Markieren Sie die Gebäude, die aktualisiert werden müssen, und aktualisieren Sie sie dann.

var toBeUpdated = new HashSet<Tiles>();
foreach(var affectedBuilding in affectedBuildings) {
    foreach(var radiusTile in affectedBuilding.RadiusTiles) {
         toBeUpdated.Add(radiusTile);

}
foreach (var tile in toBeUpdated)
{
    var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);
    // Do stuff.
}

2. Ungeeignete Datenstrukturen.

var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);

sollte eindeutig sein

var buildingsInRadius = tile.Buildings;

wobei Gebäude eine IEnumerablemit konstanter Iterationszeit ist (z. B. a List<Building>)

Peter
quelle
Guter Punkt! Ich glaube, ich habe versucht, mit MoreLINQ ein Distinct () zu verwenden, aber ich stimme zu, dass dies möglicherweise schneller ist als das Überprüfen von Duplikaten.
Yheeky