Pixel Collision Optimzation?

Game Mechanics
#1

Hey all, just registered here :wink:

Anyway, I’ve got a project I’m working on that’s a Sonic The Hedgehog-esqe game. I’ve done pretty good so far, but I’ve got a question about pixel based collision. Right now I take the two images of the ‘sprites’ that are being checked. Then it goes through and checks if they have a pixel overlapping. Here is a code-snippit:

...
      public boolean collidesWith(CollisionMask b)
      {
            if(b == this)
                  return false;

            Rectangle me = new Rectangle(getX(), getY(), getWidth(), getHeight());
            Rectangle you = new Rectangle(b.getX(), b.getY(), b.getWidth(), b.getHeight());

            if ( me.intersects(you) )
            {
                  //PixelGrabbler pg = new PixelGrabbler(this, b);
                  return collided(this, b);
                  //return pg.collided();
            }
            //System.out.println("No Collision!");
            return false;
      }

      private boolean collided(CollisionMask a, CollisionMask b)
      {
            Rectangle ar = new Rectangle(a.getX(), a.getY(), a.getWidth(), a.getHeight());
            Rectangle br = new Rectangle(b.getX(), b.getY(), b.getWidth(), b.getHeight());
            Rectangle un = ar.union(br);
            BufferedImage img1 = new BufferedImage((int)(un.getX() + un.getWidth()), (int)(un.getY() + un.getHeight()), BufferedImage.TYPE_INT_ARGB);
            BufferedImage img2 = new BufferedImage((int)(un.getX() + un.getWidth()), (int)(un.getY() + un.getHeight()), BufferedImage.TYPE_INT_ARGB);
            Graphics ig = img1.getGraphics();
            Graphics ig2 = img2.getGraphics();
            ig.setColor(new Color(255, 255, 255, 255));
            ig.fillRect(0, 0, (int)(un.getX() + un.getWidth()), (int)(un.getY() + un.getHeight()));
            ig.drawImage(a.getImage(), (int)(a.getX()), (int)(a.getY()), null);
            ig2.setColor(new Color(255, 255, 255, 255));
            ig2.fillRect(0, 0, (int)(un.getX() + un.getWidth()), (int)(un.getY() + un.getHeight()));
            ig2.drawImage(b.getImage(), (int)(b.getX()), (int)(b.getY()), null);
            return colorOverlap(img1, img2);
      }

      private boolean colorOverlap(BufferedImage i1, BufferedImage i2)
      {
            for(int x = 0; x < i1.getWidth(); x++)
            {
                  for(int y = 0; y < i1.getHeight(); y++)
                  {
                        if(monochrome(i1.getRGB(x, y)) != 0xFFFFFFFF && monochrome(i2.getRGB(x, y)) != 0xFFFFFFFF)
                        {
                              return true;
                        }
                  }
            }
            return false;
      }

      private int nullAlpha(int rgba)
      {
            return 0xFF000000 + (rgba & 0x00FFFFFF);
      }

      private int monochrome(int rgba)
      {
            if(nullAlpha(rgba) != 0xFFFFFFFF)
                  return 0xFF000000;
            else
                  return 0xFFFFFFFF;
      }
...

My problem occurs when I have more than a few sprites on-screen. This only occurs when I have this code activated so I was wondering if there is any way to optomize it.

Any help would be greatly appreciated!

#2

Hopefully, this can be greatly optimized by the use of quadtrees. A “collision” quadtree for this sprite is a hierarchical structure that allow you to test for collision in a increasing precision way. Each node of this tree cover a part of the sprite and the “oppacity state” of this part ( OPAQUE, TRANSPARENT, MIXED ). If a node is MIXED, it contains four sub-node covering each a quarter of the parent’s sprite area. The root node covers the entire area.

Example :

Let’s say a sprite is a 100x100 pixel array, the quadtree may looks like this :


// (x,y,width,height) STATE
(0,0,100,100) MIXED
|`-- (0,0,50,50 ) OPAQUE
|`-- (50,0,50,50 ) TRANSPARENT
|`-- (0,50,50,50) MIXED
|      |`-- (0,50,25,25) OPAQUE
|      |`-- (25,50,25,25) TRANSPARENT
|      |`-- (0,75,25,25) OPAQUE
|      `-- (25,75,25,25) MIXED
|            ...
 `-- (50,50,50,50) OPAQUE

This structure is built when you load the sprite and stick with it the all sprite’s life.

Now, when you need to know if two sprites overlap, apply this algorithm :


public bool collisionTest( Node node1, Node node2 ) {
  if( node1.state == TRANSPARENT || node2.state == TRANSPARENT ) {
    return false;
  } else if( node1.state == OPAQUE || node2.state == OPAQUE ) {
    return true;

  // they're both mixed.
  } else {
    Node node11, node12, node13, node14;
    Node node21, node22, node23, node24;

    return 
       collisionTest( node1.subnode1, node2.subnode1 ) ||
       collisionTest( node1.subnode2, node2.subnode2 ) ||
       collisionTest( node1.subnode3, node2.subnode3 ) ||
       collisionTest( node1.subnode4, node2.subnode4 );
  }
}

// test

Sprite sprite1( "sprite1.png" );
Sprite sprite2( "sprite2.png" );

if( collisionTest( sprite1.collisionRoot, sprite2.collisionRoot )) {
  System.out.println("Sprites overlap");
} else {
  System.out.println("Sprites dont overlap");
}

Note: This algorithm only works for sprites having the same dimension and not offseted. More advenced collision detection require quite more code but are easily feasible too.

Hope this helps =)

#3

Thanks for the great reply ;D

Also, I’m assuming the tree needs to be recalculated for each sprite animation… ?

#4

Each animation frame has its own tree.