Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (526)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (593)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Pixel Collision Optimzation?  (Read 1226 times)
0 Members and 1 Guest are viewing this topic.
Offline Vage

Senior Newbie




learning++;


« Posted 2005-04-17 22:26:22 »

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:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
...
      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!

Personally, you could strap me into a mech cockpit with 47 virtual HUD displays, two complex hand controls and foot pedals and I'd be grinning like the gamer freak I am.
Offline Deadcow

Senior Newbie




Back from beyond ... Moo!


« Reply #1 - Posted 2005-04-19 09:52:23 »

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 :

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
// (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 :

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
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 =)
Offline Vage

Senior Newbie




learning++;


« Reply #2 - Posted 2005-04-21 21:42:45 »

Thanks for the great reply  Grin

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

Personally, you could strap me into a mech cockpit with 47 virtual HUD displays, two complex hand controls and foot pedals and I'd be grinning like the gamer freak I am.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Deadcow

Senior Newbie




Back from beyond ... Moo!


« Reply #3 - Posted 2005-04-22 07:23:45 »

Quote

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


Each animation frame has its own tree.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

toopeicgaming1999 (71 views)
2014-11-26 15:22:04

toopeicgaming1999 (60 views)
2014-11-26 15:20:36

toopeicgaming1999 (14 views)
2014-11-26 15:20:08

SHC (27 views)
2014-11-25 12:00:59

SHC (25 views)
2014-11-25 11:53:45

Norakomi (31 views)
2014-11-25 11:26:43

Gibbo3771 (25 views)
2014-11-24 19:59:16

trollwarrior1 (38 views)
2014-11-22 12:13:56

xFryIx (77 views)
2014-11-13 12:34:49

digdugdiggy (55 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!