Optymalizacja obliczeń grawitacyjnych

Mam kilka przedmiotów o różnej wielkości i prędkości, które przyciągają się do siebie. Przy każdej aktualizacji muszę przeglądać każdy obiekt i sumować siły wynikające z grawitacji każdego innego obiektu. Nie skaluje się zbyt dobrze, jest jednym z dwóch dużych wąskich gardeł, które znalazłem w mojej grze, i nie jestem pewien, co zrobić, aby poprawić wydajność.

To czuje się tak, jak powinny być w stanie zwiększyć wydajność. W danym momencie prawdopodobnie 99% obiektów w systemie będzie miało jedynie nieznaczny wpływ na obiekt. Oczywiście nie mogę sortować obiektów według masy i biorę pod uwagę tylko 10 największych obiektów lub coś podobnego, ponieważ siła zmienia się wraz z odległością bardziej niż z masą (równanie jest wzdłuż linii force = mass1 * mass2 / distance^2). Myślę, że dobrym przybliżeniem byłoby rozważenie największych obiektów i najbliższych obiektów, ignorując setki maleńkich fragmentów skały po drugiej stronie świata, które prawdopodobnie nie mogą wpłynąć na nic - ale w celu ustalenia, które obiekty są najbliżej muszę iterować wszystkie obiekty, a ich pozycje ciągle się zmieniają, więc to nie tak, że mogę to zrobić tylko raz.

Obecnie robię coś takiego:

private void UpdateBodies(List<GravitatingObject> bodies, GameTime gameTime)
{
    for (int i = 0; i < bodies.Count; i++)
    {
        bodies[i].Update(i);
    }
}

//...

public virtual void Update(int systemIndex)
{
    for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
    {
        GravitatingObject body = system.MassiveBodies[i];

        Vector2 force = Gravity.ForceUnderGravity(body, this);
        ForceOfGravity += force;
        body.ForceOfGravity += -force;
    }

    Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
    ForceOfGravity = Vector2.Zero;

    Velocity += Motion.Velocity(acceleration, elapsedTime);
    Position += Motion.Position(Velocity, elapsedTime);
}

(zauważ, że usunąłem dużo kodu - na przykład testy kolizji, nie powtarzam obiektów po raz drugi w celu wykrycia kolizji).

Nie zawsze więc iteruję po całej liście - robię to tylko dla pierwszego obiektu i za każdym razem, gdy obiekt znajdzie siłę, którą odczuwa w stosunku do innego obiektu, ten inny obiekt odczuwa tę samą siłę, więc po prostu aktualizuje oba je - a następnie ten pierwszy obiekt nie musi być ponownie rozpatrywany do końca aktualizacji.

Funkcje Gravity.ForceUnderGravity(...)i Motion.Velocity(...)itp. Wykorzystują tylko trochę wbudowanej matematyki XNA.

Kiedy dwa obiekty zderzają się, tworzą bezmasowe szczątki. Jest przechowywany na osobnej liście, a masywne obiekty nie iterują po szczątkach w ramach obliczania prędkości, ale każdy kawałek szczątków musi iterować po masywnych cząsteczkach.

To nie musi być skalowane do niesamowitych granic. Świat nie jest nieograniczony, zawiera granicę, która niszczy obiekty, które go przekraczają - chciałbym być w stanie poradzić sobie z około tysiącem obiektów, obecnie gra zaczyna się dusić około 200.

Wszelkie przemyślenia na temat tego, jak mogę to poprawić? Jakaś heurystyka, której mogę użyć do ogolenia długości pętli od setek do kilku? Jakiś kod mogę wykonać rzadziej niż przy każdej aktualizacji? Czy powinienem po prostu używać wielowątkowości, dopóki nie będzie wystarczająco szybki, aby umożliwić przyzwoity świat? Czy powinienem spróbować odciążyć obliczenia prędkości do GPU? Jeśli tak, to jak mam to zaprojektować? Czy mogę zachować statyczne, współdzielone dane na GPU? Czy mogę tworzyć funkcje HLSL na GPU i wywoływać je dowolnie (za pomocą XNA), czy też muszą one być częścią procesu losowania?

To brzmi jak zadanie dla siatki. Podziel przestrzeń gry na siatkę, a dla każdej komórki siatki trzymaj listę znajdujących się w niej obiektów. Gdy obiekty przemieszczają się przez granicę komórki, zaktualizuj listę, w której się znajdują. Podczas aktualizowania obiektu i szukania innych, z którymi można wchodzić w interakcje, możesz spojrzeć tylko na bieżącą komórkę siatki i kilka sąsiednich. Możesz dostosować rozmiar siatki, aby uzyskać najlepszą wydajność (równoważenie kosztów aktualizacji komórek siatki - co jest wyższe, gdy komórki siatki są zbyt małe - z kosztem wyszukiwania, który jest wyższy, gdy komórki siatki są zbyt duże duży).

To oczywiście spowoduje, że obiekty znajdujące się dalej niż kilka komórek siatki w ogóle nie będą oddziaływać, co jest prawdopodobnie problemem, ponieważ duże nagromadzenie masy (duży obiekt lub skupisko wielu małych obiektów) powinno , jak wspomniałeś, mają większy obszar wpływów.

Jedną rzeczą, którą możesz zrobić, to śledzić całkowitą masę w każdej komórce siatki i traktować całą komórkę jako pojedynczy obiekt do celów dalszych interakcji. To znaczy: obliczając siłę działającą na obiekt, oblicz bezpośrednie przyspieszenie między obiektami dla obiektów w kilku pobliskich komórkach siatki, a następnie dodaj przyspieszenie między komórkami dla każdej dalszej komórki siatki (lub może tylko te z niemałą ilością masy). Przez przyspieszenie między komórkami mam na myśli wektor obliczony na podstawie całkowitych mas dwóch komórek i odległości między ich środkami. To powinno dać rozsądne przybliżenie zsumowanej grawitacji ze wszystkich obiektów w tej komórce siatki, ale znacznie taniej.

Jeśli świat gry jest bardzo duży, możesz nawet użyć hierarchicznej siatki, takiej jak czteroosobowy (2D) lub ośmiokątny (3D), i zastosować podobne zasady. Oddziaływania na większe odległości odpowiadałyby wyższym poziomom hierarchii.

Algorytm Barnesa-Huta jest dobrym rozwiązaniem. Został on wykorzystany w symulacjach superkomputerów, aby rozwiązać Twój dokładny problem. Nie jest zbyt trudny do kodowania i jest bardzo wydajny. Niedawno napisałem aplet Java, aby rozwiązać ten problem.

Wejdź na http://mathandcode.com/programs/javagrav/ i naciśnij „start” i „pokaż quadtree”.

Na karcie opcji widać, że liczba cząstek może wzrosnąć do 200 000. Na moim komputerze obliczenia kończą się po około 2 sekundach (narysowanie 200 000 kropek zajmuje około 1 sekundy, ale obliczenia działają na osobnym wątku).

Oto jak działa mój aplet:

1. Utwórz listę losowych cząstek z losowymi masami, pozycjami i prędkościami początkowymi.
2. Zbuduj czworokąt z tych cząstek. Każdy węzeł czterokołowy zawiera środek masy każdego podwęzła. Zasadniczo dla każdego węzła masz trzy wartości: massx, massy i mass. Za każdym razem, gdy dodajesz cząsteczkę do danego węzła, zwiększasz odpowiednio massx i massy przez cząsteczkę. X * cząstka.masa i cząstka.y * cząstka.masa. Pozycja (massx / mass, massy / mass) zakończy się jako środek masy węzła.
3. Dla każdej cząstki obliczyć siły (w pełni opisane tutaj ). Odbywa się to, rozpoczynając od górnego węzła i rekurencyjnie przez każdy podwęzeł kwadratu, aż dany podwęzeł będzie wystarczająco mały. Po zatrzymaniu rekurencji można obliczyć odległość od cząstki do środka masy węzła, a następnie obliczyć siłę na podstawie masy węzła i masy cząstki.

Twoja gra powinna z łatwością poradzić sobie z tysiącem wzajemnie przyciągających się obiektów. Jeśli każdy obiekt jest „głupi” (podobnie jak cząsteczki bez kości w moim aplecie), powinieneś być w stanie uzyskać od 8000 do 9000 cząstek, może więcej. I to zakłada jednowątkowe. Dzięki aplikacjom wielowątkowym lub równoległym możesz uzyskać o wiele więcej cząstek niż w czasie rzeczywistym.

Zobacz także: http://www.youtube.com/watch?v=XAlzniN6L94, aby uzyskać duży rendering tego

Nathan Reed ma doskonałą odpowiedź. Krótka wersja tego polega na zastosowaniu techniki szerokofazowej, która pasuje do topologii symulacji, i do wykonywania obliczeń grawitacyjnych tylko na parach obiektów, które będą miały zauważalny wpływ na siebie nawzajem. To naprawdę nie różni się od tego, co zrobiłbyś dla regularnej fazy wykrywania kolizji.

Kontynuując to, kolejną możliwością jest tylko okresowa aktualizacja obiektów. Zasadniczo za każdym razem krok (ramka) aktualizuje tylko ułamek wszystkich obiektów i pozostawia prędkość (lub przyspieszenie, w zależności od preferencji) taką samą dla innych obiektów. Użytkownik raczej nie zauważy opóźnienia w aktualizacjach, o ile interwały nie są zbyt długie. To da ci liniowe przyspieszenie algorytmu, więc zdecydowanie przyjrzyj się także technikom szerokofazowym, jak sugerował Nathan, które mogą dać znacznie większe przyspieszenie, jeśli masz mnóstwo obiektów. Chociaż wcale nie jest tak samo modelowany, jest to coś w rodzaju „fal grawitacyjnych”. :)

Ponadto możesz wygenerować pole grawitacyjne w jednym przejściu, a następnie zaktualizować obiekty w drugim przejściu. Podczas pierwszego przejścia zasadniczo wypełniasz siatkę (lub bardziej złożoną strukturę danych przestrzennych) wpływami grawitacji każdego obiektu. Wynikiem jest teraz pole grawitacyjne, które można nawet renderować (wygląda całkiem fajnie), aby zobaczyć, jakie przyspieszenie zostanie zastosowane do obiektu w danym miejscu. Następnie iterujesz obiekty i po prostu przykładasz do tego obiektu efekty pola grawitacyjnego. Co gorsza, możesz to zrobić na GPU, renderując obiekty jako okręgi / kule do tekstury, a następnie czytając teksturę (lub używając innego przejścia sprzężenia zwrotnego przez GPU), aby zmodyfikować prędkości obiektu.

Poleciłbym użyć Quad Tree. Pozwalają szybko i skutecznie wyszukać wszystkie obiekty w dowolnym prostokątnym obszarze. Oto artykuł wiki na ich temat: http://en.wikipedia.org/wiki/Quadtree

I bezwstydny link do mojego własnego projektu XNA Quad Tree na SourceForge: http://sourceforge.net/projects/quadtree/

Prowadziłbym również listę wszystkich dużych obiektów, aby mogły one oddziaływać na wszystko bez względu na odległość.

Tylko odrobina (prawdopodobnie naiwnego) wkładu. Nie zajmuję się programowaniem gier, ale czuję, że twoim podstawowym wąskim gardłem jest obliczanie grawitacji. Zamiast iterować po każdym obiekcie X, a następnie znaleźć efekt grawitacyjny z każdego obiektu Y i dodać go, możesz wziąć każdą parę X, Y i znaleźć siłę między nimi. To powinno wyciąć liczbę obliczeń grawitacyjnych z O (n ^ 2). Będziesz wtedy dużo dodawać (O (n ^ 2)), ale zwykle jest to tańsze.

Również w tym miejscu możesz zaimplementować reguły takie jak „jeśli siła grawitacji będzie mniejsza niż \ epsilon, ponieważ ciała te są zbyt małe, ustaw siłę na zero”. Korzystne może być posiadanie tej struktury również do innych celów (w tym do wykrywania kolizji).

Rozszerzając odpowiedź Seanmiddleditcha, pomyślałem, że mogę rzucić nieco światła (ironia?) Na pomysł pola grawitacyjnego.

Po pierwsze, nie myśl o tym jak o teksturze, ale o dyskretnym polu wartości, które można modyfikować (jakby dwuwymiarowa tablica); a późniejszą dokładnością symulacji może być rozdzielczość tego pola.

Kiedy wprowadzasz obiekt w pole, jego potencjał grawitacyjny można obliczyć dla wszystkich otaczających wartości; tworząc w ten sposób zlew grawitacyjny na polu.

Ale ile z tych punktów należy obliczyć, zanim stanie się ono bardziej lub tak nieskuteczne jak wcześniej? Prawdopodobnie nie wiele, nawet 32x32, to duże pole do iteracji każdego obiektu. Dlatego podziel cały proces na wiele przejść; każda z różnymi rozdzielczościami (lub dokładnością).

To znaczy, pierwsze przejście może obliczyć grawitację obiektów przedstawioną na siatce 4x4, przy czym każda wartość komórki reprezentuje współrzędną 2D w przestrzeni. Nadanie złożoności cząstkowej O (n * 4 * 4).

Drugie przejście może być dokładniejsze z polem grawitacyjnym o rozdzielczości 64x64, przy czym każda wartość komórki reprezentuje współrzędną 2D w przestrzeni. Ponieważ złożoność jest jednak bardzo wysoka, możesz ograniczyć promień otaczających komórek, których to dotyczy (być może tylko otaczające komórki 5x5 są aktualizowane).

Dodatkowy trzeci przebieg może być wykorzystany do obliczeń o wysokiej dokładności, może z rozdzielczością 1024x1024. Pamiętając, że w żadnym momencie nie wykonujesz osobnych obliczeń 1024x1024, ale operujesz tylko na częściach tego pola (być może podsekcjach 6x6).

W ten sposób ogólna złożoność aktualizacji wynosi O (n * (4 * 4 + 5 * 5 + 6 * 6)).

Aby następnie obliczyć zmiany prędkości dla każdego z twoich obiektów, dla każdego pola grawitacyjnego (4x4, 64x64, 1024x1024) wystarczy po prostu odwzorować położenie mas punktowych na komórkę siatki, zastosować ogólny wektor potencjału grawitacyjnego komórek siatki na nowy wektor; powtórz dla każdej „warstwy” lub „przejścia”; następnie dodaj je razem. To powinno dać ci dobry wynikowy wektor siły grawitacyjnej.

Dlatego ogólna złożoność wynosi: O (n * (4 * 4 + 5 * 5 + 6 * 6) + n). To, co naprawdę się liczy (dla złożoności), to ile otaczających komórek aktualizujesz podczas obliczania potencjału grawitacyjnego w przejściach, a nie ogólna rozdzielczość pól grawitacyjnych.

Powodem występowania pól o niskiej rozdzielczości (pierwsze przejścia) jest oczywiście objęcie wszechświata jako całości i zapewnienie, by odległe masy były przyciągane do gęstszych obszarów pomimo odległości. Następnie użyj pól o wyższej rozdzielczości jako osobnych warstw, aby zwiększyć dokładność dla sąsiednich planet.

Mam nadzieję, że to miało sens.

Co powiesz na inne podejście:

Przypisuj obszar wpływu obiektom na podstawie ich masy - są one po prostu zbyt małe, aby mieć mierzalny efekt poza tym zakresem.

Teraz podziel swój świat na siatkę i umieść każdy obiekt na liście wszystkich komórek, na które ma wpływ.

Wykonuj obliczenia grawitacyjne tylko na obiektach z listy dołączonej do komórki, w której znajduje się obiekt.

Musisz zaktualizować listy tylko wtedy, gdy obiekt przenosi się do nowej komórki siatki.

Im mniejsze komórki siatki, tym mniej obliczeń wykonasz na aktualizację, ale tym więcej pracy wykonasz przy aktualizowaniu list.