Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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!

share|improve this question
    
What does it [Your update threading system outlined above] do now (does it work)? Btw I'd start it ASAP in the game cycle - eg before the entities are updated. –  ThorinII Nov 7 '13 at 7:58
2  
The Trig calls in the interior of your nested loops are probably the biggest hit. If you can find a way to eliminate them, that'll reduce the k of this O(n^2) problem a lot. –  RBarryYoung Nov 7 '13 at 14:44
1  
Indeed the trig calls are completely unnecessary: you first calculate an angle from a vector, then use that to generate another vector that points in the given direction. Then you normalise that vector, but since sin² + cos² ≡ 1 it is already normalised anyway! You could just have used the original vector that connects the two objects you're interested in, and normalised this one. No trig calls whatsoever needed. –  leftaroundabout Nov 8 '13 at 20:08
    
thanks, I figured this out yesterday, felt so stupid! –  Postman Nov 9 '13 at 4:58
    
Isn't XNA deprecated? –  akled Nov 12 '13 at 19:08
show 3 more comments

7 Answers

up vote 34 down vote accepted

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!

share|improve this answer
8  
+10 if I could. Maybe you can move the last sentence to the top as an introduction, because it summarizes the core issue here. Running code on another thread doesn't magically speed up rendering if you don't have anything else to do at the same time. And the renderer probably waits for the thread to finish but if it does not (and how could it know?) it will be drawing an inconsistent game state with some entity physics still to be updated. –  LearnCocos2D Nov 7 '13 at 10:39
    
I am thoroughly convinced threading is not what I need, thank you for the lengthy and knowledgeable information! As for the performance improvements, I made the changes you (and others) suggested, but I am still getting bad performance when dealing with > 60 objects. I think it would be best for me to make another question more focused on N-Body simulation efficiency. You get my answer for this, though. thanks! –  Postman Nov 8 '13 at 0:29
1  
You're welcome, glad it helped :) When you post your fresh question, please do drop a link here so that I, and anyone else following along, will see it. –  Andrew Russell Nov 8 '13 at 4:54
    
@Postman While I agree with what this answer says in general, I think it completely misses the fact that this is basically the PERFECT algorithm to take advantage of threading. There is a reason they do this stuff on the GPU and it is because it is a trivially parallel algorithm if you move the writes into a second step. There is no need for locking or copying or thread safe data structures. A simple Parallel.ForEach and its done with no issues. –  Chewy Gumball Nov 8 '13 at 9:07
    
@ChewyGumball A very valid point! And, while Postman would have to make his algorithm two-phase, it arguably should be two-phase anyway. It is worth pointing out, though, that Parallel is not without overhead, so it's definitely something to profile - particularly for such small data sets and (what should be) a relatively fast piece of code. And, of course, it's still arguably better to reduce the algorithm complexity in this case - rather than simply throwing parallelism at it. –  Andrew Russell Nov 8 '13 at 11:33
show 2 more comments

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/

share|improve this answer
9  
The nice thing about using quad/octrees for gravity simulation is that, instead of just ignoring distant particles, you can store the total mass and the center of mass of all particles in each branch of your tree and use this to calculate the average gravitational effect of all the particles in this branch on other, distant particles. This is known as the Barnes-Hut algorithm, and it's what the pros use. –  Ilmari Karonen Nov 7 '13 at 12:22
    
Interesting read, thank you –  floAr Nov 7 '13 at 13:10
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Yeah. This solution might be fine (negligible accuracy loss only), but gets into trouble when the mass of objects differs a lot. If the mass of some objects is very huge while some objects mass is very small, the maximum distance for reasonable is higher. E.g. the effect of the earth gravity on a small dust particle is negligible for the earth, but not for the dust particle (for a quite big distance). But in fact two dust particles at the same distance do not significantly influence each other. –  Stefan K. Nov 7 '13 at 16:21
    
Actually that's a very good point. I misread this as a collision test, but it's actually doing the opposite: particles influence each other if they're not touching. –  Alistair Buxton Nov 7 '13 at 18:42
add comment

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

share|improve this answer
1  
why would that help? –  user25712 Nov 9 '13 at 15:38
1  
Because first two loops make 10 000 iterations, but second loops make only 4 950 iterations. –  Buksy Nov 9 '13 at 17:45
add comment

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.

share|improve this answer
4  
Vector2 in XNA is a value type. It has no GC overhead and the construction overhead is negligible. This isn't the source of the problem. –  Andrew Russell Nov 7 '13 at 6:48
    
@Andrew Russell: I'm not that sure, but is that really still the case if you use "new Vector2"? If you use Vector2(....) without "new", this would be probably different. –  Stefan K. Nov 7 '13 at 16:13
1  
@StefanK. In C# you can't do that. Needs the new. Are you thinking of C++? –  MrKWatkins Nov 7 '13 at 16:25
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.