Efficient 2D Collision Detection?

sort the trees for the x pos.
from the smallest (0) to the biggest(MAP_W*TILE_W)

and when you add a tree add it and sort...
or find it''s pos and then add it

ok
now you get the player radius pos..
(let the radius be the screen height or something)

so it''s like you have a surrounding circle and in the middle the player is...
then you get the left point(x) of the circle and the right one(x2)
so you have x, x2
then you scan the sorted list and see which x pos is bigger than
x then you check which x is smaller than x2
so you have now index1(bigger), index2(smaller)

and now you just check this trees from index1 to index2

i hope it helped

sorry for bad english!

I fear that sorting obsticles would infact be slower than actually doing a collision test for each object within a working range of the object in question. Collision testing for rectangular overlap is extremely simplistic and therefore very very fast, just a few if blocks for each test. Bear in mind that those sorts of statements compile to just a couple of instructions for the CPU. You won''t even notice on a modern PC.

If you start talking about collision detection between arbitary shaped polygons, then it gets somewhat slower, and therefore, sorting might be a good idea.

Use this:

bool AinsideB(RECT A, RECT B) { if(A.bottom<=B.top) { return false; } if(A.left>=B.right) { return false; } if(A.top>=B.bottom) { return false; } if(A.right<=B.left) { return false; } return true; }

And if it returns true, then do a more complex collision detection. I use this to test if I need to preform a per-pixel collision test, which seems to run quickly since it only is called upon when needed.

Here''s an idea:

Make an array (lets keep it 2d for this example). It covers the entire map, but with less precision than 1 pixel or whatever. It''s like a big chessboard over the whole land, deviding it into managable sectors. (the cells should be bigger than the biggest obstacle).
The array contains a linked list of obstacles.

When you add an obstacle, round off it''s co-ords to the precision of the grid, and add it''s pointer to the appropriate cell in the array.

Now you can do the same rounding with the player co-ords and only do collision detection on the obstacles in that cell.

This should be fast because rounding isn''t too time consuming. But I just made it up so I don''t know if it''d work well.

Frank