## Collision Question

There's probably a much better article on gamasutra about this, but here's my take on the whole 2d collision problem:

-------------------------

This was written extremely quickly and not proofread, I'll come back and proofread it later today.

In almost all cases you can divide your potential collisions into two categories, map collisions and object collisions. mpa collisions are collisions with static parts of the world, object collisions are collisions with dynamic parts of the world. I'd need to know a bit more about your game to help you with the map collision. Object collision is pretty generic however, so I'll cover that in depth.

Typically, object collision in a large world (several hundred objects) consists of three discrete steps:

Culling, where distant objects are thrown out very quickly, or only close objects are concidered at all.

bounds, where a fast test is used to determine objects that have the potential to collide.

exact, which typically a comparitively expensive process for determining exact object collision information.

typical methods of Culling include:

map grid. Divide the map into a grid of large tiles. Store a list of objects intersecting each tile. Objects only needs to be tested against other objects the the tiles they intersect.

Quad-Tree. If you have a finite world, you can use quad trees to partition the world into a heirarchy of 2x2 grids. Each node in the tree stores the four lower nodes and a pointer into a list of objects at that node. To find eligible objects, pull out the object lists for all nodes the colliding object intersects. Demoing quadtrees really needs graphics, search around the web for a good tutorial

funky bsp thing. Some sort of BSP. Too complex to go into detail about.

axis-sorted object list. Keep your object list sorted by one edge of their extents (top or left is typical). You can very quickly pull out a list of other objects with overlapping x- (or y-) extents.

bounds tests are much simpler, and generally there's only two ways to do it:

circle overlap test whether the bounding circles of the two objects overlap. This can be done in only a few multiplies and adds, and only one conditional.

rectangle overlap test whether the bounding rectangles of th two objects overlap. This is much easier mathematically, but requires 4 (or 2 if you're RELALY fancy) conditionals.

the object-level collision is up to you however, but the above should help you keep it's overhead at a minimum.

-------------------------

This was written extremely quickly and not proofread, I'll come back and proofread it later today.

In almost all cases you can divide your potential collisions into two categories, map collisions and object collisions. mpa collisions are collisions with static parts of the world, object collisions are collisions with dynamic parts of the world. I'd need to know a bit more about your game to help you with the map collision. Object collision is pretty generic however, so I'll cover that in depth.

Typically, object collision in a large world (several hundred objects) consists of three discrete steps:

Culling, where distant objects are thrown out very quickly, or only close objects are concidered at all.

bounds, where a fast test is used to determine objects that have the potential to collide.

exact, which typically a comparitively expensive process for determining exact object collision information.

typical methods of Culling include:

map grid. Divide the map into a grid of large tiles. Store a list of objects intersecting each tile. Objects only needs to be tested against other objects the the tiles they intersect.

Quad-Tree. If you have a finite world, you can use quad trees to partition the world into a heirarchy of 2x2 grids. Each node in the tree stores the four lower nodes and a pointer into a list of objects at that node. To find eligible objects, pull out the object lists for all nodes the colliding object intersects. Demoing quadtrees really needs graphics, search around the web for a good tutorial

funky bsp thing. Some sort of BSP. Too complex to go into detail about.

axis-sorted object list. Keep your object list sorted by one edge of their extents (top or left is typical). You can very quickly pull out a list of other objects with overlapping x- (or y-) extents.

bounds tests are much simpler, and generally there's only two ways to do it:

circle overlap test whether the bounding circles of the two objects overlap. This can be done in only a few multiplies and adds, and only one conditional.

rectangle overlap test whether the bounding rectangles of th two objects overlap. This is much easier mathematically, but requires 4 (or 2 if you're RELALY fancy) conditionals.

the object-level collision is up to you however, but the above should help you keep it's overhead at a minimum.

"He who breaks a thing to find out what it is, has left the path of wisdom."

- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!

1) Go through each beginning and end point of each sprite and put them in a list

2) Go through this list and sort the beggining and end points from min to max value

3) For each group in this dimension repeat steps 1 and 2 in the other dimensions until the group no longer gets subdivided

so if you have a list like this after step 1...

A A | B B | C C

1 5 | 2 3 | 8 9

1 would be the min x value for the sprite A and 5 would be the max. 2 would be the min x for sprite B and 3 the max, etc.

Next you sort these values

A B B A C C

1 2 3 5 8 9

Now we find the groups. We have two groups... In group 1 we have sprites A and B, and in group two we have sprite C.

This is only on the x axis however, next you check each individual group on the y axis. Anyways, once you're done all of this you will know which sprites are colliding.

I would recommend doing a google search for more details because there are some things that could go wrong if you don't learn all the details of the algorithm.

-- Ian