Collision detection methods

Discussion in 'Game Development (Technical)' started by tentons, Aug 24, 2004.

  1. tentons

    Indie Author

    Joined:
    Mar 1, 2004
    Messages:
    664
    Likes Received:
    0
    I'm curious about what sorts of 2d collision detection you guys employ.

    I do a sector test to reduce the number of tests to objects that are within a certain proximity, then bounding circle, then bounding box. My current game doesn't need extreme accuracy, so this should work out.
     
  2. Nemesis

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    273
    Likes Received:
    0
    The most accurate 2D solution would of course be a pixel-by-pixel check on the bounding box overlaps.

    I'm working on a 3D shoot-em-up however and hence I also had to come up with an adequate solution. Every entity has a bounding sphere. Within the bounding sphere of an entity, a number of "collision spheres" define a very approximate bounding shape. Obviously, the more spheres used, the better. For most cases, 2-6 spheres are more than enough.

    The following is a screenshot illistrating the collision spheres in the custom game editor:
    http://colinvella.no-ip.com/perihelion/021.jpg
     
  3. Rod Hyde

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    123
    Likes Received:
    0
    Pixel-perfect collision detection doesn't need to check pixel-by-pixel. For each sprite, I pre-calculate the runs of non-transparent pixels on each row. In my current game I actually save this along with the sprite data, but it would be just as simple to calculate it when the sprite bitmaps are first loaded.

    In the game itself, once the "shallow" collision detection has determined the need for a more detailed check, I simply determine the area where the two sprites overlap, then check if the runs of data overlap.

    This is the code in Python.

    Code:
        def test_collision(self, other):
            """Pixel perfect collision detection.
            
               Works on the premise that most sprites are opaque in the middle and
               therefore have a small number of relatively long runs of opaque
               pixels per row.
            """
            cd1 = self.get_collision_data()
            cd2 = other.get_collision_data()
            l1, t1, r1, b1 = self.bounding_rect
            l2, t2, r2, b2 = other.bounding_rect
            start = min(t1, t2)
            stop = 1 + min(b1, b2)
            dx = l1 - l2    # difference in x coordinates
            for y in range(start, stop):
                r1 = y - t1     # row number in first shape
                r2 = y - t2     # row number in second shape
                if cd1.has_key(r1) and cd2.has_key(r2):
                    for run1 in cd1[r1]:
                        min1, max1 = run1
                        min1 += dx
                        max1 += dx
                        for run2 in cd2[r2]:
                            min2, max2 = run2
                            if max1 >= min2 and min1 <= max2:
                                return True
            return False
     
  4. Nemesis

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    273
    Likes Received:
    0
    Rod Hyde, good technique!

    But does it handle hollow sprites? i.e. can you have more than one run per row?

    (edit) I didn't bother to look at your code snippet... the answer is no.. duh.. silly me!
     
    #4 Nemesis, Aug 24, 2004
    Last edited: Aug 24, 2004
  5. Rod Hyde

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    123
    Likes Received:
    0
    Yes, it should handle hollow sprites as there can be several runs per row. Each row of collision data is a list of pairs of x coordinates, ie, the minimum and maximum x coordinate of each run.

    To generate the collision data, I hacked up a Python script. The bit that does the work is shown below. My assumption in the following code is that black pixels are transparent.

    Code:
    def make_collision_data(image_file):
        """Generates dimension and collision data from the given bitmap file.
    
        Returns a tuple consisting of the bitmap's width, its height and a
        dictionary, indexed by row, containing lists of "run" tuples, where a run
        tuple is a (start, end) pair indicating non-transparent data.
        """
        import Image
        im = Image.open(image_file)
        width, height = im.size
        run_dict = {}
        for y in range(height):
            in_run = False
            run_list = []
            for x in range(width):
                pixel = im.getpixel((x, y))
                if pixel != (0, 0, 0) and pixel != 0:   # deals with both 24-bit and 8-bit data
                    if not in_run:
                        in_run = True
                        run_start = x
                elif in_run:
                    in_run = False
                    run_list.append((run_start, x-1))
            if in_run: run_list.append((run_start, width-1))
            if len(run_list) > 0:
                run_dict[y] = run_list
        return (width, height, run_dict)
    I am just amazed that I never thought of doing this 12 years ago when I was really into programming in 2d.

    --- Rod
     
  6. MirekCz

    Original Member

    Joined:
    Aug 16, 2004
    Messages:
    66
    Likes Received:
    0
    Pretty nice method.

    To get a very fast, all-cases collision detection you can do the following stuff:

    1.create a 1bpp masks which tells pixel trasnaprent(0) or opaque(1)
    2.If initial bounding-box or similar test is passed you make detailed test

    you simply take the mask values of objects from the same line on screen, shift them to put them in their position, AND them, if result is >0 you have got a collision. If you're sprite width is larger then 32pixels or higher then 1 you have to repeat the xor

    some ascii art now

    sprite 1 mask
    0001111000
    sprite 2 mask
    0011001100

    here's how sprite are drawn on screen (1-sprite 1, 2-sprite 2, 3-both sprites)
    1113333333222 (so sprite 2 is moved 3 pixels to right from sprite 1)

    so you need to do
    sprite1 mask AND (sprite 2 mask >>3)
    so you get
    *****0001111000
    AND**0000011001 (sprite2 was shifted 3 to right)
    ------------------------
    result*0000011000 - collision detected

    //* is just a dummy char

    This system works great, althrought it is a bit problematic to implement well in practice for all cases(simply needs time to write it well and fix eventual bugs). The good point is little memory need and very fast test time, especially for sprites <=32 pixels wide.
     
  7. Nemesis

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    273
    Likes Received:
    0
    @MirekCz,
    Your method is definitely better than pixel-pixel checking but I think Rod Hyde's solution is more efficient as it is independen of sprite width, provided there aren't too many hollow sections.. but that is unlikely.

    @Rod Hyde
    I wouldn't have thought about that solution either.. although it is reminiscent of the (name off the top of my head - correct me if wrong) span-line floodfill algorithm.
     
  8. tentons

    Indie Author

    Joined:
    Mar 1, 2004
    Messages:
    664
    Likes Received:
    0
    @Rod Hyde: That's a cool technique! I'm really interested in knowing how (natively) compiled Python performs. Have you done any benchmarking with your collision algorithm?

    @Nemesis: I'm resisting the urge to do a 3d game because I have a learning curve to face, but also because there are plenty of ideas where 3d adds nothing except more art requirements. But eventually I'll take the leap.
     
    #8 tentons, Aug 25, 2004
    Last edited: Aug 25, 2004
  9. Nemesis

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    273
    Likes Received:
    0
    That's true.. there's little point in going 3D if you can satisfy the gameplay requirements in 2D. I'm still very much in love with 2D actually but I decided to give 3D a go anyway. My game Perihelion offers classic shoot-em-up gameplay but in 3D so in essence you're given an extra dimension to dodge enemy fire, fly through structures etc.
     

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer