Multithreading 2D gravity calculations

Question

I'm building a space exploration game and I've currently started working on gravity ( In C# with XNA).

The gravity still needs tweaking, but before I can do that, I need to address some performance issues with my physics calculations.

This is using 100 objects, normally rendering 1000 of them with no physics calculations gets well over 300 FPS (which is my FPS cap), but any more than 10 or so objects brings the game (and the single thread it runs on) to its knees when doing physics calculations.

I checked my thread usage and the first thread was killing itself from all the work, so I figured I just needed to do the physics calculation on another thread. However when I try to run the Gravity.cs class's Update method on another thread, even if Gravity's Update method has nothing in it, the game is still down to 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;
        }

    }

Yeah, I know. It's a nested foreach loop, but I don't know how else to do the gravity calculation, and this seems to work, it's just so intensive that it needs its own thread. (Even if someone knows a super efficient way to do these calculations, I'd still like to know how I COULD do it on multiple threads instead)

EntityEngine.cs (manages an instance of 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 is created in Game1.cs, and its Update() method is called within Game1.cs.

I need my physics calculation in Gravity.cs to run every time the game updates, in a separate thread so that the calculation doesn't slow the game down to horribly low (0-2) FPS.

How would I go about making this threading work? (any suggestions for an improved Planetary Gravity system are welcome if anyone has them)

I'm also not looking for a lesson in why I shouldn't use threading or the dangers of using it incorrectly, I'm looking for a straight answer on how to do it. I've already spent an hour googling this very question with little results that I understood or were helpful. I don't mean to come off rude, but it always seems hard as a programming noob to get a straight meaningful answer, I usually rather get an answer so complex I'd easily be able to solve my issue if I understood it, or someone saying why I shouldn't do what I want to do and offering no alternatives (that are helpful).

Thank you for the help!

EDIT: After reading the answers I've gotten, I see that you guys actually care and aren't just trying to spew out an answer that might work. I wanted to kill two birds with one stone (improving performance and learning some basics of multlthreading), but it appears most of the issue lies in my calculations and that threading is more hassle than it's worth for performance increases. Thank you all, I will read through your answers again and try out your solutions when I'm done with school, Thanks again!

Answer 1

What you have here is a classic O(n²) algorithm. The root cause of your problem has nothing to do with threading and everything to do with the fact that your algorithm has a high complexity.

If you haven't come across "Big O" notation before, it basically means the number of operations required to work on n elements (this is the super-simplified explanation). Your 100 elements are executing the inner part of your loop 10000 times.

In game development you generally want to avoid O(n²) algorithms, unless you have a small (and preferably fixed or capped) amount of data and a very fast algorithm.

If every entity were affecting every other entity, you would by necessity require an O(n²) algorithm. But it looks like only a few entities are actually interacting (due to if (distance < ...)) - so you could significantly reduce your number of operations by using something called "Spatial Partitioning".

Because this is a fairly detailed topic and somewhat game-specific, I recommend you ask a fresh question for more details. Let's move on...

---

One of the major performance problems with your code is fairly simple. This is freaking slow:

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

You're doing a dictionary lookup by string, every iteration (multiple times in your other loops), for an object you already have!

You could do this:

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

Or you could do this: (I personally like this better, both should be about the same speed)

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

A dictionary lookup by string is pretty slow. Iterating directly will be significantly faster.

Although, how often do you actually need to look up items by name? Compared to how often you must iterate through them all? If you only do name lookups rarely, consider storing your entities in a List (give them a Name member).

The code you actually have there is relatively trivial. I haven't profiled it, but I bet most of your execution time is going to the repeated dictionary lookups. Your code may well be "fast enough" just by fixing this problem.

EDIT: The next biggest problem is probably calling Atan2 and then immediately converting it back into a vector with Sin and Cos! Just use the vector directly.

---

Finally, let's address threading, and the major issues in your code:

First and most obviously: Don't create a new thread every frame! Thread objects are quite "heavy". The simplest solution to this would be to simply use ThreadPool instead.

Of course, it's not that simple. Let's move on to problem number two: Don't touch data on two threads at once! (Without adding the appropriate thread-safety infrastructure.)

You're basically stomping memory here in the most horrible way. There's no thread-safety here. Any one of the multiple "gravity.Update" threads you are starting can be overwriting data being used in another thread at unexpected times. Your main thread, meanwhile, will no doubt be touching all these data structures as well. I would not be surprised if this code produced hard-to-reproduce memory access violations.

Making something like this thread safe is difficult and can add significant performance overhead such that it is often not be worth the effort.

---

But, seeing as you asked (not so) nicely about how to do it anyway, let's talk about that...

Normally I'd recommend starting out by practising something simple, where your thread is basically "fire and forget". Playing audio, writing something to disk, etc. Things get complicated when you have to feed the result back into the main thread.

There are basically three approaches to your problem:

1) Put locks around all the data that you use across threads. In C# this is made fairly simple with the lock statement.

Generally you create (and retain!) a new object specifically for locking to protect some set of data (it is for safety reasons that generally only come up when writing public APIs - but good style all the same). You must then lock your lock object everywhere you access the data it protects!

Of course, if something is "locked" by one thread because it is in use, and another thread tries to access it - that second thread will then be forced to wait until the first thread is finished. So unless you carefully select tasks that can be done in parallel, you'll basically be getting single-threaded performance (or worse).

So in your case, there's no point in doing this unless you can architect your game such that some other code runs in parallel that won't be touching your entity collection.

2) Copy the data into the thread, let it process, and then take the result out again when it's finished.

Exactly how you implement this will depend on what you are doing. But obviously this will involve a potentially expensive copy operation (or two) that in many cases will be slower than just doing things single-threaded.

And, of course, you still have to have some other work to do in the background, otherwise your main thread will just be sitting around waiting for your other thread to finish so it can copy the data back!

3) Use thread-safe data structures.

These are a fair bit slower than their single-threaded counterparts and often harder to use than than simple locking. They can still exhibit the problems of locking (reducing performance down to a single thread) unless you use them carefully.

---

Finally, because this is a frame-based simulation, you'll need to have the main thread wait for other threads to provide their results, so that frame can be rendered and simulation can continue. A full explanation is really too long to put in here, but basically you'll want to learn how to use Monitor.Wait and Monitor.Pulse. Here is an article to start you off.

---

I know I haven't given specific implementation details (except that last bit) or code for any of these approaches. First of all, there would be a lot to cover. And, secondly, none of them are applicable to your code on its own - you need to approach your entire architecture with a look towards adding threading.

Threading won't magically the code you have there any faster - it just lets you do something else at the same time!

Answer 2

Ok at first glance there are some things you should try out. At first you should try to reduce your collision checks, you can do this by using some kind of spatial structure like a quadtree. This will allow you to reduce the second foreach count, as you will only query entities close the first one.

Regarding your threading: Try not to create a thread every Update turn. This overhead is maybe slowing your down more than its speeding things up. Instead try creating a single collision thread and let it do the work for you. I have no concrete copy-paste-this-code approach, but there are articles about thread syncronising and background worker for C#.

Another point is that in the foreach loop you don´t need to do entityEngine.Entities[e.Key].Texture because you already accessed the dict in your foreach header. Instead you can just write e.Texture. I don´t really know about the impact of this, just wanted to let you know ;)

One last thing: At the moment you are double checking every entity, because it gets queried in the first AND the second foreach loop.

Example with 2 entities A and 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

While this is a possible approach, maybe you can handle A and B in one turn, skipping half of your collision checks

Hope this gets you started =)

PS: Even if you said you dont want to hear it: Try to keep the collision detection in the same thread and just speed it up enough. Threading it seems like an good idea but with this comes the need to synchronise like hell. If you collision check is slower than your update (reason for threading it) you WILL get glitches and errors, because collision will trigger after ships moved already and vice versa. I don´t want to discourage you, this is just a personal experiene.

EDIT1: Links with QuadTree tutorial (Java): http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Answer 3

Honestly, the first thing you should do is switch to a better algorithm.

Parallelizing your simulation can, even in the best possible case, speed it up only by a factor equal to the number of CPUs × cores per CPU × threads per core available on your system — i.e. somewhere between 4 to 16 for a modern PC. (Moving your code to the GPU can yield much more impressive parallelization factors, at the cost of extra development complexity and a lower per-thread baseline computation speed.) With an O(n²) algorithm, like your example code, this would let you use from 2 to 4 times as many particles as you currently have.

Conversely, switching to a more efficient algorithm could easily speed up your simulation by, say, a factor of 100 to 10000 (numbers purely guesstimated). The time complexity of good n-body simulation algorithms using spatial subdivision scales roughly as O(n log n), which is "almost linear", so that you could expect almost the same factor of increase in the number of particles you can handle. Also, that would still be using only one thread, so there would still be room for parallelization on top of that.

Anyway, as the other answers have noted, the general trick to efficiently simulating large numbers of interacting particles is to organize them in a quadtree (in 2D) or an octree (in 3D). In particular, for simulating gravity, the basic algorithm you want to use is the Barnes–Hut simulation algorithm, in which you store the total mass (and the center of mass) of all the particles contained in each cell of your quad/octree and use that to approximate the average gravitational effect of the particles in that cell on other, distant particles.

You can find plenty of descriptions and tutorials on the Barnes–Hut algorithm by Googling for it, but here's a nice and simple one to get you started, while here's a description of an advanced implementation used for GPU simulation of galaxy collisions.

Answer 4

Another optimization answer that has nothing to do with threads. Sorry about that.

You're calculating the Distance() of every pair. This involves taking a square root, which is slow. It also involves several object lookups to get the actual sizes.

You can optimize this using the DistanceSquared() function instead. Precalculate the maximum distance at which any two objects can interact, square it, and then compare this with the DistanceSquared(). If and only if the distance squared is within the maximum, then take the square root and compare it with the real object sizes.

EDIT: This optimization is mostly for when you're testing for collisions, which I now noticed is not actually what you're doing (though you surely will at some point). It may still be applicable to your situation though, if all the particles are of similar size/mass.

Answer 5

I don't know much about threading, but it seems like your loops are time consuming, so maybe changing from this

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

  object_i += force(object_j);

to this

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

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

could help

Answer 6

If you already have such huge problems with 10 simulated objects, you'll need to optimize the code! Your nested loop would cause only 10*10 iterations of which 10 iterations are skipped (same object), resulting in 90 iterations of the inner loop. If you only achieve 2 FPS, this would mean that your performance is so bad, that you only achieve 180 iterations of the inner loop per second.

I suggest you to do the following:

1. PREPARATION/BENCHMARKING: To surely know that this routine is the problem, write a small benchmark routine. It shall execute the Update() method of the Gravity multiple times for e.g. 1000 times and measure it's time. If you want to achieve 30 FPS with 100 objects, you should simulate 100 objects and measure the time for 30 executions. It should be less than 1 second. Using such a benchmark is needed to do reasonable optimizations. Else you will probably achieve the opposite and make the code run slower because you just think it must be faster... So I really encourage you to do this!

2. OPTIMIZATIONS: While you cannot do much about the O(N²) effort problem (meaning: calculation time increases quadratically with number of simulated objects N), you can improve the code itself.

   a) You use a lot of "associative array" (Dictionary) lookups within your code. These are slow! For example entityEngine.Entities[e.Key].Position. Can't you just use e.Value.Position? This saves one lookup. You do this everywhere in the whole inner loop to access properties of the objects referenced by e and e2... Change this! b) You create a new Vector inside the loop new Vector2( .... ). All "new" calls implicate some memory allocation (and later: deallocation). These are even much slower than lookups of Dictionaries. If you only need this Vector temporarily, so allocate it outside of the loops AND -reuse- it by reinitializing its values to the new values instead of creating a new object. c) You use a lot of trigonometric functions (e.g. atan2 and cos) within the loop. If your accuracy doesn't need to really really exact, you might try to use an lookup table instead. To do this you scale your value to a define range, round it to an integer value and look it up in a table of pre-calculated results. If you need help with that, just ask. d) You often use .Texture.Width / 2. You can pre-calculate this and store the result as .Texture.HalfWidth or -if this is always an even positive integer value - you can use bit the shift operation >> 1 to devide by two.

Do only one of the changes at a time and measure the change by the benchmark to see how it effected your runtime! Maybe one thing is good while the other idea was bad (even I did propose them above!)...

I think these optimizations will be much better than trying to achieve better performance by using multiple threads! You'll have much trouble to coordinate the threads, so they will not overwrite the others values. Also they will conflict when accessing similar memory regions too. If you use 4 CPUs/Threads for this job, you could expect only a speed up of 2 to 3 for the frame rate.

Answer 7

Are you able to rework it without the object creation lines?

Vector2 Force = new Vector2();

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

if perhaps you could place the force value into the entity instead of creating two new objects each time, it may help to improve performance.