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?
G * m1 * m2 / r^2G służy jedynie do poprawiania zachowania. (chociaż nie mogę ich po prostu podążać ścieżką, ponieważ użytkownik może zakłócać system)