Hi,
I’m just thinking of sprite-sprite-collisons. How can I detected a “true collision”? I want to ignore the transparent parts of a sprite.
I’ve been thinking of defining several Rectangles that fit the size of my sprite, but I think this will be to compllicated if we talk about complex spirtes.
So, what would be the best method?
By the way: If possible I’m interested in doing this without additional jar/API
Best regards.
Ralf
If you’re interested in using any sort of shape (as accurate as you make it) you could use collision detection with polygons via the Area class. You can see how I do that in the source to my tutorial found here:
http://www.gamelizard.com/JavaGameProgrammingPresentation.htm
You could also first detect an image-image collision (disregarding alpha, just detecting if the images overlap), and if such a collision was detected, compare the overlapping pixels of the parts of the 2 images (sprites) that overlap. If both pixels of a compare are not transparent, you have a collision. This way, you’ll have pixel perfect collision detection (which BTW is seldom really needed).
Only in the worst case you’ll be comparing all pixels of both sprites, but usually you’ll just compare a small part.
An additional optimization might be to do the comparing from the ‘inner’ pixels of the images to the ‘outer’ pixels (as the transparent pixels are usually on the ‘outer’ parts of a sprite).
I hope I’m making sense here.
Thats how games have tarditionalyl done it when needed (first do a boundign box or bounding speher and then compare the in intersection points pixel by pixel.)
But as already said its almost never done. usually bouding box or bounding spehere is good enough.
Thanks.
In the meantime I started with a solution as erikd described it. But I will think about all suggestions.
Ralf
A side note. if you REALLY need pixel perfect inertscetiion then there is an imetrmediate step between bounding-topes and pixel comaprison that cna speed thinsg up.
its sometimes called a “shadow”. What you do is create a 1 dimensional p[rojection of the 2D object ina bit mask. At any x location where a pixel is not transparent on any row of pixels, the mathcing bti is sit on the mask. If you imagine that the obejct was one bit per pixel, then the mask is the binary OR of all the rows
If this is the object:
XXX XXX
XXXX XXXXX
XXX XXXXX
Then the shadow is this:
XXXXX XXXXXXX
Edit: Damn HTMl wont make it line up straight… ghrr… well I hope you get the idea
What you do is shit the bitstring over the appropriate amount to match the current overlap of the two objects and then binary AND it together.
If the result is clear (all zeros) then there is noi collision. If it is not clear then you just check the columns for each bit position that is 1 to see if there is really an intersection there.
Obviosuly ist not justa simpel shift and AND because your going to need a wider bit field then you can fit in a single variable (twice the width of your widest object) but the theory is the same, its jus ta bit fancier code to hanbdle the arbitrarily wide bitfield 
Thats neat! So to paraphrase you build a line of pixels for each sprite by either summing up the pixels in each column or row (which I suppose you can cache). Then do a comparison between the two lines.
Double neat!
Kev
Two questions:
private static void printChannels(int pixel) {
int alpha = (pixel >> 24) & 0xff;
int red = (pixel >> 16) & 0xff;
int green = (pixel >> 8) & 0xff;
int blue = (pixel ) & 0xff;
if(alpha!=255){
System.out.println(alpha + "/" + red + "/" + green + "/" + blue);
}
}
Which combination is a transparent color? I can’t find a hint about this 
xxxxxx
xxxxxx
ooxxoo
ooxxoo
ooxxoo
oxxxxo
oxxxxo
ooxxoo
ooxxoo
ooxxoo
If I understand it well, this leads to
xxxxxx
This seems no pixel perfect collision to me?
Ah, the thing Jeff suggested wasn’t for the final check, just another quick check you can perform before performing the pixel for pixel check.
(Completely) Transpent pixels should have an alpha of zero I believe.
Kev
Thx.
Why don’t you just load the image, create another temporary image, copy the original to the empty temporary image, avoid adding alpha colours?
Then pass the managed image back to your main program.
Whenever you do basic collision it would be pixel perfect.
[quote]Ah, the thing Jeff suggested wasn’t for the final check, just another quick check you can perform before performing the pixel for pixel check.
(Completely) Transpent pixels should have an alpha of zero I believe.
Kev
[/quote]
Right, if you rotuinely fill all the coluns with at least one pixel its not terribly useufl. OTOH if you have a lot of “surrounding whitespace” or columsn of whitespace in the middle, it can be.
Its just another potential heuristic.
How should this work? My images are still defined with x/y/widht/height and the collision are still detected by overlapping rectangles. So, I still have to check the pixels, don’t I?
[quote]@K.I.L.E.R
How should this work? My images are still defined with x/y/widht/height and the collision are still detected by overlapping rectangles. So, I still have to check the pixels, don’t I?
[/quote]
Yeh, but at least you wont have to check many pixels. It removes a lot of overhead at the expense of load time.
Finally I got a solution, but I still have to test it properly. I also thinking about adding some of the suggestions above into my programm.
Nevertheless, here’s my solution. It is not called for each collison detection only for some cases.
Any comment would be appreciated.
`
import java.awt.;
import java.awt.image.;
public class CollisionDetector {
static Rectangle s1;
static Rectangle s2;
static Rectangle inter;
static int width;
static int height;
public static BufferedImage buf1;
public static BufferedImage buf2;
public static CollisionDetector single = new CollisionDetector();
public CollisionDetector getDetector(){
return single;
}
public static boolean checkPixelCollision(Image a, int ax, int ay, Image b, int bx, int by){
//Rectangles
//System.out.println("detector");
//System.out.println("A = " + ax + "/" + ay + "/" + a.getWidth(null) + "/" + a.getHeight(null));
//System.out.println("B = " + bx + "/" + by + "/" + b.getWidth(null) + "/" + b.getHeight(null));
//initialize Rectangles
Rectangle rec1 = new Rectangle();
Rectangle rec2 = new Rectangle();
inter = new Rectangle();
//set Bounds and get intersection
rec1.setRect(ax,ay,a.getWidth(null),a.getHeight(null));
rec2.setRect(bx,by,b.getWidth(null),b.getHeight(null));
Rectangle.intersect(rec1,rec2,inter);
//Intersection
//System.out.println("I = " + inter.x + "/" + inter.y + "/" + inter.getWidth() + "/" + inter.getHeight());
//widht and height must be at least 1 Pixel
width = (int) inter.width;
height = (int) inter.height;
if(width<1){
return false;
}
if(height<1){
return false;
}
//compute sub-images for image 1
s1 = getSubRec(rec1,inter);
//widht and height must be at least 1 Pixel
width = (int) s1.width;
height = (int) s1.height;
if(width<1){
return false;
}
if(height<1){
return false;
}
//compute sub-images for image 2
s2 = getSubRec(rec2,inter);
//widht and height must be at least 1 Pixel
width = (int) s2.width;
height = (int) s2.height;
if(width<1){
return false;
}
if(height<1){
return false;
}
//SubImages
//System.out.println("S1 = " + s1.x + "/" + s1.y + "/" + s1.width + "/" + s1.height);
//System.out.println("S2 = " + s2.x + "/" + s2.y + "/" + s2.width + "/" + s2.height);
buf1 = (BufferedImage)a;
buf2 = (BufferedImage)b;
buf1 = buf1.getSubimage((int)s1.x,(int)s1.y,(int)s1.width,(int)s1.height);
buf2 = buf2.getSubimage((int)s2.x,(int)s2.y,(int)s2.width,(int)s2.height);
//System.out.println(buf1.getWidth() + "/" + buf2.getWidth());
//System.out.println(buf1.getHeight() + "/" + buf2.getHeight());
for(int i=0;i<buf1.getWidth();i++){
for(int n=0;n<buf1.getHeight();n++){
//System.out.println(i + "/" + n);
int rgb1 = buf1.getRGB(i,n);
int rgb2 = buf2.getRGB(i,n);
if(isOpaque(rgb1)&&isOpaque(rgb2)){
return true;
}
}
}
return false;
}
private static boolean isOpaque(int pixel) {
int alpha = (pixel >> 24) & 0xff;
//int red = (pixel >> 16) & 0xff;
//int green = (pixel >> 8) & 0xff;
//int blue = (pixel ) & 0xff;
//transparent if alpha = 0
if(alpha==0){
return false;
}
return true;
}
//computing Rectangles for sub-images
private static Rectangle getSubRec(Rectangle rec1, Rectangle inter) {
//Rechtecke erzeugen
Rectangle sub = new Rectangle();
Rectangle source = rec1;
Rectangle part = inter;
int absoluteX = 0;
int absoluteY = 0;
//get X - compared to the Rectangle
if(source.x>part.x){
sub.x = 0;
absoluteX = source.x;
}else{
sub.x = part.x - source.x;
absoluteX = part.x;
}
if(source.y>part.y){
sub.y = 0;
absoluteY = source.y;
}else{
sub.y = part.y - source.y;
absoluteY = part.y;
}
//same handling with y
if((source.x+source.width)<(part.x+part.width)){
sub.width = (source.x+source.width)-absoluteX;
}else{
sub.width = (part.x+part.width)-absoluteX;
}
if((source.y+source.height)<(part.y+part.height)){
sub.height = (source.y+source.height)-absoluteY;
}else{
sub.height = (part.y+part.height)-absoluteY;
}
return sub;
}
}
`