Warsztat.GD

Programowanie => Projektowanie kodu => Wątek zaczęty przez: wiew w Czerwiec 24, 2011, 13:24:41

Tytuł: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: wiew w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: menajev w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Liosan w 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
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w 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ść.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Troll w 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).
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: wiew w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: counterClockWise w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Krzysiek K. w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: nembutal w 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?
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Karol w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: counterClockWise w 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?
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Krzysiek K. w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: wiew w 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.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Liosan w 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
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Czerwiec 30, 2011, 16:15:41
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ł.
Da się napisać taki kod - zobacz co wyprawiają najnowsze silniki fizyczne z jaką ilością obiektów. U Ciebie sytuacja jest dużo prostsza.
Jak osiągnąć coś takiego u Ciebie? Ciężko powiedzieć bez znajomości Twoich rozwiązań, podejść itp.

Profilery są o tyle fajne, że potrafią pokazać Ci anomalie których byś się nie spodziewał, szczególnie jeśli masz stosunkowo niewielkie doświadczenie w optymalizacji dlatego radziłbym mimo wszystko podszkolić się trochę w nich. Ręczna instrumentacja i zbieranie danych jak sugeruje Liosan też jest bardzo dobrym pomysłem.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Krzysiek K. w Czerwiec 30, 2011, 17:31:02
Cytuj
ponieważ po zrobieniu komentarza na tych linijkach, program wyciąga niemal 1000 fps
No i już żadnego vTune nie potrzebujesz. :)

Cytuj
a druga sprawdza czy wróg jest w zasięgu strzału(zasięg = 70))
No to na taką drugą funkcjonalność bym zrobił jeszcze dwie takie strukturki (to już woła o generalizację w postaci reusowalnej klasy) - do trzymania osobno wojsk jednego i drugiego gracza z siatką o oczku 64.

Jeszcze inna optymalizacją tej drugiej fazy będzie "fixowanie" jednostek na konkretnym przeciwniku - jeżeli jednostka znalazła cel, to może ten cel trzymać w następnej klatce, o ile nie zginął, nie wyszedł spoza zasięgu, albo zdążył się znudzić (licznik czasu albo random z niewielką szansą). Po takim rozwiązaniu z szukania celu będa korzystały głównie jednostki nie mające celu (które w kolejnych klatkach pewnie znowu nic nie znajdą, więc powinno być tanio), podczas gdy jednostki aktywnie walczące od czasu do czasu coś tam sprawdzą (tu test będzie znacznie droższy, bo może być dużo wrogów w zasięgu).

Cytuj
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ł.
Jeżeli masz na myśli kolizje, to taka sytuacja jest abstrakcyjna (całe dwie armie stojące na tym samym metrze kwadratowym?) i nie powinno do niej dojść jeżeli algorytm rozsuwający jednostki robi swoje.

Jeżeli masz na myśli sytuację, gdzie cała jedna armia namierza całą drugą armię (jednostki kolidują promieniem strzału), to rozwiązanie podałem powyżej - nie sprawdzać na chama co klatkę, a co jakiś czas.

Inna kwestia, że proponowany przeze mnie algorytm szukania kolizji słabo się nadaje do wyszukiwania najbliższego sąsiada - tutaj już przewagę mogą mieć drzewa. Oczywiście drzewa niekoniecznie w formie jawnej struktury danych - można posortować obiekty według pozycji na krzywej fraktalnej (np. krzywa Hilberta, ale wystarczy też przetasować na zmianę bity ze współrzędnych X i Y), przez co zrobi się nam w tablicy takie niejawne Quad Tree.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: nembutal w Czerwiec 30, 2011, 20:26:45
Próbowałem CodeAnalyst, ale nie ogarniam tego
Nie ty jeden. Ja chyba ze 3 razy podchodziłem do CodeAnalysta, ale nie udało mi się uzyskać czytelnych i sensownych wyników.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Limal w Czerwiec 30, 2011, 20:28:53
Nembutal, CodeAnalyst nie jest taki ciężki do ogarnięcia. Właściwie to nie przypomniam sobie, abym miał z nim kiedykolwiek kłopot.

Swoją drogą szkoda, że st3tca nie ma na forum. St3tc jest prawdziwym specjalistą od CodeAnalysta.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Czerwiec 30, 2011, 21:50:54
Krzysiek to powodzenia w znajdywaniu CPI na oko ;) Z jednej strony do takiego zastosowania może to być za dużo, z drugiej świetny przykład do nauki optymalizacji z profilerem w ręku.

CodeAnalyst sam w sobie jest aplikacją banalną - parę opcji na krzyż.
Co do interpretacji wyników to też nie widzę problemu - CA i vTune są profilerami samplującymi, więc próbkują co jakiś czas aplikację, żeby stwierdzić co dokładnie robi procesor w danym momencie - na jakiej instrukcji jest, w jakiej funkcji, module, procesie. Teraz jeśli nie trafiliśmy na jakiś bardzo chamski aliasing, to funkcje/instrukcje, które są wykonywane najwięcej razy będą najczęściej trafiane przez profiler i właśnie to zobaczymy w wynikach. Takim fragmentom trzeba poświęcić trochę uwagi, bo albo zawierają błędy, albo są nieoptymalnie napisane albo są bardzo często używane.
Jedyna pułapka, jaka jest związana z korzystaniem z profilerów samplujących to to, że musimy po kolei wyżynać (optymalizując/wyłączając) anomalie w kodzie, bo ciężkie fragmenty mogą nam "przykryć" te lżejsze, nawet jeśli one też będą problematyczne.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mwojt w Czerwiec 30, 2011, 21:57:02
Mając tyle jednostek i licząc to każdy z każdym wiadomo, że będzie mulić, miałem podobny problem ale liczyłem grawitację cząsteczek, tu jest o tyle prościej, że można wykluczyć niepotrzebne obliczenia, myślę że najprostszym rozwiązaniem jest posortowanie jednostek według np. współrzędnej x na mapie, podzielić mapę np. na 20 takich pasków, stworzyć 20 tablic z licznikiem wrzucanych jednostek i liczyć każdy z każdym na pasku i pomiędzy dwoma takimi paskami. Powinno przyśpieszyć co najmniej 10 razy.

A tak poza tym to programista powinien mieć analizator kodu w głowie i wiedzieć co spowalnia program, to wcale nie jest takie trudne, chyba że się nie wie co się właściwie pisze i jak to będzie działać.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Krzysiek K. w Czerwiec 30, 2011, 22:18:14
Cytuj
Krzysiek to powodzenia w znajdywaniu CPI na oko ;)
Na oko może nie, ale jeżeli po wykomentowaniu fragmentu kodu FPSy skaczą w niebo, to nie trzeba wyskakiwać z armatą większego kalibru. W przypadkach, gdzie od razu tego tak nie widać, albo nie można pokomentować, można też dopisać samemu drobne wstawki zbierające statystyki (np. ile czasu spędzamy w której funkcji). Do domowych projektów nie trzeba od razu wyciągać czołgu na muchę. :)
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Czerwiec 30, 2011, 23:02:01
Do domowych projektów nie trzeba od razu wyciągać czołgu na muchę. :)
Nie wiem, ja tam nawet w domu wolę zapuścić CA lub wręcz vTune gdy mam jakiś krytyczny fragment kodu - jakieś obliczenia SIMDowe czy mocno obciążane pętle.
Jak mam problem z wydajnością, to najpierw patrzę w profiler żeby sprawdzić jakie fragmenty są bolesne i potwierdzić tym samym swoje hipotezy, później próbuje przemodelować dany kod, na koniec staram się wycisnąć jak najwięcej na poziomie pojedynczych instrukcji.
W ogóle, to przykre jest, że większość kodu pod SSE krążącego po necie jest pisana na pałę i kompletnie nie bierze pod uwagę pipeliningu/latency i dlatego uważam, że krytyczne fragmenty kodu (operacje matematyczne, kolizje, ważne pętle) powinno się pisać z "profilerem w ręku".
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Krzysiek K. w Lipiec 01, 2011, 13:36:34
Cytuj
W ogóle, to przykre jest, że większość kodu pod SSE krążącego po necie jest pisana na pałę i kompletnie nie bierze pod uwagę pipeliningu/latency i dlatego uważam, że krytyczne fragmenty kodu (operacje matematyczne, kolizje, ważne pętle) powinno się pisać z "profilerem w ręku".
Tego typu rzeczy to ostatnia rzecz, za optymalizowanie której bym się brał. Wolę optymalizować algorytmy, niż wyciskać pojedyncze cykle z procesora.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Lipiec 01, 2011, 14:38:30
Tego typu rzeczy to ostatnia rzecz, za optymalizowanie której bym się brał. Wolę optymalizować algorytmy, niż wyciskać pojedyncze cykle z procesora.
Oczywiście, wiadomo że najpierw trzeba zoptymalizować algorytm i w większośći zastosowań to wystarczy. Jeśli jednak powstały kod jest wąskim gardłem, bądź wysoce prawdopodobne że może nim zostać, to warto posiedzieć nad disasmem i zobaczyć jak to faktycznie działa wewnątrz procka.
Zbieram się od pewnego czasu do napisania prostego symulatora, który chociaż z grubsza obrazowałby latency/throughput dla konkretnego kodu, bo często zwykłe poprzestawianie instrukcji może zdziałać cuda.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Krzysiek K. w Lipiec 01, 2011, 14:51:13
Cytuj
Jeśli jednak powstały kod jest wąskim gardłem, bądź wysoce prawdopodobne że może nim zostać, to warto posiedzieć nad disasmem i zobaczyć jak to faktycznie działa wewnątrz procka.
Albo kupić lepszego kompa lub zrezygnować z pomysłu. Nie mam tyle czasu, by wchodzić w takie rzeczy. :)
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Xirdus w Lipiec 01, 2011, 18:50:42
Jeśli jednak powstały kod jest wąskim gardłem, bądź wysoce prawdopodobne że może nim zostać
"Premature optimization is the root of all evil."
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Lipiec 01, 2011, 20:53:59
Jeśli jednak powstały kod jest wąskim gardłem, bądź wysoce prawdopodobne że może nim zostać
"Premature optimization is the root of all evil."
Tak, ale jak robisz przykładowo skining na CPU, to wypadałoby mieć sensownie działające mnożenie macierzy. Proste.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: rm-f w Lipiec 01, 2011, 20:58:21
Tak, ale jak robisz przykładowo skining na CPU, to wypadałoby mieć sensownie działające mnożenie macierzy. Proste.
Po jakiego chędożonego czorta?
Działa na planowanym sprzęcie? Działa, simple.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Spider100 w Lipiec 01, 2011, 21:42:32
Cytuj
Tak, ale jak robisz przykładowo skining na CPU
Jak ktoś robi skinning na CPU to wiadomo że musi optymalizować:D

Tak jak wcześniej wspomniano - OCT odpada na samym starcie. Haszowanie przestrzenne to najlepsze rozwiązanie pod względem aktualizacji testu kolizji, a nawet odrzucania fragmentów po za obszarem kamery(w przypadku RTS).
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Lipiec 01, 2011, 22:05:41
Przykład skiningu miał pokazać sytuację, w której decydujemy się na jakieś rozwiązanie/algorytmy i już na początku wiemy jakie fragmenty kodu będą obciążone. Pisząc takie fragmenty nie musimy oczywiście od początku pisać całości w ASMie i otymalizować co do instrukcji, ale fajnie by było pokusić się w takich miejscach o wektoryzację chociażby.

Lepszy przykład - programista game play implementuje feature - jakiś obiekt AI powiedzmy, może się spodziewać że level designerzy wykorzystają go dosyć mocno. Taki programista odpala sobie prostego test case'a - działa na planowanym sprzęcie, działa. Nie spadł FPS, nie spadł. Zajebiście - commit i idę do domu. Za tydzień wszyscy z przerażeniem patrzą na regresję FPSów, programiści silnika rzucają wszystko, żeby znowu poprofilować kod gry i voila - okazuje się, że ktoś tydzień temu machnął sobie kod z d.... a na dzień dzisiejszy przypadków użycia tego feature'a jest 100x więcej i wychodzą jakieś debilizmy. Czy faktycznie taka sytuacja musiała wystąpić, bo przecież premature optimization is root of all evil? Źle itnerpretujecie to zdanie, albo nie rozumiecie mojego przesłania :)
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Krzysiek K. w Lipiec 01, 2011, 23:13:42
Cytuj
Tak, ale jak robisz przykładowo skining na CPU, to wypadałoby mieć sensownie działające mnożenie macierzy. Proste.
Dopiero w momencie, gdy ów skinning zacznie Ci zamulać na docelowym sprzęcie. Jeżeli wszystko działa wystarczająco płynnie, to nie ma potrzeby robić żadnych optymalizacji, nawet jeżeli miały by one dać 100-krotny zysk wydajności.

Cytuj
Lepszy przykład - programista game play implementuje feature - jakiś obiekt AI powiedzmy, może się spodziewać że level designerzy wykorzystają go dosyć mocno. Taki programista odpala sobie prostego test case'a - działa na planowanym sprzęcie, działa. Nie spadł FPS, nie spadł. Zajebiście - commit i idę do domu. Za tydzień wszyscy z przerażeniem patrzą na regresję FPSów, programiści silnika rzucają wszystko, żeby znowu poprofilować kod gry i voila - okazuje się, że ktoś tydzień temu machnął sobie kod z d.... a na dzień dzisiejszy przypadków użycia tego feature'a jest 100x więcej i wychodzą jakieś debilizmy. Czy faktycznie taka sytuacja musiała wystąpić, bo przecież premature optimization is root of all evil? Źle itnerpretujecie to zdanie, albo nie rozumiecie mojego przesłania :)
Dobry level designer nie wstawi Ci w mapie featura, który zamuli cała mapę. A nawet jeżeli będzie potrzebował/chciał coś takiego zrobić, to zawczasu uderzy do technicznego, który powinien zidentyfikować kto jest odpowiedzialny za feature i zbadać, ile da się tu ugrać. W przypadku, o którym piszesz, zawalili na całej linii designerzy, którzy nie obejrzeli się na FPSy robiąc mapę.

(co do wcześniejszych wypowiedzi - pisałem o projektach domowych; w firmach panują różne zasady, ale główną jest że szef ma rację i robisz co on Ci zleci)
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: yarpen w Lipiec 02, 2011, 02:03:04
kto jest odpowiedzialny za feature i zbadać, ile da się tu ugrać. W przypadku, o którym piszesz, zawalili na całej linii designerzy, którzy nie obejrzeli się na FPSy robiąc mapę.
Nie do konca. Tak naprawde to zawiodla komunikacja. Programista tworzac feature powinien miec informacje - czy to bedzie jeden NPC na mapie czy 10. Z opisu wynika, ze kazdy dlubie swoja dzialke, a potem ma nadzieje, ze jak sie zlozy do kupy to bedzie dzialac.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Mr.Protek w Lipiec 02, 2011, 07:41:24
Tak, ale jak robisz przykładowo skining na CPU, to wypadałoby mieć sensownie działające mnożenie macierzy. Proste.
To akurat korzystając z tej waszej rozmowy mam pytanie, bo właśnie robię sobie powoli animację szkieletową u siebie na CPU, pogrupowałem Face'y względem materiału i kości (jeżeli 3 wierzchołki Face'a przynależą do tej samej kości) i teraz w zamyśle mam wyświetlać zgrupowane Face'y zmieniając tylko D3DTS_WORLD, czy takie coś będzie wydajne? Przeczytałem gdzieś że nie powinno się zmieniać macierzy widoku i świata za często podczas jednego przebiegu bo karta niby ma dużo do ustawiania rzeczy wewnątrz. Oczywiście Face'y których wierzchołki należą do różnych kości są zgrupowane w kilka grup (zależnych już tylko od materiału) i one wymagają obliczeń dla każdego wierzchołka Face'a.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: hashedone w Lipiec 02, 2011, 10:48:16
Robienie animacji szkieletowej na CPU nigdy nie będzie wydajne.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Lipiec 02, 2011, 13:21:20
@yarpen, Krzysiek: Ani LD, ani komunikacja. Feature był projektowany z myślą o tym, że będzie często wykorzystywany, bo to stosunkowo ważna sprawa była (nie chodzi o NPCe, powiedzmy obiekty-helpery). Autor machnął kod wychodząc z założenia - wstawiam 3 na ampę działa, no to fajnie. LD wyszli z założenia, że skoro działa to korzystają, bo w końcu trzeba, a nikt się nie połapał w czym rzecz dopóki z 10 tych obiektów zrobiło się 1000. Z racji tego, że zmiany FPSów z iteracji na iteraję mapy były niewielkie nikt tego nie zauważył na bieżąco.

@hashedone:
Bullshit. Wydajność to miara względna, którą należy rozpatrywać w konkretnym kontekście dlatego przykładowo:
1. GBA/NDS - jak tutaj zrobisz skinowanie nie na CPU jak masz dostępne tylko ARMy obsługujące fixed pointy?
2. Masz grę na PS3, RSX już wyciska siódme poty - będziesz jeszcze mu dorzucał skining jak masz bezrobotne SPU?
3. Ogólniej - wyobraź sobie instancjonowany animowany tłum osób rysowany forward rendererem. Też będziesz zawsze rzucał wszystko na GPU jeśli nie wspiera ono Stream Outa? No to powodzenia.

Jeśli dobrze pamiętam, to papery na temat Black'n'White 2 rozwodziły się nad tematyką animacji wielkich armii i właśnie tam część obiektów na dalszych LODach miało uproszczone szkielety transformowane na CPU.

@Mr.Protek:
Będziesz miał dużo DIPów, które faktycznie będą sporo stanów zmieniać. Wszystko jest kwestią tego w jaki sprzęt celujesz i na jakim API oraz jakie będą te ilości obiektów. Jeśli dodatkowo będziesz w forward renderingu rysował ten sam model parę razy dla wielu świateł to ta liczba jeszcze bardziej rośnie. W takim wypadku może Ci się bardziej opłacić przetransformować cały szkielet, wrzucić to do VB i wtedy już rysować jako jednolity obiekty jednym DIPem. Jak już wspomniałem - kwestia konkretnej sytuacji.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: rm-f w Lipiec 02, 2011, 13:29:14
Cytuj
1. GBA/NDS - jak tutaj zrobisz skinowanie nie na CPU jak masz dostępne tylko ARMy obsługujące fixed pointy?
> GBA
> skinning
Eeee?

Mówimy o tym samym GBA?
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Lipiec 02, 2011, 13:52:12
Mówimy o tym samym GBA?
http://www.youtube.com/watch?v=oH0gwEAMrxg
http://www.youtube.com/watch?v=Qh4ttJB48i8&feature=related
http://www.youtube.com/watch?v=7_oUy1i7NRY&NR=1
http://www.youtube.com/watch?v=zTRYIOIMqU8&feature=related
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: rm-f w Lipiec 02, 2011, 15:00:41
Jedną/dwie postacie które mają mniej poligonów niz postać w quake jako techdemo z 2002 nazywasz grą?
Tak jak byś mi przytaczał "argumenty" za optymalizacją pod rozmiar assetów pokazując .kkriegera
Sztuka dla sztuki.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: Esidar w Lipiec 02, 2011, 17:58:46
@yarpen, Krzysiek: Ani LD, ani komunikacja. Feature był projektowany z myślą o tym, że będzie często wykorzystywany, bo to stosunkowo ważna sprawa była (nie chodzi o NPCe, powiedzmy obiekty-helpery). Autor machnął kod wychodząc z założenia - wstawiam 3 na ampę działa, no to fajnie. LD wyszli z założenia, że skoro działa to korzystają, bo w końcu trzeba, a nikt się nie połapał w czym rzecz dopóki z 10 tych obiektów zrobiło się 1000.
Jesli "autor wyszedł z założenia", to znaczy że nie rozmawiał o tym z LD, ani z grafikami, czyli zero komunikacji. LD ma usiąść razem z programistą i z grafikiem i we trzech razem mają ustalić, ilość postaci, ich szczegółowość, jakie features są potrzebne (np. mimika, fizyka włosów), jaka będzie różnorodność wyglądu, ile jest na to pamięci, jakie są ograniczenia sprzętu (np. 1 kość na wierzchołek) itd. Nie może być tak, że jeden z nich "wyszedł z założenia".

Eeee?
Mówimy o tym samym GBA?
GBA nie ma sprzętowego skinowania. Musisz robić na CPU. Po za tym to co już pisał mINA87: czasami lepiej jest policzyć skinning na CPU, bo nie tylko odciążasz GPU, ale wtedy również możesz policzyć krawędzie do cieni na stencilu.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Lipiec 02, 2011, 21:42:36
@Esidar: o widzisz, wiedziałem że o czymś zapomniałem, dobrze że przypomniałeś o tych shadow volume'ach.

Mój przykład jest ciut ocenzurowaną sytuacją z życia wziętą. Fakt jest taki, że problemem nie było to, że programista w chwili pisania był przekonany że instancji jego obiektu będzie mało. On miał świadomość że będzie ich dużo. Po prostu sobie machnął kod, wrzucił do repo i tyle.
O takich sytuacjach się właśnie rozpisuję - od początku wiadomo, że dany kod będzie obciążony - w takich sytuacjach po prostu trzeba się zastanowić nad tym co się pisze, warto przeprowadzić testy obciążeniowe a w przypadku najbardziej krytycznego kodu (biblioteki matematyczne, schedulery wątków, niskopoziomowe bebechy renderera, liczenie kolizji itp) warto go wręcz pisać z profilerem w ręku i/lub popatrzeć w wynikowy kod ASM.
Odnośnie takiego podejścia w domu - jasne, że jak będę pisał kółko i krzyżyk to nie będę się przejmował takimi rzeczami, ale jak już pisałbym konkretniejszy silnik, to wpiąłbym sobie CA na stałe, bo wynajdywać koła na nowo po raz 100tny nie mam czasu i nie chciałoby mi się bawić w pisanie ręcznej instrumentacji.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: msieradzki w Lipiec 04, 2011, 18:37:31
Używał ktoś R-drzew, żeby zminimalizować skakanie po pamięci? Znalazłem jeden artykuł:
http://sebastiansylvan.wordpress.com/2010/07/11/r-trees-%E2%80%93-adapting-out-of-core-techniques-to-modern-memory-architectures/
ale zastanawiało mnie czy ktoś mierzył wydajność KD-tree, Octree, R-tree itd. Nie zdziwiłbym się gdyby R-tree porównywalnie dobrze unikało skakania co ta siatka.
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: wiew w Lipiec 23, 2011, 12:59:47
Chyba najbardziej wydajną optymalizacją będzie jednak połączyć jednostki w grupy po 200 jednostek, ale postanowiłem odłożyć optymalizację na później i najpierw ukończyć tą grę.
Pierwsze screeny dostępne na tej stronie: http://warsztat.gd/projects.php?x=view&id=2137
Tytuł: Odp: Wyciskanie soków z procesora w grze RTS
Wiadomość wysłana przez: mINA87 w Lipiec 23, 2011, 14:15:30
Kurcze - aż bym sobie na to popatrzył pod profilerem ;)