Collision Detection Ideas...
BlitzMax Forums/BlitzMax Programming/Collision Detection Ideas...
| ||
| Hi I'm working on improving my LD entry (see sig) and I have already managed to greatly speed up it's performance with enhancements to the collision detection. As the 'Advancing wall of doom' tends to grow in a square pattern I now limit the CollideImage checks to bullets that enter a bounding box around the blocks of doom. I think I can enhance this approach further by using a sectoring grid, simply divide all of the unit's x, y coords by a scaling factor then add each one to an array of lists at those secor coords. Now any inter object checks can be limited to sectors and their neighbours cutting down the n factorial checks needed for checking every object to every other... So before I implement this and test it I was wondering if you think this will be a good generic collision detection framework? Note that the game could include sectoring grids at different resolutions to potentially further reduce tests. e.g corse for faster sector scanning, fine for limiting tests to a handfull of objects. Ideally sectors would actually overlap, so an object on the edge of two or more sectors would appear in all it intersected with, alternatly I would need to check all sourrounding sectors for collisions. |
| ||
| I use a similar style of collision detection in most of my games, and it is very quick. |
| ||
| why don't you profile your code to determine what part spends the most time. I suspect you pretty much optimized your collision to it's limit. I don't see how dividing your code into sectors would increase it. For you to do that, you would have to add more code and would probably eat up the difference. if you are still using "ImagesCollide" try using an alternative. Check the drawing functions, that might be what's eating your frame rate. I saw your wall drawing function. It appears you are drawing outside of the viewing area. if you stop doing that it will improve your speed by a noticeable difference. |
| ||
| Yep, it's quicker, and you can even go further and make a quadtree. |
| ||
| OK quadtree, also found the link about k-d tree's just a quick browse and it looks like they are good at nearest neighbour searches as well? Darn it had a bit more of a look and there are loads of heirarchical structures for spacial partitioning, but which one will work best for collision detection and viewclipping 2d sprites? |
| ||
| Bounding boxes are still very quick. So are nested grids. |
   |