Map to entity collision

Nibbie
Posts: 1
Joined: 2010.11
Post: #1
I have a large map of around 2000 polygon (not triangle, 3-16 sided) objects and I'm checking their collision with each moving entity in the game every frame. I'm wondering if there is a faster way than this brute force method (check each line of each polygon with each line of the first, move on to the next one, next and so on). A library or sample code would be cool Cool

Thanks
Quote this message in a reply
Nibbie
Posts: 2
Joined: 2006.10
Post: #2
Are these 2D polygons in a 2D world? A simple improvement is to give every polygon a bounding box/circle and check to see if the bounding shapes intersect before moving on to the more complex polygon-polygon intersection test. This alone might be sufficient.

If you need to optimize more however, you could overlay a grid of cells on top of your map (like say a 10x10 grid). Each cell keeps track of which polygons are contained inside it. When you test for collision, you only have to check for collisions between objects in the same cell. If the polygons themselves are not moving, it may be more efficient to use a quadtree for this same purpose rather than a fixed grid.
Quote this message in a reply
Member
Posts: 86
Joined: 2005.01
Post: #3
A bounding box would be the easy way here. Alternatively you could determine points on the outside of your polygons that are most likely to collide and test only those.
Quote this message in a reply
Nibbie
Posts: 1
Joined: 2010.11
Post: #4
I already do bounding circles, which speeds it up a bit. The problem with the grid is the fact that objects overlap into other grids. Maybe I could make it only check the grid within a certain range (the cell it's in and the other 8 cells all around it). Hmm...
Quote this message in a reply
Nibbie
Posts: 2
Joined: 2006.10
Post: #5
Joseph Duchesne Wrote:I already do bounding circles, which speeds it up a bit. The problem with the grid is the fact that objects overlap into other grids.

This is OK. Your objects don't have to live in exactly one grid cell. When I'm using a grid to optimize collision detection, I typically also use bounding rectangles (instead of circles) because it makes it easier to determine which grid cells the object belongs to. I also make sure that my grid cells are large enough so that no object can be in more than 4 cells at a time (basically, they should be as large as your largest bounding rectangle). Each cell keeps track of an NSSet of objects. When testing for collision with a specific object, I figure out which cells it is in (by checking each vertex of the bounding rectangle) and union their object sets.
Quote this message in a reply
Post Reply