Hi,
Does anyone have a simple example of implementing pixel perfect collision between a sprite and a random generated world? Something like http://www.java-gaming.org/index.php/topic,23669.0.html
I don’t know how to implement this effect, I’m doing only rectangle based collision and I’d like to improve my game with pixel collision.
thanks!
The collision detection in that game is really simple, just two points at the feet and head of the penguin checked against the floor and ceiling height for the x location. I could have added more points for more accurate results, but I didn’t really need to. No pixels were involved!
My updated Sprite-class, feel free to use it or parts of it 
It has support for pixel-perfect collisions
ok, maybe that was not the right example. But anyway, is there any tutorial about the subject, how to implement it using java. I’d like to make a sprite walk on a ground like a mountain for example that has a very irregular ground and I’m not able to do it… I was googling something about it, and I found methods envolving bitmasks but no java implementation as an example… 
Here is a class I made many many moons ago. 
No promises here, but you can at least check out the collision method, as it’s simple.
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Polygon;
import java.awt.Rectangle;
import java.awt.geom.Area;
import java.awt.image.BufferedImage;
import java.util.Iterator;
/**
* The Physical is the superclass for all objects that appear within
* the level, including all Players, Explosions, and Spells.
* Physicals have a current direction of force that determines the
* direction and velocity it moves. Physicals also have a mass which
* affects this as well, and if a mass is zero no force affects them.
* @author eli
*
*/
public abstract class Physical implements java.io.Serializable
{
private static final long serialVersionUID = 1L;
/** Variables used to determine collision and location, x+y are top left corner*/
protected float x, y, width, height;
/** The current force of this physical, it determines
* how the physical is moving at the end of the timestep. */
protected Vector force;
/** The mass of this physical, changes overall speed */
protected float mass;
public Physical()
{
x = y = width = height = mass = 0.0f;
force = new Vector(0,0);
}
public Physical(float newX, float newY, float w, float h, Vector f, float m)
{
x = newX;
y = newY;
width = w;
height = h;
force = f;
mass = m;
}
public Vector position()
{
return new Vector(x,y);
}
public Vector force()
{
return force;
}
public float mass()
{
return mass;
}
public BufferedImage bounds()
{
BufferedImage b = new BufferedImage((int)width,(int)height,BufferedImage.TYPE_INT_ARGB);
Graphics2D g = b.createGraphics();
g.setColor(Color.BLACK);
g.fillRect(0,0,(int)width,(int)height);
g.dispose();
return b;
}
/** Applies a force to this physical, useful for bounces,
* deflections, and the like. Offsets the force already existing.
* @param v The Vector force to apply
*/
public void applyForce(Vector v)
{
force.x += v.x;
force.y += v.y;
}
/** Applies a force to this physical that is exactly its
* opposite, thereby making it negative. Useful for ground and
* anything else that may deflect a Physical entirely.
*/
public void applyOppositeForce()
{
force.x *= -1;
force.y *= -1;
}
/** Applies an opposite force to the current one while
* also multiplying it by a certain factor. This is
* called by the Ground when it deflects a Physical.
*/
public void applyForceFactor(float factor)
{
force.x *= -factor;
force.y *= -factor;
}
/** Manually set the force to this value. Can be useful for
* some spells with fixed effects or targets that should not
* be affected by the Ground and Arena.
* @param v The Vector to set the force to
*/
public void setForce(Vector v)
{
force = v;
}
/** Change the mass of this physical to this value. Can be
* useful for explosions and other effects that need changing mass.
* @param m The float value to change the mass to.
*/
public void setMass(float m)
{
mass = m;
}
/**
* Move the location of this Physical as is appropriate
* with its current force. Also contains logic to see
* what is should do about level boundaries.
*/
public void move()
{
x += force.x;
y += force.y;
//If below the bottom of the screen
if (y+height/2 >= Global.SCREEN_SIZE.height)
{
if (!Global.WRAPPING_FLOOR)
Arena.remove(this);
else
y = -height/2;
}
//If above the top of the screen
else if (y+height/2 <= 0)
{
if (!Global.OPEN_CEILING)
force.y *= -1;
}
//If past the left or right side of the screen
if (x+width/2 >= Global.SCREEN_SIZE.width || x-width/2 <= 0)
{
if (Global.WRAPPING_WALLS)
{
if (x-width/2 <= 0)
x = Global.SCREEN_SIZE.width+width/2-1;
else
x = -width/2+1;
}
else
force.x *= -1;
}
}
/** Change the location of this Physical manually.
* @param newX The new x location of the top left corner
* @param newY The new y location of the top left corner
*/
public void move(float newX, float newY)
{
x = newX;
y = newY;
}
/**
* Directly move the location of this Physical manually.
* @param deltaX The change in x to move
* @param deltaY The change in y to move
*/
public void moveTo(float deltaX, float deltaY)
{
x += deltaX;
y += deltaY;
}
/**
* Resize this Physical, can be useful for some spells
* and for explosions.
* @param w The new width
* @param h The new height
*/
public void resize(int w, int h)
{
width = w;
height = h;
}
public java.awt.Point collided(Physical p)
{
try
{
int[] size = new int[4];
BufferedImage b = p.bounds(); Vector o = p.position();
//If hitTest rectangles intersect, check for pixel-by-pixel collision
Rectangle r = new Rectangle((int)o.x,(int)o.y,(int)o.x+b.getWidth(),(int)o.y+b.getHeight());
if (r.intersects(new Rectangle((int)x,(int)y,(int)width,(int)height)))
{
//Cycle through all pixels within the colliding physical
if (b.getWidth()*b.getHeight() < width*height)
return collisionHelper(b,p.position(),bounds(),new Vector(x,y),size);
else
return collisionHelper(bounds(),new Vector(x,y),b,p.position(),size);
}
}
catch (Exception e) {}
return null;
}
public java.awt.Point collided(BufferedImage b, Vector o)
{
try
{
int[] size = new int[4];
//If hitTest rectangles intersect, check for pixel-by-pixel collision
Rectangle r = new Rectangle((int)o.x,(int)o.y,(int)o.x+b.getWidth(),(int)o.y+b.getHeight());
if (r.intersects(new Rectangle((int)x,(int)y,(int)width,(int)height)))
{
//Cycle through all pixels within the colliding physical
if (b.getWidth()*b.getHeight() < width*height)
return collisionHelper(b,o,bounds(),new Vector(x,y),size);
else
return collisionHelper(bounds(),new Vector(x,y),b,o,size);
}
}
catch (Exception e) {}
return null;
}
private java.awt.Point collisionHelper(BufferedImage a, Vector aPos, BufferedImage b, Vector bPos, int[] size)
{
for (int i = 0; i < a.getWidth(); i++)
{
for (int j = 0; j < a.getHeight(); j++)
{
//If this point is not transparent (i.e. is existant)
if (a.getRaster().getPixel(i,j,size)[3] != 0)
{
//TODO FIX THIS I NEED P TO BE RIGHT, AND BOUNDS TO BE RIGHT
//If the matching point within the ground is also not transparent, we have collision.
if (b.getRaster().getPixel((int)(bPos.x+aPos.x+i),(int)(bPos.y+aPos.y+j),size)[3] != 0)
return new java.awt.Point((int)(i+aPos.x),(int)(j+aPos.y));
}
}
}
return null;
}
/**
* Draw the Physical, this is abstract, as generic Physicals
* don't have anything to draw.
* @param g The Graphics context to draw onto.
*/
public void draw(java.awt.Graphics g) {}
}
You could try circular or elliptical collision checks instead of rectangles. These tend to match animal and human shapes more accurately.
It’s better to think in geometrical rather than pixel-based terms if you can. Pixel checking is slow, especially when there’s lots of sprites to check.
what I was doing for pixel colision (in ASM, long long time ago… :’() test was to generate a list of the “border pixel” for each sprite, it make computation of colision pretty fast, generating this list is really simple ( just compare neigbourg pixel with background sprite color ) and give high performance improvment.
then you got two solutions : per pixel test on a fixed(limited) lenght of displacement, or a segment to segment test collision for each border pixels
That’s a very good idea unless you have situations where the two objects can overlap (i.e. something going 50 px / ts actually moves all 50 pixels at once, thereby allowing one object to be inside another), in which case it may not work. But I guess you could just move everything in a for loop 1 pixel at a time and in 99% of the cases you probably still end up with less collision comparisons than doing absolutely all the pixels.
What I find also helps is just to make sure you have very few large objects colliding with other. Like if you have a small character in a very large world, it’s still very cheap to check collisions because you only need to iterate over the small character’s pixels. In this way, I’ve had very high-res backgrounds colliding against many many different objects with fine speed just because the objects themselves were rather small.
Just thinking here, but maybe you could do some sort of spatial collision test like a quad tree that has granularity down to a pixel level. So you can just keep checking different levels of definition for collision until you get a result. Like this:
boolean collides(rectA, rectB)
{
if (rectA collidesWith rectB)
{
return (collides(rectA, subRectTopLeft(rectB));
return (collides(rectA, subRectTopRight(rectB));
return (collides(rectA, subRectBottomLeft(rectB));
return (collides(rectA, subRectBottomRight(rectB));
}
}
Obviously that’s missing a ton of logic, like comparing actual pixels, and rectA would also need to be split up to get correct definition, but I think in the average case you’d end up with very few comparisons, even with very large images.
[quote]That’s a very good idea unless you have situations where the two objects can overlap
[/quote]
that why I was talking about two cases, pixel to pixel if you take care of not moving too fast and segment to segment (each border pixel for a sprite moved represent a segment).
the last solution is the best and pixel perfect (even with huge move) also the equation for each border pixel of a sprite moving will be the same with only one constant difference something like ax+b (with b changing for each pixels) or (x0+vxt ; y0+vy*t) with x0 & y0 changing for each pixel, this should enable good improvement for implementng this solution, inded in addition before doing such perpixel(segment/segment) test, a simple bounding box test will avoid the need to compute most of them.
that why I was talking about two cases, pixel to pixel if you take care of not moving too fast and segment to segment (each border pixel for a sprite moved represent a segment).
the last solution is the best and pixel perfect (even with huge move) also the equation for each border pixel of a sprite moving will be the same with only one constant difference something like ax+b (with b changing for each pixels) or (x0+vxt ; y0+vy*t) with x0 & y0 changing for each pixel, this should enable good improvement for implementng this solution, inded in addition before doing such perpixel(segment/segment) test, a simple bounding box test will avoid the need to compute most of them.
[/quote]
Oh, yeah. I guess I didn’t fully read your post, my fault.
[quote]Oh, yeah. I guess I didn’t fully read your post, my fault.
[/quote]
I do that often too
going further :
1 - using boundingbox collision determine if two sprite can collide
2 - if not continue
3 - if they can collide, compute sprite 1 displacment in frame of reference of sprite 2 (so only one sprite is moving for the next step, and computation is more easy/fast)
4 - pre-compute some sprite 1 displacment equation parameters (common for each pixels moving)
5 - test if one segment draw by each border pixel of sprite 1 (moved in sprite 2 frame of reference) go trought one pixel of sprite 2
6 - if colliding, compute back the resulting xcolid,ycolid collision pos found in the original frame of reference (world space)