Autor Wątek: Wyciskanie soków z procesora w grze RTS  (Przeczytany 5906 razy)

Offline wiew

  • Użytkownik

# Czerwiec 24, 2011, 13:24:41
Witam. Piszę grę strategiczną (RTS) i moim głównym założeniem jest to, aby w grze było bardzo dużo jednostek walczących - 5000 mnie zadowoli. Problem jednak jest taki, że mam procesor core duo 2.6ghz i gdy uruchamiam program z 1000 jedostek widać spadki prędkości działania programu. Moje dotychczasowe optymalizacje są takie: oddzieliłem grafikę od logiki, używam fixed timestep i wykonuję ją (logikę) na osobnym wątku.
Próbowałem oddzielić sekcje logiki na kilka innych wątków (poruszanie jednostek, kolizje między jednostkami, strzelanie, lot pocisków(uprzedzając pytania - tak używałem semaforów)), ale wtedy gra jeszcze bardziej spowolniła i chodziła bardzo skokowo.
Posiadam grę Medieval 2 total war i podczas bitwy z okolo 6000 jednostek, gra chodzi płynnie, a tam przecież jeszcze jest dosyć dobra grafika itp. a w mojej grze jednostka to punkt(bilboard), wiec teoretycznie powinienem móc udźwignąć więcej jednostek niż w medievalu. Może istnieje szybszy sposób liczenia kolizji, niż liczenie w każdej pętli czy każda jednostka koliduje z każdą inną, za pomocą tw. Pitagorasa.

Jak wycisnąć maksymalna moc obliczeniową z procesora? Jak zoptymalizować kod w takiej grze?
Piszę w c++, Code::Blocks i SDL+OpenGL.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline menajev

  • Użytkownik
    • Karate Inowrocław

# Czerwiec 24, 2011, 13:31:54
W Medievelu jednostki był łączone w grupy, więc pewnie większość obliczeń też była dokonywana dla całej grupy.
Sprawdź, wykonanie którego kawałka kodu zajmuje najwięcej czasu i tam szukaj optymalizacji.

Offline Liosan

  • Moderator

# Czerwiec 24, 2011, 13:37:55
Moje dotychczasowe optymalizacje są takie: oddzieliłem grafikę od logiki, używam fixed timestep
To nie są optymalizacje, ale to jest zdrowy rozsądek :)

Próbowałem oddzielić sekcje logiki na kilka innych wątków
Shit, skąd w ogóle taki pomysł? To powinna być ostatnia rzecz jakiej spróbujesz - wątki mają koszt, synchronizacja ma koszt, a na Core 2 duo więcej niż z  2 tego typu wątków korzyści mieć nie będziesz. Oczywiście nie mówię, że posiadanie puli wątków nie daje korzyści, ale taki podział odpowiedzialności jest... chyba mało korzystny.

Posiadam grę Medieval 2 total war i podczas bitwy z okolo 6000 jednostek, gra chodzi płynnie, a tam przecież jeszcze jest dosyć dobra grafika itp. a w mojej grze jednostka to punkt(bilboard)
W Medievalu 2 te 6000 to też billboardy, dopiero po przybliżeniu stają się modelami 3d.

Może istnieje szybszy sposób liczenia kolizji, niż liczenie w każdej pętli czy każda jednostka koliduje z każdą inną, za pomocą tw. Pitagorasa.
Jeśli masz naiwne sprawdzanie kolizji każdy-z-każdym, to to jest sendo Twojego problemu :) Poczytaj o algorytmach podziału przestrzeni. Dwa podstawowe to drzewo czwórkowe (quadtree) i podział mapy na sztywne kubełki/sektory. W Twoim przypadku jeden i drugi powinien dać jakieś 100-krotne przyspieszenie :D

Liosan

Offline mINA87

  • Użytkownik

# Czerwiec 24, 2011, 13:59:51
Przede wszystkim nie optymalizuj w ciemno.
CodeAnalyst/Intel Performance Studio/Intel vTune/gperf - od tego zacznij i zobacz jakie są u Ciebie anomalia w wydajności.
Co do kolizji to poszukaj - na necie jest pełno gotowego kodu do optymalnego liczenia kolizji między poszczególnymi prymitywami, następnie warto zrobić jakiś prosty podział przestrzeni.
Do wyciskania dodatkowych ms możesz jeszcze zaprząc SSE/wątki, ale to powinna być ostateczność.

Offline Troll

  • Użytkownik
    • Oficjalna strona gry Gizarma

# Czerwiec 24, 2011, 14:24:09
Jak wycisnąć maksymalna moc obliczeniową z procesora? Jak zoptymalizować kod w takiej grze?
Piszę w c++, Code::Blocks i SDL+OpenGL.

Pytanie powinno brzmiec: jak napisac grę, żeby wymagała jak najmniej mocy obliczeniowej procesora.

Jeżeli chodzi o RTSy, to w perełkach gier komputerowych było to bardzo ładnie wytłumaczone jak się za to zabrac (niepamiętam w którym tomie).

Offline wiew

  • Użytkownik

# Czerwiec 29, 2011, 19:01:17
Podzieliłem mapę na sztywne sektory i przed przystąpieniem do "poważniejszych" obliczeń sprawdzam czy rozważana jednostka znajduje się na sąsiednich sektorach. To trochę pomogło, ale do 5000 jednostek nadal daleko. Wydaje mi się, że posiadanie tylu jednostek real-time jest na razie nie wykonalne. A co do medievala to słusznie menajev zauważył, że obliczenia są robione dla całej grupy jednostek, a ja chciałem, żeby każda jednostka była autonomiczna :) No cóż, pozostaje mi robienie gierki RTS z około 1500 jednostek, co i tak jest nie mało.
Jeśli jednak ktoś jeszcze ma jakiś genialny pomysł to proszę o napisanie go tu.

Offline counterClockWise

  • Użytkownik

# Czerwiec 29, 2011, 19:06:56
Podzieliłem mapę na sztywne sektory i przed przystąpieniem do "poważniejszych" obliczeń sprawdzam czy rozważana jednostka znajduje się na sąsiednich sektorach. To trochę pomogło, ale do 5000 jednostek nadal daleko. Wydaje mi się, że posiadanie tylu jednostek real-time jest na razie nie wykonalne.

Nadal to kwestia użycia odpowiednich struktur przestrzennych i sprytnego przeszukiwania. Myślę, że projektując szyte na miarę drzewa (nie sztywne siatki) o zwiększającym się LOD lub nawet kombinacje różnych struktur jesteś w stanie spokojnie mieć 5000 jednostek. Może nawet 50000-500000 w sytuacjach optymistycznych tj. gdy mało kolizji zachodzi.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 29, 2011, 19:18:54
Pytanie podstawowe, które należy postawić sobie przed każdą próbą optymalizacji: który element zamula. Kolizje? Logika? AI? Wyświetlanie? Dopiero wtedy można szukać oszczędności.


Cytuj
Nadal to kwestia użycia odpowiednich struktur przestrzennych i sprytnego przeszukiwania. Myślę, że projektując szyte na miarę drzewa (nie sztywne siatki) o zwiększającym się LOD lub nawet kombinacje różnych struktur jesteś w stanie spokojnie mieć 5000 jednostek. Może nawet 50000-500000 w sytuacjach optymistycznych tj. gdy mało kolizji zachodzi.
Wszelakie drzewka są do takich celów wysoce nieoptymalne. Najlepsze rozwiązanie, jakie udało mi się do tego typu rzeczy znaleźć (kolizje między tysiącami małych obiektów) to hashowana tilemapa - czyli sprawdzanie pojedynczej kolizji w O(1). Żadne drzewo temu nie dorówna.

Offline nembutal

  • Użytkownik

# Czerwiec 29, 2011, 19:42:36
Wszelakie drzewka są do takich celów wysoce nieoptymalne. Najlepsze rozwiązanie, jakie udało mi się do tego typu rzeczy znaleźć (kolizje między tysiącami małych obiektów) to hashowana tilemapa - czyli sprawdzanie pojedynczej kolizji w O(1). Żadne drzewo temu nie dorówna.
Możesz wyjaśnić mniej rozgarniętym na czym to polega? Jeżeli chcesz zbudować graf kolizji N obiektów, to w najprostszym wariancie robi się N * (N-1)/2 testów, co nie? Jak to wygląda w twojej metodzie?

Offline Karol

  • Użytkownik

# Czerwiec 29, 2011, 19:55:08
Wydaje mi się, że posiadanie tylu jednostek real-time jest na razie nie wykonalne. (...) No cóż, pozostaje mi robienie gierki RTS z około 1500 jednostek, co i tak jest nie mało.
To teraz nie dziwię się czemu na huge mapie i 8 graczach SoaSE potrafi tak mulić :D.

Offline counterClockWise

  • Użytkownik

# Czerwiec 29, 2011, 20:09:06
Pytanie podstawowe, które należy postawić sobie przed każdą próbą optymalizacji: który element zamula. Kolizje? Logika? AI? Wyświetlanie? Dopiero wtedy można szukać oszczędności.


Cytuj
Nadal to kwestia użycia odpowiednich struktur przestrzennych i sprytnego przeszukiwania. Myślę, że projektując szyte na miarę drzewa (nie sztywne siatki) o zwiększającym się LOD lub nawet kombinacje różnych struktur jesteś w stanie spokojnie mieć 5000 jednostek. Może nawet 50000-500000 w sytuacjach optymistycznych tj. gdy mało kolizji zachodzi.
Wszelakie drzewka są do takich celów wysoce nieoptymalne. Najlepsze rozwiązanie, jakie udało mi się do tego typu rzeczy znaleźć (kolizje między tysiącami małych obiektów) to hashowana tilemapa - czyli sprawdzanie pojedynczej kolizji w O(1). Żadne drzewo temu nie dorówna.

Drzewo może prawie za darmo odrzucić duże fragmenty, ale jasne: pozostaje jeszcze kwestia sprawdzania kolizji między obiektami.
Mało napisałeś, ale jakoś wnioskuje, że tile ma rozmiar tego małego elementu. Robisz jakoś hash-key z jego pozycji i jeśli próbujemy dodać istniejący już klucz to jest kolizja?

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 29, 2011, 20:28:09
Cytuj
Możesz wyjaśnić mniej rozgarniętym na czym to polega? Jeżeli chcesz zbudować graf kolizji N obiektów, to w najprostszym wariancie robi się N * (N-1)/2 testów, co nie? Jak to wygląda w twojej metodzie?
Nie tyle budować graf, co szybko znajdować kolidujące obiekty.

Założenie: obiekty są kółkami (o promieniu 1/2) albo kwadratami o boku 1 (jeżeli są inne rozmiary, to można przeskalować).

Idea algorytmu jest prosta - robimy siatkę pól 1x1 i do każdego pola wrzucamy te jednostki, których środek leży na danym polu (jeżeli jest dokładnie na krawędzi dwóch pól, to wrzucemy obojętnie gdzie). Żeby dla danej jednostki znaleźć inną, z która koliduje wystarczy sprawdzić jednostki zapisane w 4 polach (jednostka może wychodzić maksymalnie o 0.5 pola poza obrys, więc zawsze wystarczy sprawdzić tylko 4 pola w bloku 2x2).

Żeby jednak w pamięci nie trzymać całej mapy kafelków (która może być dość duża) wystarczy zrobić tablicę haszującą. Mając współrzędne pola X Y liczymy hash(X,Y) i używamy bitów, żeby zakres wartości hasha był w okolicy liczba_jednostek*4 (można użyć większej stałej, ale nie mniej niż 2 by minimalizowac kolizje funkcji haszującej). Jeżeli w każdej klatce wrzucamy do hasha wszystkie obiekty od nowa, nie trzeba nawet robić list per-pole, a można zapisywać bezpośrednio w tablicy haszującej elementy po sobie.

// inicjalizacja tablicy
memset(&hash_tile_map[0],0,sizeof(hash_tile_map));

int hash_mask = hash_tile_map.size() - 1;  // rozmiar tablicy musi byc potęgą 2
for(int i=0;i<units.size();i++)
{
    int h = hash(int(units[i]->pos.x),int(units[i]->pos.y));
    while( hash_tile_map[h&hash_mask] ) h++;
    hash_tile_map[h&hash_mask] = units[i];
}

void find_col(Unit *u,int x,int y)
{
    int hash_mask = hash_tile_map.size() - 1;
    int h = hash(x,y);
    Unit *u2;

    while( (u2 = hash_tile_map[h++ & hash_mask]) )
        u->test_collision( u2 );
}

// znajdowanie kolizji
Unit *u = ... ; // nasza jednostka
int x = int(u->pos.x-0.5f);
int y = int(u->pos.y-0.5f);
find_col(u,x,y);
find_col(u,x+1,y);
find_col(u,x,y+1);
find_col(u,x+1,y+1);


Cytuj
Drzewo może prawie za darmo odrzucić duże fragmenty
Problem w tym, że my tutaj nie korzystamy z tej właściwości. Za to boli nas koszt skakania po drzewie.

Offline mINA87

  • Użytkownik

# Czerwiec 29, 2011, 22:14:09
Drzewo ma ten problem, że jak Krzysiek powiedział boli skakanie po drzewku - posypią się cache misse.
Druga sprawa, to że takie sensowne drzewko jest bardziej kosztowne do wygenerowania/zmiany.
Ostatnia kwestia to paralelizacja algorytmów - w przypadku drzewek robi się to problematyczne albo inaczej mówiąc - nieoptymalne.
Praktycznie wszyscy twórcy gier, którzy tworzą z myślą o konsolach, szczególnie z powodów 1 i 3 porzucają bardziej skomplikowane struktury danych na rzecz prostszych i na pozór mniej optymalnych tablic/siatek. W ostatecznym rozrachunku takie siatki łatwiej zoptymalizować, poprawić cache-coherency i zrównoleglić.

wiew: powtórzę to raz jeszcze - CodeAnalyst/Intel vTune. Nie rób nic w ciemno, tylko popatrz co boli Twój kod.

Offline wiew

  • Użytkownik

# Czerwiec 30, 2011, 15:55:27
@mINA87
Próbowałem CodeAnalyst, ale nie ogarniam tego, a vTune nie pokazuje mi kodu źródłowego mojego programu mimo że podałem mu odpowiednie search directory. Spróbuję się z tym jeszcze kiedyś pomęczyć, ale na razie to zostawię. A co do kodu, to jestem pewien na 100%, że to właśnie 2 funkcje sprawdzające kolizje są winne (jedna pilnuje żeby jednostki były w odstępach od siebie (odstęp = 1), a druga sprawdza czy wróg jest w zasięgu strzału(zasięg = 70)), ponieważ po zrobieniu komentarza na tych linijkach, program wyciąga niemal 1000 fps. Zauważyłem, że ilość jednostek nie gra roli dla mojej karty graficznej - 500000(pół miliona) jednostek płynnie chodzi (podczas wyłączonej logiki gry).
Propozycja Krzyśka K. jest interesująca i przetestuję to.

A czy da się zoptymalizować kod tak, żeby gra chodziła płynnie kiedy każda jednostka koliduje z każdą?
Mam na myśli dwie armie walczące ze sobą i każda jednostka bierze w tym udział.

Za jakiś czas wrzucę na stronie filmik z tej gry.

Offline Liosan

  • Moderator

# Czerwiec 30, 2011, 16:01:47
Nawet bez code analysta / vTune jesteś w stanie podać jakieś liczby:
- ile czasu trwa jedna klatka
- ile czasu zajmuja te dwie problematyczne metody w kazdej klatce (każda oddzielnie)
- ile porownan wykonuje funkcja sprawdzajaca kolizje
itp itd. Jeśli masz problem z wydajnością i podejrzewasz że tutaj - to zbieraj takie dane zawsze, nie tylko kiedy odpalasz przez profiler. W buildzie release też się mogą przydać.

Liosan