W jaki sposób Dwarf Fortress śledzi tak wiele bytów bez utraty wydajności?

W Dwarf Fortress możesz mieć setki krasnoludów, zwierząt, goblinów itp. W grze w tym samym czasie, każda z własną złożoną sztuczną inteligencją i procedurami poszukiwania ścieżki. Moje pytanie brzmi: w jaki sposób nie powoduje to zauważalnego spowolnienia? Czy każdy krasnolud działa we własnym wątku?

Każdy system, który miał wątek dla każdej z tak wielu postaci, bardzo szybko wyczerpałby zasoby. Wątki mogą zapewniać dostęp do dodatkowych rdzeni procesora, ale nie zwiększają one wewnętrznej wydajności i mają narzut.

Prosta odpowiedź ma na celu jedynie efektywne przetwarzanie każdego elementu w grze.

• Nie przetwarzaj każdego elementu w każdej ramce.
• Podziel przetwarzanie na rzeczy, które często trzeba robić, i rzeczy, które nie muszą często robić.
• Rozłóż długo działające algorytmy na wiele ramek, aby nie blokowały przetwarzania w innych systemach.
• Upewnij się, że stosowane są wydajne algorytmy i struktury danych.
• Przechowuj w pamięci podręcznej wyniki drogich obliczeń, jeśli prawdopodobnie zostaną ponownie użyte.

Dwarf Fortress nie jest open source i chociaż istnieje wiele domysłów i inżynierii odwrotnej, które mogą wpłynąć na to, jak to wszystko działa, zamiast tego skupię się na kilku podstawowych technikach optymalizacji 3D (nie grafiki 3D, świata 3D) roguelike taki sam typ.

Podobnie jak w przypadku wszystkich gier wideo, istnieje wiele dymu i luster, które tworzą iluzję złożoności z prostych reguł i systemów. Są to zarówno proste liczby losowe do bezcelowego poruszania się, jak i wstępne wypalanie siatki węzłów wysokiego poziomu do wyszukiwania ścieżek.

Ruch

Mówiąc o wyszukiwaniu ścieżek, często może to być bardzo trudny problem do rozwiązania dla dużych przestrzeni, takich jak mapa DF (aż 768 x 768 x 64 IIRC), jednak problem można uprościć i przyspieszyć w następujący sposób:

• Wstępnie upieczona sieć węzłów: Po utworzeniu mapy świat można podzielić na części, a każda część może mieć zmapowane wyjścia i wejścia. Gdy porcja jest aktualizowana, na przykład gdy budowana jest ściana, należy zaktualizować tylko sieć porcji.
• Staged Pathfinding: Uruchomienie ścieżki na całej mapie, komórka dla komórki, zajęłoby dużo czasu, zamiast tego można by znaleźć ścieżkę w większej sieci fragmentów, która mapuje wszystkie połączenia między fragmentami, a następnie uruchomić ścieżkę wewnątrz fragmentu, gdy przechodzenie z porcji na porcję. To robi dla ciebie 2 rzeczy. Przyspiesza wyszukiwanie ścieżki, dzieląc ją na wiele mniejszych elementów, a także umożliwia jednostce zmianę kierunku częściowo wzdłuż ścieżki, gdy fragment jest aktualizowany. Zmieniłby ścieżkę w dużej sieci, jeśli którykolwiek z węzłów musi przejść przez aktualizację.
• Losowe sterowanie: gdy nie zbliża się do celu, jednostka musi jedynie chodzić bez celu. Wielu roguelike po prostu przesuwa jednostkę w losowym kierunku, co wydaje się nienaturalne. Można stosować różne techniki kierowania, z których najprostsze sprzyjają poruszaniu się po linii prostej i mają coraz mniejsze szanse na ruch w kierunkach promieniujących do tyłu, co miałoby tylko około 1% szansy. Dlatego jednostka czasami całkowicie zmienia kierunek, ale tylko rzadko.

Nie będę omawiał podstaw poszukiwania ścieżki. Większość roguelike używa A *, ale istnieją inne metody skórowania kota. Mmmm Skóra kota ..

Zadania osobiste

Jedną z głównych rzeczy, które sprawiają, że jednostki DF wyskakują i czują się żywi, jest ich osobista lista celów. W rzeczywistości wiele gier typu roguelike ma to na podstawowym poziomie. Zasadniczo każda jednostka ma listę pragnień (a dla twoich dorfów zadania, które mogą podjąć, o które prosisz), i wybiorą je na podstawie swojej osobowości (statystyki).

Niektóre zadania mają wymagania. Wykonanie skórzanej spódnicy wymaga, aby dorf był w takim a takim sklepie, który ma X przedmiotów. Wszystkie są sprawdzane i dodawane jako zadania do ich listy. Proste.

Ponieważ przez większość czasu jednostka będzie w tranzycie, kontrole tego, co robią jednostki, mogą być bardzo szybkie, tylko kilka jednostek dokona wyboru w danym momencie, więc ogólnie nie ma spowolnienia nawet dla setek lub tysiące jednostek. I pamiętaj, że w DF wszystko, od pszczół, troglodytów po drzewa, jest jednostkami.

Przeprowadzając dodatkowe badania, jasne jest, że w zabawny sposób DF wykonuje okropną robotę w poszukiwaniu ścieżki. Nie dzieli mapy na części, ale dzieli mapę na segmenty lub obszary, które są połączone (co jest lepsze niż nic na pewno), więc moja powyższa ocena jest jeszcze mniej przykładem działania DF, niż myślałem. :) Co nie znaczy, że DF jest niczym innym niż niesamowitym z miliona innych powodów.

Pokazuje, że w grze ważna jest gra. Nie grafika, nie świetne programowanie, nie świetne pisanie, nie świetna muzyka, nawet interfejs; nic innego nie jest tak ważne, jak 1%, jak sama gra.

Z tej strony :

Cóż [odnajdywanie ścieżki] wygląda niesamowicie z mojego końca, ponieważ jest mnóstwo ton postaci, które robią to jednocześnie.

TA: Same krasnoludy przeważnie poruszają się z A *, ze zwykłą, heurystyczną odległością od ulicy. Problem polega na tym, że tak naprawdę nie może zadzwonić do A *, jeśli nie wie, że może się tam dostać z wyprzedzeniem, w przeciwnym razie spowoduje to zalanie mapy i zabicie procesora.

Nie wiem, czy na pewno w ten sposób zapobiega „zalaniu mapy” , ale zwykłym sposobem na zrobienie tego w grach jest zmiana A * o nazwie Hierarchical Path-Finding A * lub HPA *. Chodzi o to, aby podzielić siatkę na wiele mniejszych, ale większych części, a następnie użyć A *, aby znaleźć najlepszą ścieżkę od każdej części do sąsiednich części. Możesz użyć tego do zbudowania znacznie mniejszego wykresu, na którym uruchomisz A * dla każdej jednostki.

Możesz również pogrupować te fragmenty na jeszcze większe, stąd też pochodzi „hierarchia”.

Algorytm ten znajduje tylko optymalne ścieżki, ale w przypadku gier takich jak Dwarf-Fortress zwykle jest to w porządku. Wciąż istnieje gwarancja znalezienia ścieżki, jeśli taka istnieje; a gdy nie ma ścieżki, wypełnia tylko mniejszy wykres, oszczędzając ogromną ilość czasu.

Istnieje również abstrakcja HPA *, która zajmuje się jednostkami , które mogą pokonywać niektóre tereny, ale nie innymi (np. Klify, nad którymi jednostki powietrzne mogą się przemieszczać, ale jednostki naziemne nie mogą) . To się nazywa HAA * , a tam jest bardzo łatwo dostępny artykuł wyjaśniający go tutaj .

Możesz przeczytać więcej o różnych algorytmach wyszukiwania ścieżek tutaj .

Wręcz przeciwnie - całość działa na jednym wątku i teraz osiąga punkt, w którym staje się czynnikiem blokującym (ostatnim razem sprawdzałem!)

Powodem jest to, że nie ma wymyślnej grafiki. Jest to zwodnicze, ale najważniejsze, co spowalnia rzeczy, to rysowanie rzeczy (pomyśl o dwóch trzecich kadru w tytułach AAA). Ponieważ forteca karłowata jest dość podstawowa, resztę czasu poświęca na robienie interesujących rzeczy.

Nie wiem, jak kodowany jest DF, ale ilość sztucznej inteligencji nie robi na mnie wrażenia, ponieważ ludzie często go nadzorują, że AI nie potrzebuje precyzji . Robienie większości rzeczy jest całkowicie wykonalne co kilka sekund. Można również zastosować nieprecyzyjne obliczenia. Niedoskonałość oszczędza wiele wydajności . Możesz uruchomić procedurę decyzyjną 100 jednostek co 100 ms lub możesz uruchomić ją dla 1000 jednostek co sekundę, zajmie to tyle samo czasu procesora, ale cóż ... masz 10 razy więcej jednostek.

Oto prosty przykład, jak można obsługiwać wiele jednostek:

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

Sztuczna inteligencja będzie coraz mniej reagować, im więcej ich będzie, ale gracz prawdopodobnie zauważy to tylko w skrajnych przypadkach.