Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (483)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
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  
  My pixel-perfect collision detection method.  (Read 4779 times)
0 Members and 1 Guest are viewing this topic.
Offline Funkapotamus

Junior Member




wo shuo han yu


« Posted 2004-10-22 17:42:52 »

Pixel-Perfect Collision Detection.  There's a lot of demand for this type of endeavor but there arn't any specific examples on how people can get it to work for themselves.  In an effort to help others where I struggled, here's a rundown on how to get pixel-perfect detection with Java.

I'll be basing this on this link:  http://www.gamedev.net/reference/articles/article754.asp

The guy who wrote it, TANSTAAFL, lays out the math and other concepts pretty clear so I won't get much into that.  I'm just going to go over how to get your bitmask layer and how to use it like he recommends.

1)  Load the image and get it's data into a byte array:
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  
      // Get the image's data.
     private byte[] getData(String ref)
      {
            BufferedImage sprite = null;
            URL absoluteRef = null;

            try
            {
                  absoluteRef = ImageThingie.class.getClassLoader().getResource(ref);

                  if(absoluteRef == null)
                        System.out.println("No URL?  Classloader failed?");

                  sprite = ImageIO.read(absoluteRef);
            }
            catch(Exception e)
            {
                  System.out.println("ERROR: File " + ref  + " not found.");
                  // Just exit out of the image isn't found.  It's pretty essential to the program so don't bother trying to run without it.
                 System.exit(0);
            }

            imageWidth = sprite.getWidth();
            imageHeight = sprite.getHeight();

            //  Force RGBA.
           //  If it's not RGBA, well, screw it.
           ColorModel glAlphaColorModel = new ComponentColorModel(ColorSpace.getInstance(ColorSpace.CS_sRGB),
                  new int[] {8,8,8,8},
                  true,
                  false,
                  ComponentColorModel.TRANSLUCENT,
                  DataBuffer.TYPE_BYTE);

            WritableRaster raster = Raster.createInterleavedRaster(DataBuffer.TYPE_BYTE, imageWidth,imageHeight, 4, null);
            BufferedImage texImage = new BufferedImage(glAlphaColorModel, raster, false, new Hashtable());

            Graphics2D g = (Graphics2D)texImage.getGraphics();
            g.drawImage(sprite, 0, 0, null);
            g.dispose();

            return ((DataBufferByte)texImage.getRaster().getDataBuffer()).getData();
      }


2)  When you read an image like this, it dumps all of it's information into a byte array.  Each pixel's data is 4 elements long in the array.  The first element holds the pixel's Red saturation, the second is Green, third is Blue, and the last is the Alpha.  For collision detection, we only need to worry about the alpha value.  So, we're going to strip it out of the image's data.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
byte imageData[] = getData(FILENAME);
byte alpha[] = new byte[IMAGEWIDTH * IMAGEHEIGHT];

// -1 is a pixel.  Anything else is transparant or an alpha value.
           int count = 0;
            for(int i = 0; i < imageData.length; i++)
            {
                  if(i % 4 == 0 && i != 0)
                  {
                        alpha[count] = imageData[i-1];
                        count++;
                  }
            }


Now that you have an array of the image's alpha value, you can refer back to GameDev link above and apply your collision detection technique.

If you're doing rotational collision detection, things get a little more complicated, but the gist of things remains the same.  To rotate a position in an array, you can do something like this (Note: The below is pseudocode.  It won't really work-  you're going to have to use this as a guideline for how you want your rotations to be done.):

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  
byte rotationLayer[][] = new byte[IMAGEWIDTH][IMAGEHEIGHT];
            int imageX = TRANSLATED_WORLD_X;
            int imageY = TRANSLATED_WORLD_Y;

            int angle = SPRITE_ANGLE;

            double cos = Math.cos(Math.toRadians(angle));
            double sin = Math.sin(Math.toRadians(angle));

            for(int x = 0; x < IMAGEWIDTH; x++)
            {
                  for(int y = 0; y < IMAGEHEIGHT; y++)
                  {
                        if(alpha[x][y] == -1)
                        {
                              int currentX = x + imageX;
                              int currentY = y + imagey;

                              int nextX = (int)((currentX * cos) - (currentY * sin));
                              int nextY = (int)((currentX * sin) + (currentY * cos));

                              if(nextX >= 0 && nextX < imageWidth && nextY >= 0 && nextY < imageHeight)
                              {
                                    // -1 = pixel
                                   rotationLayer[nextX][nextY] = -1;
                              }
                        }
                  }
            }


When this is done, the byte array named rotationLayer will have the alpha data of the sprite when it's rotated.  You can then use this array to check against another 'rotationLayer' and do the same collision detection technique as you use for non-rotated images.  The catch here however, is figuring out how to translate these coordinates into your gaming world so you can find the point of collision outside of just having a position in the array.

Later, I'll be posting a webstartable application that loads an image and dumps it's data into an HTML file.  You'll be able to rotate the image and whatnot so you guys can get a nice feel for how things are supposed to go.  Expect that later this week.  For now, I've got a busy weekend ahead of me outside the coding world.

I hope this helped some people.  Feel free to PM me with questions or comments.  I'll try to do my best and help.

Edit: Whoops, I doubleposted before I was finished writing.  I deleted the old one.
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #1 - Posted 2004-10-27 00:36:50 »

PPCol is overrated Grin

Well, if you use it always remember to use a tiered collison detection scheme.

Like:
-check hitboxes
-if hit check for ppcol
-if hit... yes you've really hit it then

With rotations it's usually something like:
-check bounding spheres
-if hit rotate (see no unneccessary rotation)
-if hit rotated shape (ppcol or geometry)... yes you've hit

The reaons for doing so is easy. Most of the time there isn't a collision. Therefore it makes perfect sense to use easy to calculate tests for sorting those out before doing any cpu intensive accurate checks.

A low level logic optimisation like that can already give you a *huge* performance improvement.

There is also a higer level of logic optimsation. Like game rules (no need to check your bullets agains yourself or agains other bullets) and things like sectors or quad trees. So before you do the first step (checking if they might intersect) you determine if they have a chance to intersect. For example entities in the upper left quadrant can't intersect with entities in the lower left quadrant.

Well, each game is different. If you have for exmaple some kind of static grid (oldschool breakout or a tilebased jump n run) you won't need anything tricky. Because you "know" were you are and which tiles/bricks are next to you. In a breakout game those tiles of interest are those which are below the four ball sprite corners (if the ball is smaller than the grid you have 1, 2 or 4 cells, which you have to check for collision).

The topic is pretty broad... so I'll stop here. Over at gamedev.net and gamasutra.com are a bunch of articles.

I also recommand the article of those "N" (a flash game) guys. It has a bunch of interactive parts, which can be used to try (and see) those different methods.

http://www.harveycartel.org/metanet/tutorials/tutorialA.html

弾幕 ☆ @mahonnaiseblog
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #2 - Posted 2004-10-27 01:17:18 »

I forgot that I have some demonstration material Smiley



That's the breakout example. The white box shows the 4 grid cells, which I have to check and the red square highlights the one which contains the ball middle. That one is somewhat special, because it's used for "sorting" the voronoi regions by importance (edge collision first[flat], vertex collision later[corner]).

If you wondering what I mean... well if there are two bricks next to each other and the ball hits somewhere in the middle, I want the ball to bounce off straigt (as if it's a single big brick). Therefore I care about those straight bounce off voronoi regions (edges within the white rect touching the red rect) first and about the corners later (if no collision happened).

Well, (advanced) collision detection is quite complicated, but fortunately it's also pretty interesting Smiley

弾幕 ☆ @mahonnaiseblog
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.

CopyableCougar4 (15 views)
2014-08-22 19:31:30

atombrot (28 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (38 views)
2014-08-06 19:49:38
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

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!