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 e in entityEngine.Entities)
{
Vector2 Force = new Vector2();
foreach (KeyValuePair 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 Entities = new Dictionary();
public Gravity gravity;
private Thread T;
public EntityEngine()
{
gravity = new Gravity(this);
}
public void Update()
{
foreach (KeyValuePair 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
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 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 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!
No comments:
Post a Comment