2d collision detection
Author
I am at the point I need to do collision detection in my game. I will have a lot of sprites, upwards of 500, and every one of them needs to check collision against the other. Now I dont want an n^2 situation here, so I started thinking about appropriate data structures, such as one of the many partitioning trees. Just for the hell of it I would see how well my little structure would work. I doubt its that original, but if it is more efficent that a tree it would be nice. I am not sure it is, but what do you think? By efficent, I mean both speed and memory. Also, coordinates maximums are the max size of float.
So here is what my code does (I prototyped it in ruby. havent written it in game yet. Similar to hash table): It divides the whole world into divisions of 100x100. It does this in a virtual method, so it doesnt need to store every division.
For every sprite that collision detection is needed, a linear address is calculated from it's x, y coordinates, exactly how a pixels address is calculated. The only difference is the x and y are divided by 100 first, to determine which grid section the sprite is in: addr = (sar[0]/100) + ((sar[1]/100) * 100000). 100000 is an arbitrary universe width, just for example. I then map that number to be less than 1024: mapped_addr = addr % 1024. 1024 is the maximum # of sprites. In an array, mapped_addr is used as an index to a small array (perhaps a vector). If the sprite's calculated addr is in the nested array, it means a previous sprite who is in that block was already added. In that case, do collision detection for that block. If the addr was not in the nested array, then add it.
If I made that clear, then it should be obvious that this method will only test collisions in 100x100 blocks with more than 1 sprite. And it will only tesgt the sprites in that block. So there are some n^2 elements, but only on a small level. Plus I can add some optimizations, like not test bullet collisions with other bullets. Any good? Problems? Not explained well enough?
My crappy test ruby code(OH GOD THAT IS UGLY. HOW DO I USE ONE OF THOSE CODE BOXES?):
car = [] #collision array. size 1024 sprites max
sar = [[12,20],[5,30],[150,15],[300,300],[170, 16]] #sprite array
class Laddr #linear address class
attr_reader :addr
def initialize(adr)
@addr = adr
end
end
sar.length().times {|i|
addr = (sar[0]/100) + ((sar[1]/100) * 1000) #calc linear addres
mapped_addr = addr % 1024
found = 0
if car[mapped_addr] == nil then #nothing here. make it
car[mapped_addr] = [Laddr.new(addr)] #create nested array for index
else #something here. check to see if addr already here. If not, add it. If so, test it
car[mapped_addr].each {|a|
if (a.addr == addr) then #the block already is here. It means this sprite is with it
#do collision checks between sprites
found = 1 #signal that addr does not need to be added
end
}
if found == 0 then #addr was not found. push addr on
car[mapped_addr] = Laddr.new(addr)
end
end
}
Although I didn't follow all the details of the implementation, the hashed grid you describe is certainly a good approach. If you're interested in a formal treatment of this approach, other grid implementations, and other subdivision schemes (and can afford a book), check out Christer Ericson's new book on collision detection.
What about when a sprite is on the corner of the grid? Now you need to start checking surrounding cells. What if the character is bigger than the size of a single cell? Now you need to start checking two cells in all directions. A lot of redundant checking.
Look up Quad Trees. They will remove this inefficiency.
(I seem to recall having this argument at some point.)
Look up Quad Trees. They will remove this inefficiency.
(I seem to recall having this argument at some point.)
Just to clarify for the OP, quadtrees are a different, but not necessarily superior, solution than grids. They eliminate some of the problems inherent to grids, but introduce some new ones as well.
If you position your sprite in the grid by its upper-left corner, and no sprite is larger than a cell, you need only check the cells below, to the right, and to the lower right in addition to the cell in which the sprite resides. So it's not that bad.
In any case, quadtrees have similar problems. Objects can span multiple leaves (again requiring tests against multiple cells). If you instead choose to place objects higher in the tree, the number of inter-object tests can become unacceptable.
Loose quadtrees work around some of these problems (perhaps this is what grozzler was referring to), but they still require testing against multiple cells.
What kind of game are you making? Another option for you might be 'sweep and prune', which has some advantages over the aforementioned techniques.
One of the projects I'm working on right now is a generic broad-phase collision detection library. I'm writing it in 2D first, and then will build the 3D version from that. I think it will be ideal for 2D games like this. Unfortunately, it'll probably be a few months before it's finished :)
Anyway, for such a seemingly simple problem as broad-phase coldet between sprites in 2D, there are quite a few options. Again, Christer's book has a great chapter on this subject.
If you position your sprite in the grid by its upper-left corner, and no sprite is larger than a cell, you need only check the cells below, to the right, and to the lower right in addition to the cell in which the sprite resides. So it's not that bad.
In any case, quadtrees have similar problems. Objects can span multiple leaves (again requiring tests against multiple cells). If you instead choose to place objects higher in the tree, the number of inter-object tests can become unacceptable.
Loose quadtrees work around some of these problems (perhaps this is what grozzler was referring to), but they still require testing against multiple cells.
What kind of game are you making? Another option for you might be 'sweep and prune', which has some advantages over the aforementioned techniques.
One of the projects I'm working on right now is a generic broad-phase collision detection library. I'm writing it in 2D first, and then will build the 3D version from that. I think it will be ideal for 2D games like this. Unfortunately, it'll probably be a few months before it's finished :)
Anyway, for such a seemingly simple problem as broad-phase coldet between sprites in 2D, there are quite a few options. Again, Christer's book has a great chapter on this subject.
Author
I will take a look at that book. I wonder if my college has it.
Well, my sprites havea location designated by the center, as well as 4 vertexes, each representing a corner (the sprites can be rotated as well as just straight blitted). I suppose I could add each vertex to to my grid, instead of object coords. The reason I am leaning away from trees is memory overhead. My grid has a fair amount. But the universe will be gigantic, with friendly and enemy AI battling offscreen in realtime. What is this sweet and prune method. I am always open to alternative, especially simpler, solutions.
The large universe is my primary motivation for going with my hash grid idea. My memory requirments will increase with the number of sprites, not the size of the universe, which will be considerable. I should probably optimize it further, by once collision between A and B is found, it does not check collision between B and A (if possible).
Well, my sprites havea location designated by the center, as well as 4 vertexes, each representing a corner (the sprites can be rotated as well as just straight blitted). I suppose I could add each vertex to to my grid, instead of object coords. The reason I am leaning away from trees is memory overhead. My grid has a fair amount. But the universe will be gigantic, with friendly and enemy AI battling offscreen in realtime. What is this sweet and prune method. I am always open to alternative, especially simpler, solutions.
The large universe is my primary motivation for going with my hash grid idea. My memory requirments will increase with the number of sprites, not the size of the universe, which will be considerable. I should probably optimize it further, by once collision between A and B is found, it does not check collision between B and A (if possible).
If your sprites can be rotated, for the broad phase I'd just use an axis-aligned rectangle that is big enough to contain the sprite at any orientation. I wouldn't store the corner points in the grid - it's usually more useful to represent the axis-aligned rect as a min and max coordinate, or center and extents.
Is this is a space game? For any large world with a more or less uniform distribution of objects, a quadtree may be a poor choice due to memory requirements (as you noted). Same with an explicit grid.
Really, the hashed grid may be close to optimal. Sweep and prune is the only reasonable alternative that I can think of.
Sweep and prune basically *only* stores the axis-aligned bounding boxes - no grid, no tree, no cells. The trick is that the AABBs are decomposed into 1-dimensional intervals, one along each axis. The endpoints of these intervals are kept sorted by their position. Under the assumption that motion from one frame to another is relatively small compared to world size, keeping the lists sorted is actually fairly efficient.
It sounds simple, but the implementation is actually a little involved. The best reference on sweep and prune that I know of is 'Collision Detection in Interactive 3D Environments', by Gino van den Bergen. If you're interested in sweep and prune, and can't get ahold of the book, I'll be glad to give you more information about the algorithm.
Is this is a space game? For any large world with a more or less uniform distribution of objects, a quadtree may be a poor choice due to memory requirements (as you noted). Same with an explicit grid.
Really, the hashed grid may be close to optimal. Sweep and prune is the only reasonable alternative that I can think of.
Sweep and prune basically *only* stores the axis-aligned bounding boxes - no grid, no tree, no cells. The trick is that the AABBs are decomposed into 1-dimensional intervals, one along each axis. The endpoints of these intervals are kept sorted by their position. Under the assumption that motion from one frame to another is relatively small compared to world size, keeping the lists sorted is actually fairly efficient.
It sounds simple, but the implementation is actually a little involved. The best reference on sweep and prune that I know of is 'Collision Detection in Interactive 3D Environments', by Gino van den Bergen. If you're interested in sweep and prune, and can't get ahold of the book, I'll be glad to give you more information about the algorithm.
Author
It is a space game of sorts. But I would like to make it genralized to be many things. Including seamless transitions between earth and space.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement