Jump to content
  • Advertisement
Sign in to follow this  
Arith

Collision

This topic is 3323 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm taking my first plunge into writing some collision detection but I've been running into some walls. I know there's ALOT of material on this site, much of which I have looked at. I figure I'd get some suggestions from the forums on my particular situation while I continue to read. So obviously, I'm writing a game. (AllegroGL, C++) I have a working map and sprite engine. I started with a simple set of loops to address sprite + map collision;
      for (int s=0;s<=SPRITENUM;s++) 
      {
       if (Sprites[s].Active)
       {
         // Start
         for (int y=0; y<=MAPY; y++)
         {
          for (int x=0; x<=MAPX; x++)
          {

          }
         }
         // End
       }
      }
Obviously no actual collision detection is happening, but my problem is... This destroys frame rate. As it is there. I understand why however. SPRITENUM is 100, and MAPX/Y are also 100. 100x100x100 loops (worst case) is ALOT of work. I'd hate to think of what it would be like if I put actual code in these loops. So, my question is.. if that loop alone kills framerate, how are you SUPPOSED to do collision efficiently? If I comment out the code between //start and //end the framerate is more or less normal. So if anyone has any thoughts or recommended reading it would be greatly appreciated. Arith

Share this post


Link to post
Share on other sites
Advertisement
the first optimisations would be to limit your collision check only the tiles covered by your sprite. I assume your tiles are evenly placed in rows and columns, and your sprites have a bounding box around them.

The code would be quite similar to something like this.

In any case, you need some sort of spatial sorting for your objects and tiles. a 2D grid is an obvious candidate for that sort of things for a 2D sprite game.

Share this post


Link to post
Share on other sites
For colliding sprites against terrain (where the terrain is presumably on a grid), you should, as Olii suggested, just look at the specific squares on the grid that the sprite could possibly interact with.

For colliding sprites with sprites, since any given sprite can have an arbitrary location, I suggest looking into quadtrees. They're very handy data structures.

Share this post


Link to post
Share on other sites
you can also have grid cells reference the objects that are found to intersect the cell. That includes static tiles, as well as dynamic objects, bullets, ect... in the form of bucket lists.

an object would have a reference to the cells it covers (basically the area covered, as in cell coordinates), while each cell covered would have a reference to the object (a pointer, handle, ect...).

When you wish to know what object can collide with a specific object, you simply pull out the objects from the lists and test against them. At most, a single cell would reference 1/2 dozen object at a time, so the checks would be minimal.

Grids are also very useful for ray-cast type queries and proximity queries. Sweep and prune not so much.

The main disadvantage with grids is memory consumption.

Here's an article. The limitations they talk about can be overcome easily. it's just a matter of computing what cells are covered by a particular object's bounding box.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!