Jak poprawić wydajność drogich funkcji w 2d city builder

Już szukałem odpowiedzi, ale nie byłem w stanie znaleźć najlepszego podejścia do obsługi drogich funkcji / obliczeń.

W mojej obecnej grze (budynek miasta oparty na kafelkach 2D) użytkownik może stawiać budynki, budować drogi itp. Wszystkie budynki wymagają połączenia ze skrzyżowaniem, które użytkownik musi umieścić na granicy mapy. Jeśli budynek nie jest podłączony do tego skrzyżowania, nad budynkiem dotkniętym katastrofą pojawi się znak „Niepołączony z drogą” (w przeciwnym razie należy go usunąć). Większość budynków ma promień i może być również ze sobą powiązana (np. Straż pożarna może pomóc wszystkim domom w promieniu 30 płytek). Właśnie to muszę zaktualizować / sprawdzić, gdy zmieni się połączenie drogowe.

Wczoraj napotkałem duży problem z wydajnością. Spójrzmy na następujący scenariusz: Użytkownik może oczywiście również usuwać budynki i drogi. Jeśli więc użytkownik przerywa połączenie zaraz po skrzyżowaniu , muszę zaktualizować wiele budynków jednocześnie . Myślę, że jedną z pierwszych rad byłoby unikanie zagnieżdżonych pętli (co jest zdecydowanie dużym powodem w tym scenariuszu), ale muszę sprawdzić ...

1. jeśli budynek jest nadal podłączony do skrzyżowania w przypadku, gdy płytka drogi została usunięta (robię to tylko dla budynków dotkniętych tą drogą). (W tym scenariuszu może to być mniejszy problem)

2. lista płytek w promieniu i zdobądź budynki w promieniu (zagnieżdżone pętle - duży 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.
       }
   }
   

To wszystko rozkłada mój FPS z 60 do prawie 10 na sekundę.

Mógłbym to zrobić. Moje pomysły to:

• Nieużywanie głównego wątku (funkcja aktualizacji) dla tego, ale innego wątku. Mogę napotkać problemy z blokowaniem, gdy zacznę korzystać z wielowątkowości.
• Korzystanie z kolejki do obsługi wielu obliczeń (jakie byłoby najlepsze podejście w tym przypadku?)
• Zachowaj więcej informacji w moich obiektach (budynkach), aby uniknąć dalszych obliczeń (np. Budynki w promieniu).

Korzystając z ostatniego podejścia, mogę zamiast tego usunąć jedno zagnieżdżenie w tej foreach:

// 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.
    }
}

Ale nie wiem czy to wystarczy. Gry takie jak Cities Skylines muszą obsługiwać znacznie więcej budynków, jeśli gracz ma dużą mapę. Jak sobie z tym radzą ?! Może istnieć kolejka aktualizacji, ponieważ nie wszystkie budynki aktualizują się w tym samym czasie.

Czekam na Wasze pomysły i komentarze!

Wielkie dzięki!

Zasięg buforowania budynku

Pomysł buforowania informacji o tym, które budynki znajdują się w zasięgu budynku efektorowego (który można buforować albo z efektora, albo w dotkniętym nim budynku) jest zdecydowanie dobrym pomysłem. Budynki (zwykle) się nie poruszają, więc nie ma powodu, aby przerabiać te kosztowne obliczenia. „Co wpływa na ten budynek” i „Co wpływa na ten budynek” to coś, co trzeba tylko sprawdzić, kiedy budynek zostanie utworzony lub usunięty.

Jest to klasyczna wymiana cykli procesora na pamięć.

Obsługa informacji o zasięgu według regionu

Jeśli okaże się, że używasz zbyt dużej ilości pamięci, aby śledzić te informacje, sprawdź, czy możesz poradzić sobie z takimi informacjami według regionów mapy. Podziel mapę na kwadratowe regiony n*npłytki. Jeśli region jest w całości objęty przez straż pożarną, wszystkie budynki w tym regionie są również objęte. Musisz więc przechowywać informacje o zasięgu tylko według regionu, a nie poszczególnych budynków. Jeśli region jest tylko częściowo objęty, musisz wrócić do obsługi połączeń budowania w tym regionie. Tak więc funkcja aktualizacji dla twoich budynków najpierw sprawdzi „Czy region jest objęty przez straż pożarną?” a jeśli nie „Czy ten budynek jest indywidualnie objęty strażą pożarną?”. Przyspiesza to również aktualizacje, ponieważ po usunięciu straży pożarnej nie trzeba już aktualizować stanów pokrycia 2000 budynków, wystarczy zaktualizować tylko 100 budynków i 25 regionów.

Opóźniona aktualizacja

Kolejną optymalizacją, którą możesz zrobić, jest nie aktualizowanie wszystkiego od razu i nie aktualizowanie wszystkiego w tym samym czasie.

Niezależnie od tego, czy budynek jest nadal podłączony do sieci drogowej, nie trzeba sprawdzać każdej klatki (nawiasem mówiąc, możesz również znaleźć kilka sposobów na optymalizację tego, patrząc trochę na teorię grafów). Byłoby całkowicie wystarczające, gdyby budynki sprawdzały to okresowo co kilka sekund po wybudowaniu budynku (ORAZ gdyby nastąpiła zmiana sieci dróg). To samo dotyczy efektów zasięgu budynku. Jest całkowicie do przyjęcia, jeśli budynek sprawdza tylko co kilkaset ramek „Czy przynajmniej jedna ze straży pożarnych, która mnie dotyczy, jest nadal aktywna?”

Możesz mieć więc pętlę aktualizacji, aby wykonywać te kosztowne obliczenia dla kilkuset budynków jednocześnie dla każdej aktualizacji. Możesz dać preferencje budynkom, które są obecnie na ekranie, aby gracze otrzymywali natychmiastowe informacje zwrotne o swoich działaniach.

Odnośnie wielowątkowości

Budowniczowie miast wydają się być bardziej kosztowni pod względem obliczeniowym, szczególnie jeśli chcesz pozwolić graczom budować naprawdę duże i jeśli chcesz mieć wysoką złożoność symulacji. Dlatego na dłuższą metę może nie być źle myśleć o tym, jakie obliczenia w Twojej grze można traktować asynchronicznie.

1. Zduplikowana praca .

Twoje affectedBuildingssą przypuszczalnie blisko siebie, więc różne promienie będą się pokrywać. Zgłoś budynki, które wymagają aktualizacji, a następnie zaktualizuj je.

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. Nieodpowiednie struktury danych.

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

powinno być wyraźnie

var buildingsInRadius = tile.Buildings;

gdzie budynki mają IEnumerablestały czas iteracji (np. a List<Building>)