I was wondering if there was a better way to do collision detection than the current way I''m doing it... right now I guess you could say I''m using brute force - check every object with every other object every single frame. While this method works, it''s slow. Is there some super complex and optimized collision detection algorithm out there somewhere?

If you now check every plane of each object with each plane of each other object do the following, if you already do what i said or if it sounds stupid to you, please ignore it .
First check the distance between the objects, if the distances together are less than the distances of the farrest vertices of both objects, test for collision per vertex. This really speeds up.

See, that''s what I do now... to speed up collision detection and make my code easier to write, all my bounding boxes are spheres. The game is in space and you can only move on the X and Y plane, so the only thing you can run into is other guys, bullets, and maybe asteroids. So I just check the distance between my two objects, and if that is less than the sum of the collision radii... then a collision happened.

You could try:
1. Test collision using low detail models
2. Use space partitioning making a bounding box for for example each limb.

Actually i don''t really understand why your collision detection slows down as distance checking is not really an expensive calculation as it only incorporates adding, an if statement, multiplying and one sqrt operation. This will only really slow down when using like 10,000 objects (my expererience) but i don''t think that''s the case.

quote:

---

Original post by LlamaGuy
See, that''s what I do now... to speed up collision detection and make my code easier to write, all my bounding boxes are spheres. The game is in space and you can only move on the X and Y plane, so the only thing you can run into is other guys, bullets, and maybe asteroids. So I just check the distance between my two objects, and if that is less than the sum of the collision radii... then a collision happened.

---

What you''re looking for is a spatial tree, something like an Oct-tree or quad-tree which organises your objects based on their position and size. It lets you quickly determine objects in a region, so you don''t have to test lots of objects that are on the one side of the world against those on the other.

Tip: when checking distance don''t sqrt the distance and multiply the radius sum by itself, this way you will still have an accurate check (even more accurate) and it makes the sqrt call unneccesery! I thought of this 2 weeks ago and it suddenly came up again !

Was gonna post about saving the sqrt function but looks like I''ve been beaten to it! sqrt is an expensive function and can easily be eliminated in bounding sphere collision detection.

If you''re checking every object with every other object, make sure you don''t check twice (e.g. A and B vs B and A) and that you don''t check with itself (e.g. A and A). i.e. object 1 checks with objects 2-10, object 2 with objects 3-10 etc. I''m sure you''ve already though of this but it''s worth mentioning.

Quadtrees/Octrees are not relevant to collision detection with dynamic objects. They are more suited to collisions with (and drawing of) the game world. It sounds to me like your objects are dynamic. ...As an afterthough, if your asteroids all move in the same direction at the same speed, i.e. an asteroid field, the asteroid field could be considered a static object through which other objects fly, so could benefit from space-partitioning/localised collision detection.

I never thought of getting rid of the sqrt function like that, that''s a really good idea. I think I''m also checking collision on each ship twice... which probably explains some of the bugs I''ve been having with collisions... but when I''m detecting bullets colliding into ships, I''ll have to run through every combination still.

Thanks guys, those tips will probably speed up detection by a good amount.

quote:

---

Original post by Anonymous Poster
Quadtrees/Octrees are not relevant to collision detection with dynamic objects.

---

Bullshit. Quad/Oct trees work perfectly well with dynamic objects. Granted they don''t have the same efficiency than if you can do some preprocessing due to static world geometry, but thats not actually needed.

S-Type uses totally dynamic objects - nothing has to be fixed - and a quadtree to manage collision. Without it the huge number of objects would bring it down to a crawl.

[S-Type] [V-Script]