Wielowątkowe obliczenia grawitacyjne 2D

Buduję grę w eksplorację kosmosu i obecnie rozpocząłem pracę nad grawitacją (w C # z XNA).

Grawitacja wciąż wymaga ulepszenia, ale zanim to zrobię, muszę rozwiązać niektóre problemy z wydajnością w moich obliczeniach fizycznych.

Wykorzystuje 100 obiektów, zwykle renderując 1000 z nich bez obliczeń fizycznych, osiąga znacznie ponad 300 FPS (co jest moim ograniczeniem FPS), ale każde więcej niż 10 obiektów sprowadza grę (i pojedynczy wątek, na którym działa) do jej kolana podczas obliczeń fizycznych.

Sprawdziłem użycie wątku i pierwszy wątek zabijał się po całej pracy, więc pomyślałem, że po prostu muszę wykonać obliczenia fizyki dla innego wątku. Jednak gdy próbuję uruchomić metodę aktualizacji klasy Gravity.cs w innym wątku, nawet jeśli metoda aktualizacji Gravity nie ma w tym nic, gra wciąż spada do 2 FPS.

Gravity.cs

public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in entityEngine.Entities)
        {
            Vector2 Force = new Vector2();

            foreach (KeyValuePair<string, Entity> e2 in entityEngine.Entities)
            {
                if (e2.Key != e.Key)
                {
                    float distance = Vector2.Distance(entityEngine.Entities[e.Key].Position, entityEngine.Entities[e2.Key].Position);
                    if (distance > (entityEngine.Entities[e.Key].Texture.Width / 2 + entityEngine.Entities[e2.Key].Texture.Width / 2))
                    {
                        double angle = Math.Atan2(entityEngine.Entities[e2.Key].Position.Y - entityEngine.Entities[e.Key].Position.Y, entityEngine.Entities[e2.Key].Position.X - entityEngine.Entities[e.Key].Position.X);

                        float mult = 0.1f *
                            (entityEngine.Entities[e.Key].Mass * entityEngine.Entities[e2.Key].Mass) / distance * distance;

                        Vector2 VecForce = new Vector2((float)Math.Cos(angle), (float)Math.Sin(angle));
                        VecForce.Normalize();

                        Force = Vector2.Add(Force, VecForce * mult);
                    }
                }
            }

            entityEngine.Entities[e.Key].Position += Force;
        }

    }

Tak, wiem. To zagnieżdżona pętla foreach, ale nie wiem, jak inaczej wykonać obliczenia grawitacyjne, i wydaje się, że to działa, jest tak intensywne, że potrzebuje własnego wątku. (Nawet jeśli ktoś zna super wydajny sposób wykonywania tych obliczeń, nadal chciałbym wiedzieć, jak MOGĘ to zrobić na wielu wątkach)

EntityEngine.cs (zarządza instancją Gravity.cs)

public class EntityEngine
{
    public Dictionary<string, Entity> Entities = new Dictionary<string, Entity>();
    public Gravity gravity;
    private Thread T;


    public EntityEngine()
    {
        gravity = new Gravity(this);
    }


    public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in Entities)
        {
            Entities[e.Key].Update();
        }

        T = new Thread(new ThreadStart(gravity.Update));
        T.IsBackground = true;
        T.Start();
    }

}

EntityEngine jest tworzony w Game1.cs, a jego metoda Update () jest wywoływana w Game1.cs.

Potrzebuję moich obliczeń fizycznych w Gravity.cs, aby były uruchamiane przy każdej aktualizacji gry, w osobnym wątku, aby obliczenia nie spowalniały gry do strasznie niskich (0-2) FPS.

W jaki sposób mógłbym sprawić, by wątkowanie działało? (wszelkie sugestie dotyczące ulepszonego systemu planetarnej grawitacji są mile widziane, jeśli ktoś je ma)

Nie szukam też lekcji, dlaczego nie powinienem używać wątków ani niebezpieczeństw związanych z niewłaściwym użyciem, szukam prostej odpowiedzi, jak to zrobić. Spędziłem już godzinę na wyszukiwaniu tego pytania z niewielkimi wynikami, które zrozumiałem lub były pomocne. Nie chcę odejść od niegrzeczności, ale zawsze wydaje się trudne jako programista, aby uzyskać prostą, sensowną odpowiedź, zwykle raczej otrzymuję odpowiedź tak złożoną, że z łatwością byłbym w stanie rozwiązać mój problem, jeśli go zrozumiałem, lub ktoś mówi, dlaczego nie powinienem robić tego, co chcę, i nie oferuje żadnych alternatyw (które są pomocne).

Dziękuję za pomoc!

EDYCJA : Po przeczytaniu odpowiedzi, które otrzymałem, widzę, że was obchodzi, a nie tylko próbujecie wyrzucić odpowiedź, która może zadziałać. Chciałem zabić dwa ptaki jednym kamieniem (poprawa wydajności i nauczenie się podstaw wielowątkowości), ale wydaje się, że większość problemu leży w moich obliczeniach, a gwintowanie jest bardziej kłopotliwe niż warte zwiększenia wydajności. Dziękuję wszystkim, jeszcze raz przeczytam wasze odpowiedzi i wypróbuję wasze rozwiązania, kiedy skończę szkołę, jeszcze raz dziękuję!

Masz tutaj klasyczny algorytm O (n²) . Główna przyczyna problemu nie ma nic wspólnego z wątkami, a wszystko z tym, że algorytm ma dużą złożoność.

Jeśli wcześniej nie spotkałeś notacji „Big O”, oznacza to po prostu liczbę operacji wymaganych do pracy na n elementach (jest to bardzo uproszczone wyjaśnienie). Twoje 100 elementów wykonuje wewnętrzną część pętli 10000 razy .

Podczas tworzenia gier na ogół chcesz unikać algorytmów O (n²) , chyba że masz małą (a najlepiej stałą lub ograniczoną) ilość danych i bardzo szybki algorytm.

Gdyby każdy byt oddziaływał na każdy inny byt, z konieczności wymagałby algorytmu O (n²). Wygląda jednak na to, że tylko kilka jednostek wchodzi w interakcje (z powodu if (distance < ...)) - dzięki czemu można znacznie zmniejszyć liczbę operacji, używając czegoś zwanego „ partycjonowaniem przestrzennym ”.

Ponieważ jest to dość szczegółowy temat i nieco specyficzny dla gry, radzę zadać nowe pytanie, aby uzyskać więcej szczegółów. Przejdźmy dalej...

Jeden z głównych problemów z wydajnością kodu jest dość prosty. To jest cholernie wolne :

foreach (KeyValuePair<string, Entity> e in Entities)
{
    Entities[e.Key].Update();
}

Sprawdzasz słownik według ciągu znaków, przy każdej iteracji (wiele razy w twoich innych pętlach), dla obiektu, który już masz!

Możesz to zrobić:

foreach (KeyValuePair<string, Entity> e in Entities)
{
    e.Value.Update();
}

Lub możesz to zrobić: (Osobiście bardziej mi się podoba, oba powinny być o tej samej prędkości)

foreach (Entity e in Entities.Values)
{
    e.Update();
}

Wyszukiwanie słownika według ciągów jest dość wolne. Bezpośrednie iterowanie będzie znacznie szybsze.

Chociaż, jak często można rzeczywiście trzeba szukać przedmioty wg nazwy? W porównaniu do tego, jak często musisz powtarzać je wszystkie? Jeśli rzadko wyszukujesz nazwy, rozważ przechowywanie swoich bytów w List(daj im Nameczłonka).

Kod, który tam masz, jest stosunkowo trywialny. Nie wyprofilowałem tego, ale założę się, że większość twojego czasu wykonania przeznaczasz na powtarzające się wyszukiwania w słowniku . Twój kod może być „wystarczająco szybki” tylko przez naprawienie tego problemu.

EDYCJA: Kolejnym największym problemem jest prawdopodobnie wywołanie, Atan2a następnie natychmiastowe przekształcenie go w wektor za pomocą Sini Cos! Wystarczy użyć wektora bezpośrednio.

Na koniec omówmy wątki i najważniejsze problemy w kodzie:

Po pierwsze i najbardziej oczywiste: nie twórz nowego wątku w każdej ramce! Obiekty wątku są dość „ciężkie”. Najprostszym rozwiązaniem byłoby po prostu użyć ThreadPoolzamiast tego.

Oczywiście nie jest to takie proste. Przejdźmy do problemu numer dwa: nie dotykaj danych w dwóch wątkach jednocześnie! (Bez dodawania odpowiedniej infrastruktury bezpieczeństwa wątków).

Zasadniczo tupiesz tutaj pamięć w najstraszniejszy sposób. Tutaj nie ma bezpieczeństwa wątków. Dowolny z wielu gravity.Updaterozpoczynanych wątków może nadpisywać dane używane w innym wątku w nieoczekiwanym czasie. Tymczasem główny wątek bez wątpienia dotyczy również wszystkich tych struktur danych. Nie zdziwiłbym się, gdyby ten kod powodował trudne do odtworzenia naruszenia praw dostępu do pamięci.

Uczynienie czegoś takiego wątkiem bezpiecznym jest trudne i może spowodować znaczne zwiększenie wydajności, tak że często nie jest warte wysiłku.

Ale skoro pytasz (nie tak) o to, jak to zrobić, porozmawiajmy o tym ...

Zwykle polecam zacząć od ćwiczenia czegoś prostego, gdzie twój wątek jest w zasadzie „strzelaj i zapomnij”. Odtwarzanie audio, zapisywanie czegoś na dysku itp. Sprawy komplikują się, gdy trzeba wprowadzić wynik z powrotem do głównego wątku.

Istnieją trzy podejścia do twojego problemu:

1) Umieść blokady wokół wszystkich danych używanych w wątkach. W języku C # jest to dość proste dzięki lockoświadczeniu.

Ogólnie rzecz biorąc, tworzysz (i zachowujesz!) new objectBlokadę, aby chronić pewien zestaw danych (to ze względów bezpieczeństwa, które zwykle pojawiają się tylko podczas pisania publicznych interfejsów API - ale dobry styl). Następnie musisz zablokować obiekt blokady wszędzie , gdzie masz dostęp do chronionych danych!

Oczywiście, jeśli coś jest „zablokowane” przez jeden wątek, ponieważ jest w użyciu, a inny wątek próbuje uzyskać do niego dostęp - ten drugi wątek będzie wówczas zmuszony czekać do zakończenia pierwszego wątku. Więc jeśli nie wybierzesz dokładnie zadań, które można wykonać równolegle, zasadniczo uzyskasz wydajność jednowątkową (lub gorszą).

Więc w twoim przypadku nie ma sensu tego robić, chyba że możesz tak zaprojektować grę, aby jakiś inny kod działał równolegle, co nie będzie miało wpływu na Twoją kolekcję encji.

2) Skopiuj dane do wątku, pozwól mu przetworzyć, a następnie wyjmij wynik po zakończeniu.

Dokładny sposób wdrożenia tego zależy od tego, co robisz. Ale oczywiście wiąże się to z potencjalnie kosztowną operacją kopiowania (lub dwiema), która w wielu przypadkach będzie wolniejsza niż zwykłe wykonywanie operacji jednowątkowych.

I oczywiście nadal musisz wykonać inną pracę w tle, w przeciwnym razie główny wątek będzie siedział i czekał na zakończenie drugiego wątku, aby mógł skopiować dane z powrotem!

3) Używaj bezpiecznych dla wątków struktur danych.

Są one nieco wolniejsze niż ich jednowątkowe odpowiedniki i często trudniejsze w użyciu niż proste blokowanie. Nadal mogą wykazywać problemy z blokowaniem (zmniejszeniem wydajności do jednego wątku), chyba że zastosujesz je ostrożnie.

Wreszcie, ponieważ jest to symulacja oparta na ramkach, musisz sprawić, aby główny wątek czekał, aż inne wątki dostarczą wyniki, aby można było renderować ramkę i kontynuować symulację. Pełne wyjaśnienie jest naprawdę zbyt długie, aby je tu podać, ale w zasadzie będziesz chciał nauczyć się korzystać z Monitor.Waiti Monitor.Pulse. Oto artykuł na dobry początek .

Wiem, że nie podałem konkretnych szczegółów implementacji (oprócz tego ostatniego bitu) ani kodu dla żadnego z tych podejść. Przede wszystkim będzie wiele do omówienia. Po drugie, żaden z nich nie ma zastosowania do twojego kodu samodzielnie - musisz podejść do całej architektury z myślą o dodaniu wątków.

Wątkowanie nie magicznie kod, który masz tam szybciej - pozwala po prostu zrobić coś innego w tym samym czasie!

Ok, na pierwszy rzut oka jest kilka rzeczy, które powinieneś wypróbować. Na początku powinieneś spróbować zmniejszyć liczbę kontroli kolizji, możesz to zrobić, używając jakiejś struktury przestrzennej, takiej jak czterokąto . Pozwoli ci to zmniejszyć liczbę drugich foreach, ponieważ będziesz pytać tylko o jednostki zamykające pierwszy.

Odnośnie wątków: staraj się nie tworzyć wątku w każdej turze aktualizacji. Ten koszt może spowalniać bardziej niż przyspieszanie. Zamiast tego spróbuj utworzyć pojedynczy wątek kolizyjny i pozwól mu wykonać pracę za Ciebie. Nie mam konkretnego podejścia kopiuj-wklej-ten-kod , ale są artykuły na temat synchronizacji wątków i pracy w tle dla C #.

Inną kwestią jest to, że w pętli foreach nie musisz tego robić, entityEngine.Entities[e.Key].Textureponieważ masz już dostęp do dykt w nagłówku foreach. Zamiast tego możesz po prostu pisać e.Texture. Tak naprawdę nie wiem o tym, tylko chciałem cię poinformować;)

I ostatnia rzecz: w tej chwili podwójnie sprawdzasz każdy byt, ponieważ jest on sprawdzany w pierwszej ORAZ w drugiej pętli foreach.

Przykład z 2 jednostkami A i B:

pick A in first foreach loop
   pick A in second foreach loop
      skip A because keys are the same
   pick B in second foreach loop
      collision stuff
pick B in first foreach loop
   pick A in second foreach loop
      collision stuff
   pick B in second foreach loop
      skip B because keys are the same

Chociaż jest to możliwe podejście, być może możesz poradzić sobie z A i B w jednej turze, pomijając połowę kontroli kolizji

Mam nadzieję, że dzięki temu zaczniesz =)

PS: Nawet jeśli powiedziałeś, że nie chcesz tego słyszeć: spróbuj utrzymać wykrywanie kolizji w tym samym wątku i po prostu przyspieszyć go wystarczająco. Wątek wydaje się dobrym pomysłem, ale z tym wiąże się potrzeba synchronizacji jak diabli. Jeśli sprawdzanie kolizji przebiega wolniej niż aktualizacja (powód, dla którego jest to związane z wątkami), dostaniesz usterki i błędy, ponieważ kolizja zostanie uruchomiona po tym, jak statki już się poruszyły i na odwrót. Nie chcę cię zniechęcać, to tylko osobiste doświadczenie.

EDYCJA 1: Łącza z samouczkiem QuadTree (Java): http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Szczerze mówiąc, pierwszą rzeczą, którą powinieneś zrobić, to przejść na lepszy algorytm.

Równoważenie symulacji może, nawet w najlepszym możliwym przypadku, przyspieszyć ją tylko o współczynnik równy liczbie procesorów × rdzeni na procesor × wątków na rdzeń dostępnych w twoim systemie - tj. Około 4 do 16 dla nowoczesnego komputera. (Przeniesienie kodu do GPU może zapewnić znacznie bardziej imponujące czynniki paralelizacji, kosztem dodatkowej złożoności programistycznej i niższej prędkości obliczeniowej linii bazowej na wątek.) Dzięki algorytmowi O (n²), podobnie jak przykładowy kod, pozwoliłoby to użyj od 2 do 4 razy więcej cząstek niż obecnie.

I odwrotnie, przejście na bardziej wydajny algorytm może z łatwością przyspieszyć symulację, powiedzmy, od 100 do 10000 (liczby dokładnie oszacowane). Złożoność czasowa dobrych algorytmów symulacji n-ciała wykorzystujących podział przestrzenny skaluje się z grubsza jako O (n log n), który jest „prawie liniowy”, dzięki czemu można oczekiwać prawie tego samego współczynnika wzrostu liczby cząstek, z którymi można sobie poradzić. Również, że nadal będzie używać tylko jeden wątek, więc nadal będzie pokój dla zrównoleglenia na dodatek .

W każdym razie, jak zauważyły ​​inne odpowiedzi, ogólną sztuczką w efektywnym symulowaniu dużej liczby oddziałujących cząstek jest uporządkowanie ich w poczwórne (w 2D) lub ośmiokątne (w 3D). W szczególności, do symulacji grawitacji, podstawowym algorytmem, którego chcesz użyć, jest algorytm symulacji Barnesa-Huta , w którym przechowujesz całkowitą masę (i środek masy) wszystkich cząstek zawartych w każdej komórce twojego kwadratu / oktawy i użyj tego, aby przybliżyć średni wpływ grawitacji cząstek w tej komórce na inne, odległe cząstki.

Możesz znaleźć wiele opisów i samouczków na temat algorytmu Barnes – Hut autorstwa Googlinga , ale tutaj jest miły i prosty sposób na rozpoczęcie pracy , a tutaj jest opis zaawansowanej implementacji używanej do symulacji GPU zderzeń galaktyk.

Kolejna odpowiedź optymalizacyjna, która nie ma nic wspólnego z wątkami. Przepraszam za to.

Obliczasz Odległość () każdej pary. Wymaga to pobrania pierwiastka kwadratowego, który jest wolny. Obejmuje to także kilka wyszukiwań obiektów w celu uzyskania rzeczywistych rozmiarów.

Możesz to zoptymalizować za pomocą funkcji DistanceSquared (). Należy wstępnie obliczyć maksymalną odległość, z jaką dowolne dwa obiekty mogą oddziaływać, wyrównać, a następnie porównać z funkcją DistanceSquared (). Jeśli i tylko jeśli odległość do kwadratu mieści się w granicach maksimum, weź pierwiastek kwadratowy i porównaj go z rzeczywistymi rozmiarami obiektów.

EDYCJA : Ta optymalizacja ma głównie zastosowanie podczas testowania kolizji, co teraz zauważyłem, że tak naprawdę nie jest tym, co robisz (choć na pewno w pewnym momencie to zrobisz). Może jednak mieć zastosowanie do twojej sytuacji, jeśli wszystkie cząstki mają podobny rozmiar / masę.

Nie wiem wiele na temat wątków, ale wygląda na to, że twoje pętle są czasochłonne, więc może się od tego zmieni

i = 0; i < count; i++
  j = 0; j < count; j++

  object_i += force(object_j);

do tego

i = 0; i < count-1; i++
  j = i+1; j < count; j++

  object_i += force(object_j);
  object_j += force(object_i);

może pomóc

Jeśli masz już tak ogromne problemy z 10 symulowanymi obiektami, musisz zoptymalizować kod! Twoja zagnieżdżona pętla spowodowałaby tylko 10 * 10 iteracji, z których 10 jest pomijanych (ten sam obiekt), co daje 90 iteracji wewnętrznej pętli. Jeśli osiągniesz tylko 2 FPS, oznacza to, że twoja wydajność jest tak zła, że ​​osiągasz tylko 180 iteracji wewnętrznej pętli na sekundę.

Proponuję wykonać następujące czynności:

1. PRZYGOTOWANIE / ZNACZENIE: Aby na pewno wiedzieć, że ta procedura stanowi problem, napisz małą procedurę testową. Powinien on wykonać Update()metodę grawitacji wiele razy, na przykład 1000 razy i zmierzyć swój czas. Jeśli chcesz osiągnąć 30 klatek na sekundę na 100 obiektów, powinieneś symulować 100 obiektów i mierzyć czas na 30 wykonań. Powinien być krótszy niż 1 sekunda. Korzystanie z takiego testu porównawczego jest potrzebne do racjonalnych optymalizacji. W przeciwnym razie prawdopodobnie osiągniesz coś przeciwnego i sprawisz, że kod będzie działał wolniej, ponieważ po prostu uważasz, że musi być szybszy ... Naprawdę zachęcam do zrobienia tego!

2. OPTYMALIZACJE: Chociaż nie można wiele zrobić z problemem nakładu pracy O (N²) (co oznacza, że ​​czas obliczeń wydłuża się kwadratowo wraz z liczbą symulowanych obiektów N), można poprawić sam kod.

   a) W swoim kodzie używasz wielu wyszukiwań „tablicy asocjacyjnej” (słownika). Te są wolne! Na przykład entityEngine.Entities[e.Key].Position. Nie możesz po prostu użyć e.Value.Position? To oszczędza jedno wyszukiwanie. Robisz to wszędzie w całej wewnętrznej pętli, aby uzyskać dostęp do właściwości obiektów, do których odnoszą się e i e2 ... Zmień to! b) Tworzysz nowy Vector wewnątrz pętli new Vector2( .... ). Wszystkie „nowe” wywołania wiążą się z pewną alokacją pamięci (a później: zwolnieniem). Są nawet znacznie wolniejsze niż wyszukiwanie słowników. Jeśli potrzebujesz tylko tego wektora tymczasowo, więc przydziel go poza pętlami ORAZ - użyj go ponownie, ponownie inicjując jego wartości do nowych wartości, zamiast tworzyć nowy obiekt. c) Używasz wielu funkcji trygonometrycznych (np. atan2icos) w pętli. Jeśli twoja dokładność nie musi być naprawdę dokładna, możesz zamiast tego spróbować użyć tabeli odnośników. Aby to zrobić, przeskaluj swoją wartość do zdefiniowanego zakresu, zaokrąglij ją do wartości całkowitej i wyszukaj w tabeli wstępnie obliczonych wyników. Jeśli potrzebujesz pomocy, po prostu zapytaj. d) Często używasz .Texture.Width / 2. Możesz to wstępnie obliczyć i zapisać wynik jako.Texture.HalfWidth lub - jeśli jest to zawsze dodatnia liczba całkowita - możesz użyć bitowej operacji przesunięcia, >> 1aby podzielić przez dwa.

Wykonuj tylko jedną ze zmian naraz i mierz zmianę za pomocą testu porównawczego, aby zobaczyć, jak wpłynęło to na czas działania! Może jedno jest dobre, a drugie jest złe (nawet ja zaproponowałem je powyżej!) ...

Myślę, że te optymalizacje będą znacznie lepsze niż próby osiągnięcia lepszej wydajności przy użyciu wielu wątków! Będziesz miał wiele problemów z koordynacją wątków, aby nie zastąpiły one innych wartości. Będą również powodować konflikty podczas uzyskiwania dostępu do podobnych regionów pamięci. Jeśli do tego zadania używasz 4 procesorów / wątków, możesz spodziewać się jedynie przyspieszenia od 2 do 3 dla liczby klatek na sekundę.

Czy potrafisz go przerobić bez linii tworzenia obiektu?

Vector2 Force = nowy Vector2 ();

Vector2 VecForce = nowy Vector2 ((zmiennoprzecinkowy) Math.Cos (kąt), (zmiennoprzecinkowy) Math.Sin (kąt));

gdybyś mógł umieścić wartość siły w elemencie zamiast tworzyć dwa nowe obiekty za każdym razem, może to pomóc w poprawie wydajności.