Elysian Shadows

I have a program that i ran in a profiler and 30% of the entire code is in one function. It is really slowing down the program and thought maybe there is a much better way to code this. The program is in XNA. I am running collision detection using spacial hashing and this update function is from updating the grid.


the function it calls inside of itself (handlecollide) isnt spending much time itself, 30% is all just in the for+foreach statements. There has to be a better way to code this. Bucketlist count is usually around 3 or 4 and count is around 200-400.

this is how I am declaring the variables the problem is i can only get about 400 enemies on screen before it starts lagging, and thats on PC, on 360 it starts slowing up with 5 or 10! can you notice any common mistakes or maybe something that would help speed up this function a bit??
thanks guys,

do a printout of how many are in the bucket, and how many times the foreach is being called, it might just be that the hashing is not fine enough, and you are doing all 400 against each other.

also, you might wanna look into a quadtree.

avansc wrote:do a printout of how many are in the bucket, and how many times the foreach is being called, it might just be that the hashing is not fine enough, and you are doing all 400 against each other.

The buckets are fine I have the bucket 'grid' at 64x64 with the objects in the game being the same size. The amount in each bucket has looked fine and i switched out foreach a little bit ago due to the fact that for is faster. i saw a little big of performance increase, but nothing drastic

avansc wrote:also, you might wanna look into a quadtree.

lmao, I literally spent 2 weeks optimizing a quad tree for my program needs to its peak and in the course became fairly familiar with them, haha. The maximum efficiency from a quadTree is O(NlogN) for N objects while a hashing technique is O(N) with a cell query of O(1) and an object query of O(N), as you can see this can be extremely more efficient. Especially with hundreds of dynamic objects restructuring the tree each frame, the quadtree is not ideal in this situation.

I used a couple other profilers (intel's Amplifier) and it says that most of the time is rendering the draw function so now I don't know where to keep my focus, becoming very frustrating. Hmmm.... Tomorrow I will try and see if optimizing the graphics device coding does anything.. although all profilers say a good amount of time is spend chugging in the grid.update function.

thanks avansc for the response

yeah i got yah, well just keep at it.

Ive done things like this with quad trees that have worked out pretty well.

you can structure things that, what you call your bucket cell query being O(1), be the same in a quad tree.
you have a kind of temp list of all your unchecked entities, then you start looping through this list, each entity has a reference to the current node it occupies in the QT, so then you just check for collisions in those objects that occupie that node, and you remove all those entities from your temp list, then just keep looping through the list and doing that kinda deal. your list shrinks pretty quickly. also, you really dont need to reconstruct a tree each frame. you just need to propagate a entity up the tree and back down, at worst case.

but the spatial hashing should work fine, its best to first be 100 percent sure what is eating your cycles up. are you using immediate mode or whatever its called in DX?

avansc wrote:yeah i got yah, well just keep at it.

Ive done things like this with quad trees that have worked out pretty well.

you can structure things that, what you call your bucket cell query being O(1), be the same in a quad tree.
you have a kind of temp list of all your unchecked entities, then you start looping through this list, each entity has a reference to the current node it occupies in the QT, so then you just check for collisions in those objects that occupie that node, and you remove all those entities from your temp list, then just keep looping through the list and doing that kinda deal. your list shrinks pretty quickly. also, you really dont need to reconstruct a tree each frame. you just need to propagate a entity up the tree and back down, at worst case.

but the spatial hashing should work fine, its best to first be 100 percent sure what is eating your cycles up. are you using immediate mode or whatever its called in DX?

nope, not using dx
yeah after doing a bit more research on xna forums, it sounds like it is gpu bound. Also I will have to check garbage collection and see what kind of numbers I get from there. if all of this fails im going to have to put the project together piece by piece this weekend, see where it starts encountering problems, which sounds extremely fun

oh last post i forgot to put this pic up shows some of the hotspots in the code:


1 by EdBoon, on Flickr

On a DX graphics device, which is what an XNA device fundamentally is, spending excessive amounts of time in Present is not indicative of being inefficient graphically. Precisely the opposite normally. Now, I do stress "normally". Without anymore code or a more worthwhile profile it'd be difficult to say. However, more times than not if you're spending ridiculous amounts of time in Present it means that your CPU is at least several frames ahead of your GPU and you're stalling it. This isn't to say that your draw calls are expensive, this may or may not be the case. If the complexity of all the tasks within your main loop aren't too terribly deep, then it can simply mean that you're sitting in a "busy-wait" loop. Eg: You're not handling the case where attempting to present when the GPU is excessively busy.

With DX devices, and I'm sure XNA is no different here, invoking Present on a device that is busy will raise an error that indicates the GPU is busy. Since Present operates asynchronously you're free to do whatever you wish here, further game processing or whatever. This is part of the beauty of that pipeline is that you can offload tasks to the CPU while you're stuck in that busy-wait loop. You'll never be faster than your slowest piece of the pipeline so you may look at metering your application (eg: slowing it down so that you don't end up with this massive disparity in CPU/GPU wait time) or you may look at perhaps doing some preprocessing on some number of frames ahead while you're waiting. The GPU is going to take a certain amount of time regardless if the application is even relatively efficient in terms of graphics API code, so you can just always count on this. With very simple applications with a lack of very in-depth game logic, it's very common to see this busy-wait cycle going on and on because the game logic simply doesn't consume enough time so it goes ahead and fills up the command buffer of the GPU very very quickly so you end up waiting every frame for retarded amounts of time. (In this case it's Present). This is primarily the case if you've got triple buffering going on (VSync). If this is the case you should look at the PRESENT flags and see if there's one that will allow you to go off and do something else if its busy, normally D3DPRESENT_DONOTWAIT. A simple test may be to FORCE the device to update whether its ready or not (which may cause tearing) but may reveal something about what's going on. This flag is normally D3DPRESENT_INTERVAL_IMMEDIATE.

So this is based ONLY on the indications from VTune. It may turn out that an instrumented profiler turns up something more meaningful and reveals a problem elsewhere that is manifesting itself similarly. I can't be sure. Either way, as you're no doubt seeing...balancing the GPU and CPU load is QUITE paramount and the usage of a good code profiler is absolutely critical.

A more meaningful examination is not inclusive time, which is what you're looking at. You'll want to look at frame time. See if PIX isn't available for XNA devices or if there is an XNA GPU profiler available similar to DX's PIX profiler available to you, it will give you time spent rendering a single frame and dissect the draw calls and their time. This is a MUCH more meaningful time, as you can average this out over the course of however much time your CPU is spent spinning around in there and determine who's doing the bulk of the work. There you can see if there's any room for optimization of the GPU code.

you were right, i did some checks and it is cpu bound not gpu, which does not make me happy because my methods to try and get things more efficient were not making much of a difference. Although I did spend most the night looking for things that could be simplified or avoided calling methods, and i got about 10x more efficient, but thats not saying much cuz i was only at 25 guys before I noticed delay. Now I am up to 250, but still well short of my goal of 1000. I guess I will keep trying to trim down my collision detection although it seems pretty simple to me. The thing with xna and the 360 is that it handles code so much differently and there are certain little things that it does not handle well, on pc i can get tons of enemies.

Well thats good though because effective code profiling is going to save you TONS of time and if you can make sense of it will bring you to what REALLY makes for efficient code instead of making presumptions about what makes efficient code. The results are commonly very surprising

This is part of what I try to preach to people. Just make the damn thing work, then examine the inefficiencies. There in a pipelined architecture you're only going to be as fast as your slowest stage. If you're stuck in post processing, there's not a DAMN thing you can do on the CPU to make it run faster. If you're stuck on the CPU, no amount of graphics trickery will make it run faster than the slowest CPU processing time. So its pointless to optimize code if you aren't sure where the bottlenecks really are.

Very good, indeed.