Aargh, a conversation with my partner on this project and it seems I overlooked something... The memory footprint if I make the grid spacing as tight as it needs to be for reasonably accurate detection would be many megabytes by my estimate. I'm thinking of ways to improve that.

While all of the above are well established methods (N being a classic example), all I would say is be careful not to prematurely optimise.

If you have a very simple AABB check that just returns true or false and does not try to compute an intersecting rectangle, and as long as you only compare unique pairs in your broadphase, the number of AABB tests you can perform each frame is pretty huge on a modern computer.

The advantages are that the code is far simpler, there are no restrictions on object size and there is no additional memory usage.

Unless you are talking about insane numbers of objects, I'd seriously recommend profiling your approach against a broadphase that just does an AABB check on each unique pair to generate the narrow phase list to check that you are gaining anything from the above complexity, since you do lose in some respects.

My experience with a fairly large number objects was that the simpler approach was faster, although this is purely anecdotal as I don't have any profiling data available.

Quote:Original post by medevilenemy
Aargh, a conversation with my partner on this project and it seems I overlooked something... The memory footprint if I make the grid spacing as tight as it needs to be for reasonably accurate detection would be many megabytes by my estimate. I'm thinking of ways to improve that.

How big of a grid and game world are you considering?

To achieve megabytes, that would mean, around 1024 x 1024 cells, which is HUGE! A cell would be between 16 to 64 pixels wide, that's a 16,000 x 64,000 playing area (if you want to consider off-screen collisions). Grids don't have to be tight. In fact, too tight and it will impact on performance quite a lot.

Storing pointers, that's 4 megabytes, just for the bucket lists. with a coverage of 1 cell average per objects, a 100,000 objects (including tiles), a 40 bytes in size, that's around 4 megabytes. All in all, 8 megabytes would be for a very large playing area. It is a large amount of memory just for collision detection, I'll admit! But that's a pretty big case.

Whenever you want to partition 100,000 objects, it's gonna take up some memory.

Quote:
Unless you are talking about insane numbers of objects, I'd seriously recommend profiling your approach against a broadphase that just does an AABB check on each unique pair to generate the narrow phase list to check that you are gaining anything from the above complexity, since you do lose in some respects.

My experience with a fairly large number objects was that the simpler approach was faster, although this is purely anecdotal as I don't have any profiling data available.

I'd consider that for a small scale app, at least for dynamic objects. I'd partition the static world in some way though. It does grows exponentially with the number of objects you want to consider, so it has to be limited in scope.

In the (unoptimised) example I provided, It does 400 dynamic bodies in 1/2 a millisecond on a modern CPU (1500 - 2000 fps), that includes, updates, broadphase, one raycast and one area query. So that's not too bad for a first pass. It will also scale linearly with the number of objects, and static objects will have very little impact on performance (since they don't move, and shouldn't be considered for broadphase queries).

Wow, perhaps I have been grossly miscalculating memory use. I'm thinking there will be a maximum of perhaps a couple hundred "collide-able" objects at any given time spread out over a few screen sizes worth of stage area. I was calculating the [very] rough memory footprint as follows:

Given the variable sizes of objects, and the fact that objects do not move tile to tile, but rather smoothly across the stage, I figured the safest way to make collision detection accurate (in the worst case where a single object is sitting right on the border between two "grid blocks") is to set the grid spacing fairly tight. Very roughly estimating the smallest typical size of an object at perhaps 10% of the screen width, the grid spacing should be no more than perhaps 1/4 of that (so that in the worst case, the deviation will only barely be visible on most screens)... so about 1/40th of a screen width. My perspective is set up for 1 screen width = 2.0 units... so, grid spacing is 2.0/80 or 1.0/40. My partner estimated 7-10 screen widths/heights worth of map between loads, so I need roughly 80 * 10 blocks in either dimension for a total of 800*800 = 640000 total blocks. Using linked lists of ints (not pointers at the moment), estimating each list element to take roughly 2Bytes (sizeof(int) -- this isn't quite accurate for the size of a node, but it is just a rough estimate anyway) and in the worst case perhaps 3/4 of grid blocks will have a resident... (probably less) yields... 640000 * 2Bytes * 0.75 = 960000Bytes = 937.5 Kilobytes. That's not that bad. It gets really ugly really fast if I need to tighten up the grid spacing, though... but it definitely seems like my estimates late last night were horribly wrong.

Thanks again for the insight, everyone!

[Edited by - medevilenemy on June 10, 2009 10:05:30 AM]

Unfortunately, my compiler crashes every time it gets to the line where I declare my grid itself: list<int> thegridproper[800][800]; It can't seem to deal with array indices that large. It appears the large indices are causing cc1plus.exe to crash -- maybe an overflow of its stack? not sure how to fix.

I'm really trying to avoid adding more overhead to my program, so if there is a relatively native (or STL since I'm already using that) way to do it, I'd prefer that. I'll look into boost, though.

Heh, I was referring to compiling in more libraries, most of the functionality of which I won't use... but I don't know boost. I'm looking into it now. Thanks for the suggestion.