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

Offline mINA87

  • Użytkownik

# 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.

Offline Mr. Spam

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

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# 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.

Offline nembutal

  • Użytkownik

# 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.

Offline Limal

  • Użytkownik
    • http://wolnik.co.uk

# 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.

Offline mINA87

  • Użytkownik

# 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.

Offline mwojt

  • Użytkownik

# 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ć.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# 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ę. :)

Offline mINA87

  • Użytkownik

# 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".

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# 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.

Offline mINA87

  • Użytkownik

# 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.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# 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. :)

Offline Xirdus

  • Redaktor

# 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."

Offline mINA87

  • Użytkownik

# 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.

Offline rm-f

  • Użytkownik
    • Tu trolluje

# 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.

Offline Spider100

  • Użytkownik
    • Strona domowa

# 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).