Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (552)
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 perfect collision  (Read 5891 times)
0 Members and 1 Guest are viewing this topic.
Offline luisoft

JGO Coder


Projects: 6


Java games rock!


« Posted 2011-01-18 18:42:39 »

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/topics/panicky-penguin/23669/view.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!
Offline SimonH
« Reply #1 - Posted 2011-01-18 18:57:56 »

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!

People make games and games make people
Offline Captain Awesome

Junior Member


Medals: 2


Hi


« Reply #2 - Posted 2011-01-18 19:05:07 »

http://pastebin.com/DbK677qW

My updated Sprite-class, feel free to use it or parts of it Smiley
It has support for pixel-perfect collisions
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline luisoft

JGO Coder


Projects: 6


Java games rock!


« Reply #3 - Posted 2011-01-18 19:06:39 »

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... Sad
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #4 - Posted 2011-01-18 19:15:54 »

Here is a class I made many many moons ago. Tongue No promises here, but you can at least check out the collision method, as it's simple.

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  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
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) {}
}

See my work:
OTC Software
Offline SimonH
« Reply #5 - Posted 2011-01-18 19:23:21 »

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.

People make games and games make people
Offline DzzD
« Reply #6 - Posted 2011-01-18 20:28:23 »

what I was doing for pixel colision (in ASM, long long time ago... Cry) 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

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #7 - Posted 2011-01-18 21:03:29 »

what I was doing for pixel colision (in ASM, long long time ago... Cry) 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:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
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.

See my work:
OTC Software
Offline DzzD
« Reply #8 - Posted 2011-01-18 21:17:54 »

Quote
That's a very good idea unless you have situations where the two objects can overlap

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 a*x+b (with b changing for each pixels) or (x0+vx*t ; 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.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #9 - Posted 2011-01-18 21:30:21 »

Quote
That's a very good idea unless you have situations where the two objects can overlap

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 a*x+b (with b changing for each pixels) or (x0+vx*t ; 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.
Oh, yeah. Smiley I guess I didn't fully read your post, my fault.

See my work:
OTC Software
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline DzzD
« Reply #10 - Posted 2011-01-18 21:33:31 »

Quote
Oh, yeah. I guess I didn't fully read your post, my fault.

I do that often too Smiley


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)

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 (23 views)
2014-08-22 19:31:30

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

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

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

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

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

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

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

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

Norakomi (41 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!