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


79

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?


6
Interesujące pytanie. Chociaż nie podoba mi się sposób, w jaki jest wyrażony, ponieważ spekulacją byłoby odpowiedzieć na to pytanie w brzmieniu. Tak czy inaczej, być może widziałeś ten artykuł rozmawiający z Tarnem Adamsem. Tam, gdzie krótko omawiają znalezienie ścieżki.
MichaelHouse

25
To absolutnie powoduje zauważalnego spowolnienia raz masz skomplikowany topologię tunelu i 100 + krasnoludy.
Russell Borogove

3
Tak, DF z mojego doświadczenia jest niesamowicie powolny w opisywanym scenariuszu.
argentage

4
Zniszcz główną klatkę schodową i obserwuj, jak twoja liczba klatek spada na chwilę jak kamień, podczas gdy każdy krasnolud nagle odsuwa się jednocześnie.
Mooing Duck

2
Wpadnę i zgodzę się, że DF nie jest najlepszym przykładem; w rzeczywistości DF ma problemy z wydajnością.
Robert S.

Odpowiedzi:


110

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.

2
+1 za to, za faktyczne wyjaśnienie, co się dzieje, zamiast szemrania o grafice takiej jak ja. :)
Matt Kemp,

4
Szczerze mówiąc, dałem ci również +1, ponieważ zapomniałem o tym aspekcie, i to jest bardzo prawdziwe - wyjmij gfx z równania i to tak, jakby komputery natychmiast dwa lub trzy razy szybsze.
Kylotan

Słyszałem, że DF jest teraz wielowątkowy, ale przynajmniej do niedawna wszystko odbywało się w jednym wątku. (Może być nadal, nie jestem pewien)
Kaczka Mooing

@MooingDuck To wciąż nie jest.
Tharwen,

63

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.


1
1024X1024X32? Wierzę, że w pionie jest 128 lub 256. Jest znacznie większy niż 32.
Lawton

@Lawton Wydaje mi się, że nie mam racji co do maksymalnego rozmiaru, ale wysokość nie jest aż tak nieprawidłowa. Poprawiam to. Załadowałem grę, a statek, na którym jestem, ma tylko około 45 poziomów. Więcej może być „symulowanych”, ale nie mam do nich dostępu do kopania lub budowania.
DampeS8N

@ DampeS8N Właśnie załadowałem niemodyfikowaną, średnią mapę i byłem w stanie oglądać od +16 do -156, około 180 poziomów. Mapy 40 poziomów są wyjątkiem, a nie regułą. Nawet jeśli jesteś w stanie wykopać 40 z nich z powodu zablokowania przez warstwę wodonośną lub lawę, nie ma to znaczenia, ponieważ obszar poniżej jest nadal wypełniony symulowaną zabawą.
Lawton

@Lawton, moja mapa pozwala mi przewijać tylko 45 poziomów. Są absolutnie zmienne, ale nie mogłem łatwo znaleźć liczb, ile jest dostępnych dla każdej mapy. Może to również zależeć od używanej wersji gry. Ostatecznie nie jest to aż tak ważne dla mojej odpowiedzi.
DampeS8N

To stary słup, ale głębokości twierdzy karłowatej zależą od warstw osadowych. Podobnie jak skorupa ziemska jest w niektórych miejscach grubsza. DF nie jest całkowicie poprawna geologicznie, ale badają go jak zawodowcy: D.
Madmenyo,

50

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.

Hierarchiczne wyszukiwanie ścieżek

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 .


3
Uważam ten film od dewelopera RimWorld za bardzo pouczający. To podobna gra, tylko w 2D. Wyjaśnia podstawy szukania ścieżki i korzyści z podziału mapy na regiony. youtube.com/watch?v=RMBQn_sg7DA
Sire

18

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.


8
Jeden punkt danych przemawiający za tym to przepisywanie OpenGL od jakiegoś czasu, które, jak pamiętam, przyniosło ogromny wzrost liczby klatek na sekundę. Więc nawet wykonanie prostej grafiki sprite, którą DF skutecznie wywarło wpływ.
millimoose

3
Grafika z
paskiem

2
Warto zauważyć, że grafika DF jest tak samo wymagająca, jak każda współczesna niezależna gra 2D. Istnieje wiele tekstur, nawet jeśli są małe i proste, i można je rozłożyć na monitory Full HD nieruchomości. Nie ma żadnych efektownych efektów cząsteczkowych ani tego, co masz, ale surowa praca „pomaluj wszystkie te piksele” jest nadal obecna, a ze względu na liczbę wezwań do rysowania potrzebnych dla małych rozmiarów płytek jest naprawdę dużym wyzwaniem, aby sprawić, by była wydajna.
DampeS8N

Na pierwszy rzut oka może to wyglądać głupio, ale jest to poprawne, wyobraź sobie, co można zrobić z mocą procesora graficznego 4-12 gb i 4-12 tflops, jeśli nie potrzebujesz rysować skomplikowanych operacji podstawowych, rozpakowywać, tekstury i przekształcać wektory 3d w tablica 2d pikseli, shaderów itp.
Felype

10

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.


Wiele można powiedzieć o przechodzeniu przez stosy zadań, które nie są precyzyjne na poziomie klatki. Gry AAA często wyraźnie określają ramy czasowe poszczególnych działów w procentach klatek, aby jeden dział nie mógł nadepnąć na palce innych działów. Jeśli metoda animacji kołysania drzew w oparciu o prędkość i kierunek wiatru jest wolna, przetworzonych zostanie mniej drzew, niż pochłonie budżet innych zespołów.
DampeS8N
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.