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?

2D grid is an option.

The problem with grids is memory, as you pointed out. I can give you some more details if you are interested.

Sure, Thanks, I'm interested, what do you suggest?

download box2d, use it.
(http://www.box2d.org)

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

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.

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!

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.

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.

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.



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.

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)