Sign in to follow this  
medevilenemy

Collision Detection in a 2D environment

Recommended Posts

For the project I've been working on the past couple weeks, I'm working on a method of space partitioning to speed collision detection between objects. I've been thinking about using a grid partitioning system of some sort. Objects are not necessarily of the same size, so I was thinking of setting the grid size rather small. the UID (unique identifier) of a particular object would be placed into a list of UIDs for each grid block the object intersects. To check for collisions, simply check the blocks within and perhaps immediately surrounding an object for other UIDs. This method, however, seems to have a number of issues. 1) Very small blocks would be necessary to provide adequate precision. This requirement would yield a very large grid which would likely take up a lot of memory. 2) I haven't managed to devise any efficient way to update the grid. For example, when an object moves blocks it is no longer in need to be informed of that, and blocks it has entered need to be informed as well. However, doing so would seem to require a full traversal of the grid OR storing a list of references to grid blocks within objects themselves (which might be a bit troublesome). I am thinking the system may benefit from a full redesign... What do you all think would be an appropriate method?

Share this post


Link to post
Share on other sites
download box2d, use it.
(http://www.box2d.org)

or, use axis separation. nice and easy for broad-phase collision.

Share this post


Link to post
Share on other sites
Sweep and Prune is another alternative.

Quote:

1) Very small blocks would be necessary to provide adequate precision. This requirement would yield a very large grid which would likely take up a lot of memory.

The cells don't have to be small. Roughly the size of your objects (if you have a tile map, ideally, you'd want cells to be the size of the tile).

Quote:

2) I haven't managed to devise any efficient way to update the grid. For example, when an object moves blocks it is no longer in need to be informed of that, and blocks it has entered need to be informed as well. However, doing so would seem to require a full traversal of the grid OR storing a list of references to grid blocks within objects themselves (which might be a bit troublesome).


Nope, you can use a mapping function, to find the cells coordinates that are covered by an object's bounding box.

Share this post


Link to post
Share on other sites
My graphics engine is "tiled" only in that it will be rendering the environment out of a large series of discrete blocks, but these blocks have no standard size. Therefore, I figured it would be safest (from a precision standpoint) to use a smaller grid size to hopefully better fit the varying sizes of objects. Because of the way I have set up the stage, a mapping function between stage coordinates and grid coordinates is very simple (its basically (int)((StageCoord+1)*10)). So, at least I'm that far along, but I'm not certain how to clean out unneeded entries (lets say a block moves from coords 0,1 and 0,2 to 0,2 and 0,3... the 0,1 entry needs to be deleted) efficiently.

I will look through the project you linked later today... sorry, been a bit busy with work. Thanks for the help!

Share this post


Link to post
Share on other sites
I just use a single-linked list for each cell, listing all the objects' bounding box that intersect that cell. The list is not sorted, but the number of objects covering a single cell should be very small (from one to under half a dozen, although there is no restriction on that number).

It's not efficient, but it's not too bad. I've also tried a hashmap (with a custom boost allocator) for each cell, for faster insertion / removal, but it increases the memory footprint.

I use a static allocator to allocate nodes for the lists, you don't want to do a new / delete everytime an object moves. If the allocator runs out of memory, I dynamically allocate memory for nodes. A better way to do this is to have a dynamic allocator that can grow in size, but you'll need to reference your nodes using indices, not pointers.

Since most objects would move relatively slowly compare to the grid granularity, I only move and add nodes to the newly covered / uncovered cells.

I suppose an optimisation would be to have sorted, double linked lists lists for each cells.

Also, given the wide variety of objects that a game can have (a static tile, a player bullet, an enemy bullet, a player, a NPC, ect...), it can be faster to have several maps on top of each other, so you don't end up doing needless bullet-bullet tests, or testing for collisions between two static tiles (which would be pointless). So in theory, you could put all the bullets into one map, all the NPCs into one map, so you can test bullets vs NPC slightly more efficeintly, at the expense of more memory usage.

I put everything into one map, and I use bitmasks to masks types of objects from others, so for example, a bullet can reject tests against other bullets (unless you want to be able to shoot bullets).

I also added a raycast query, to give a list of objects that intersect a segment. If your player fires fast, pixel-size bullets, converting the bullet path into a raycast would be a solution.

In general, there are three basic queries for collision detections.

1. raycast query (objects's bounding boxes intersecting a ray)
2. area query (objects' bounding box intersecting a rectangular area).
3. pairwise collisions (list all pairs of objects with their bounding box intersecting).

all these also use the 'collidable' bitmask filter, to filter out unwanted object types.

One problem with sweep and prune is the raycast/area query. Usually, it's pretty bad with long diagonal raycast, or large rectangular areas.

Share this post


Link to post
Share on other sites
Alright, your method is similar to what I had in mind but has helped me refine it somewhat (though my method is admittedly less robust). I am now thinking of having a two dimensional array of static size of singly linked lists. These linked lists would contain pointers to any objects that spill into them (though I might use an objects UID instead of a reference to it). Collision queries would work by basically passing the collision detector function your location... it would convert your location into grid coordinates, then return a list of UIDs of all the objects that either intersect or immediately border the current object (not sure precisely on that one). Once I have the UIDs of the collided objects, I can issue the appropriate commands through my internal messaging system.

As for updating the grid after something moves... that is a bit trickier. I'm thinking perhaps I should give each object a list of the coordinate pairs of the grid blocks it spills into. When I need to update, I'd have to determine the differences between the new location list and the old stored list, and tell the members of the old list to remove their references. (nothing more needs to be done for the newly occupied blocks, since the design for the linked lists would allow only one entry from a single object within it. The problem with this update method (besides memory footprint -- which would be somewhat significant, lets call it a few hundred bytes) is it is fairly slow. The update operation would have a roughly double-linear operation time. This isn't so good.

Share this post


Link to post
Share on other sites
Quote:

As for updating the grid after something moves... that is a bit trickier. I'm thinking perhaps I should give each object a list of the coordinate pairs of the grid blocks it spills into. When I need to update, I'd have to determine the differences between the new location list and the old stored list, and tell the members of the old list to remove their references. (nothing more needs to be done for the newly occupied blocks, since the design for the linked lists would allow only one entry from a single object within it. The problem with this update method (besides memory footprint -- which would be somewhat significant, lets call it a few hundred bytes) is it is fairly slow. The update operation would have a roughly double-linear operation time. This isn't so good.


What I store in the object, is the cells covered by it, in the form of a rectangular area (minx, miny, maxx, maxy), which is basically cell indices along the x and y axis.

When an object moves, his area would change. Both the old and new area can potentially intersect. It means that the area shared does not need to be updated. You only need to remove references to the old portions not covered anymore, and add references to the new portions.



// remove object from the grid.
bool Grid::unmapObject(Object* object, const CellArea& newArea)
{
if(!object->m_cellArea.valid())
return false;

for(int i = object->m_cellArea.m_minx; i < object->m_cellArea.m_maxx; i ++)
{
for(int j = object->m_cellArea.m_miny; j < object->m_cellArea.m_maxy; j ++)
{
if(i >= newArea.m_minx && i < newArea.m_maxx && j >= newArea.m_miny && j < newArea.m_maxy)
continue;

Cell* c = cell(i, j);

c->remove(m_nodes, object);
}
}
return true;
}

// insert object into the grid
bool Grid::mapObject(Object* object, const CellArea& newArea)
{
if(!newArea.valid())
return false;

for(int i = newArea.m_minx; i < newArea.m_maxx; i ++)
{
for(int j = newArea.m_miny; j < newArea.m_maxy; j ++)
{
if(i >= object->m_cellArea.m_minx && i < object->m_cellArea.m_maxx && j >= object->m_cellArea.m_miny && j < object->m_cellArea.m_maxy)
continue;

Cell* c = cell(i, j);

c->add(m_nodes, object);
}
}
object->m_cellArea = newArea;
return true;
}



anyway, there is room for optimisations.

Another method I've heard about is Dynamic Sphere Trees (John Ratcliff), in the Games Programming Gems 2. The method looks good (both in speed, feature set, flexibility, and also extends to 3D), I haven't played with it yet, and I don't know how good it actually performs.

Share this post


Link to post
Share on other sites
Similar to what I had in mind, but rather more elegant. Many thanks. I'll try to code up my implementation and update the thread ([grid] or complain if I run into trouble)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by medevilenemy
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 haven't read the entire thread, but trying to create an array of that size on the stack could cause problems, I would think. Try allocating from the free store instead (I'd also recommend using boost::multi_array for this rather than a raw 1-d or 2-d array).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
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.
What kind of overhead are you talking about? Run-time? Compile-time?

Anyway, if you don't want to use multi_array for some reason, you can just use std::vector (perhaps with a simple wrapper to facilitate 2-d indexing).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Heh, I was referring to compiling in more libraries, most of the functionality of which I won't use...
I see.

Just as a heads up (since you're looking into Boost), the Boost download is quite large, but in general, you only pay for the parts of it that you actually use. So, if you only need multi_array, you just include the corresponding header and you're good to go. (Some of the libraries require building and linking, but the majority of them - including multi_array - are header-only.)

There can be some compile-time overhead due to heavily templated code and/or deep inclusion trees, but I wouldn't worry about it unless you actually notice a problem. In general, most of the tools that come with Boost are well worth any minor additional overhead that they might incur.

Share this post


Link to post
Share on other sites
Haha, I see what you mean about the download being large -- though its the extraction process thats really the big part. But it seems to be fairly simple anyway. I should be able to drop it in without having to change much. JYK, one again, your insight is invaluble. [grin]

[edit]
Wow, it really does add to compile time... about an extra 5 seconds.

Share this post


Link to post
Share on other sites
Quote:
Wow, it really does add to compile time... about an extra 5 seconds.
I'm just curious - what seems to have added the 5 seconds exactly? Was including the multi_array header in one of your files the only change you made?

Five seconds sounds a little suspicious to me - maybe something else changed between compiles? (Of course it's hard to say for sure without actually seeing the project...)

Share this post


Link to post
Share on other sites
Sorry, you're right, it really didn't add all that much... It went really slowly for one build -- don't know why. But its back to normalish now.

I am, however, having trouble making it give me an array of linked lists through std::list (as in a two dimensional array of lists of ints)

[edit] nope, its not that I'm making an array of lists, its that I was trying to declare it in the private: section of my class definition... looking for a workaround.

Share this post


Link to post
Share on other sites
Ok, I got it. I got around the error by declaring the array itself in the public section and setting its extents in the generic constructor for the class. Once again, thanks jyk.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this