🔒 Locked

Collision

Started by Arith May 18, 2009 at 10:09 AM 3 replies 750+ views

Original Post

May 18, 2009 at 10:09 AM

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

oliii

May 18, 2009 at 10:43 AM

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.

Derakon

May 18, 2009 at 11:06 AM

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.

oliii

May 18, 2009 at 7:01 PM

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.

oliii

May 20, 2009 at 4:57 PM

well, I've done it. It's a bit much to talk through though...

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.