Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (604) Games in Android Showcase (171) games submitted by our members Games in WIP (653) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 collision between a rect and a circle?  (Read 3163 times) 0 Members and 1 Guest are viewing this topic.
CyanPrime
 « Posted 2010-05-14 12:14:35 »

Okay, I'm trying to create a method to handle collisions between a rect and a circle. this is how far I've gotten, but now I'm stumped. It only works properly if px and py < the circles center.

Here's the method
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 `    public boolean col(){       float planeAngle = (float) Math.toDegrees(Math.atan2(px - (px + pwidth), -(py - py)));       float planeWidth = rotate(px + pwidth,py + pheight, px,py,planeAngle,true);       float planeHeight = rotate(px + pwidth,py + pheight, px,py,planeAngle,false);       float planeCentX = (planeWidth/2);       float planeCentY = (planeHeight/2);              float dist = (float) Math.sqrt(Math.pow((bx + (bsize/2)) - planeCentX, 2) + Math.pow(-((by + (bsize/2)) - planeCentY), 2));       if(dist <= (bx + (bsize/2)))          return true;                 else          return false;    }`

and here is the full source: (requires slick)
 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 `import org.newdawn.slick.AppGameContainer;import org.newdawn.slick.BasicGame;import org.newdawn.slick.GameContainer;import org.newdawn.slick.Graphics;import org.newdawn.slick.Input;import org.newdawn.slick.SlickException;public class ColTest extends BasicGame{       float px = 50;   float py = 50;   float pheight = 50;   float pwidth = 50;      float bx = 200;   float by = 200;   float bsize = 200;      float pspeed = 3;    Input input;        public ColTest()    {        super("ColTest");    }     @Override    public void init(GameContainer gc)         throws SlickException {             }    @Override    public void update(GameContainer gc, int delta)         throws SlickException   {       input = gc.getInput();              try{             if(input.isKeyDown(Input.KEY_UP))                 py-=pspeed;                    if(input.isKeyDown(Input.KEY_DOWN))                 py+=pspeed;                    if(input.isKeyDown(Input.KEY_LEFT))                 px-=pspeed;                    if(input.isKeyDown(Input.KEY_RIGHT))                 px+=pspeed;       }              catch(Exception e){}   }     public void render(GameContainer gc, Graphics g)         throws SlickException    {             g.drawString("col: " + col(), 10, 10);          g.fillRect(px, py, 50, 50);          g.fillOval(200, 200, 200, 200);    }        public boolean col(){       float planeAngle = (float) Math.toDegrees(Math.atan2(px - (px + pwidth), -(py - py)));       float planeWidth = rotate(px + pwidth,py + pheight, px,py,planeAngle,true);       float planeHeight = rotate(px + pwidth,py + pheight, px,py,planeAngle,false);       float planeCentX = (planeWidth/2);       float planeCentY = (planeHeight/2);              float dist = (float) Math.sqrt(Math.pow((bx + (bsize/2)) - planeCentX, 2) + Math.pow(-((by + (bsize/2)) - planeCentY), 2));       if(dist <= (bx + (bsize/2)))          return true;                 else          return false;    }        public float rotate(float x, float y, float ox, float oy, float a, boolean b)    {         float dst = (float) Math.sqrt(Math.pow(x-ox,2.0)+ Math.pow(y-oy,2.0));         float oa = (float) Math.atan2(y-oy,x-ox);         if(b)            return (float) Math.cos(oa + Math.toRadians(a))*dst+ox;         else            return (float) Math.sin(oa + Math.toRadians(a))*dst+oy;    }        public static void main(String[] args)         throws SlickException    {         AppGameContainer app =         new AppGameContainer( new ColTest() );          app.setShowFPS(false);         app.setAlwaysRender(true);         app.setTargetFrameRate(60);         app.setDisplayMode(800, 600, false);         app.start();    }}`
Roquen
 « Reply #1 - Posted 2010-05-14 12:17:31 »

You'll probably get a faster response if you ask a question that doesn't require the reader to figure out your code to understand what is being asked.

Circle to Rect:  Can the rectangle be rotated?
CyanPrime
 « Reply #2 - Posted 2010-05-14 12:28:28 »

Circle to Rect:  Can the rectangle be rotated?
Yeah, it can.
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #3 - Posted 2010-05-14 18:49:03 »

The key thing to remember here is that you just need to distill this down into the possible cases. What are the different things that can happen?

- The circle can be outside the rectangle (no collision).
- The circle can touching one of the vertices of the rectangle only.
- The circle can be touching one of the sides of the rectangle.
- The circle can be touching any number of sides as well as any number of vertices.
- The rectangle can lie inside the circle.
- The circle can lie inside the rectangle.

Calculating every single one of those would take a lot of time, thinking, and waste a lot of cycles, but you would probably be able to figure out a way to do each step if your geometry is pretty good. But after doing them all you'd probably realize that there are a lot of redundant cases there.

- If the circle is touching just one vertex, that means that it's also touching two different line segments.
- if the circle is touching multiple sides or vertices, then you should only need to check the first side it's touching and then know there is collision.
- If the rectangle lies inside the circle, then that's equivalent to all 4 sides touching the circle.

So that simplifies us to:

- The circle can be outside the rectangle (no collision).
- The circle can be touching one of the sides of the rectangle.
- The circle can lie inside the rectangle.

We don't need to worry about checking for the first case, because we know if either of the last two cases are true then the first case can't be true. So that leaves just two.

- The circle can be touching one of the sides of the rectangle.
- The circle can lie inside the rectangle.

And to simplify even more, you know that the circle lies inside the rectangle, if it gets too close to a side then that means that it will intersect that side, so all you really need to do is see if the center of the circle lies inside the rectangle - its radius doesn't even matter.

Google should be able to tell you how to do circle/segment collision (essentially you see if the radius segment that is perpendicular to the line segment intersects the line segment), and also how to find whether or not a point lies inside a rectangle (compare 4 dot products for the perpendiculars of each line, basically).

Or, have a look here:
http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection
http://local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/
http://stackoverflow.com/questions/2752725/finding-whether-a-point-lies-inside-a-rectangle-or-not

See my work:
OTC Software
 « Reply #4 - Posted 2010-05-15 03:53:03 »

Circle to Rect:  Can the rectangle be rotated?

Rotate the axis.
Abuse

JGO Knight

Medals: 28

falling into the abyss of reality

 « Reply #5 - Posted 2010-05-15 13:30:19 »

Are either the circle or rectangle in motion?

If so, you need to intersect the swept volumes, not just the static shapes.
To not do so will lead to pass-through, (to a lesser or greater extent, depending on your time step & object velocities)

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #6 - Posted 2010-05-15 17:16:53 »

Are either the circle or rectangle in motion?

If so, you need to intersect the swept volumes, not just the static shapes.
To not do so will lead to pass-through, (to a lesser or greater extent, depending on your time step & object velocities)
Yes, this is true.

By swept volume he means if you were to draw a circle at previousPos, then another one at destinationPos, then draw two lines to connect the circles (to end up with a sort of cylinder), and calculate collision that way.

See my work:
OTC Software
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1019
Projects: 4
Exp: 16 years

 « Reply #7 - Posted 2010-05-15 20:16:20 »

Oh man, there is this not-so-fine line between correctness and helpfulness.

Hi, appreciate more people! Î£ â™¥ = Â¾
Learn how to award medals... and work your way up the social rankings!
Nate

« JGO Bitwise Duke »

Medals: 165
Projects: 4
Exp: 14 years

Esoteric Software

 « Reply #8 - Posted 2010-05-16 00:20:41 »

Is the circle in a bad mood? How does the rectangle feel about the circle's possible intersection?

Is Riven's circle of vagueness intersecting the not-so-fine line of helpfulness? Signs say yes.

Riven
« League of Dukes »

« JGO Overlord »

Medals: 1019
Projects: 4
Exp: 16 years

 « Reply #9 - Posted 2010-05-16 00:25:03 »

What I tried to say discretely, was that if this poor boy is struggling with circle/rect intersections, it's absolutely no help to him to even mention swept circle/rect intersections.

Hi, appreciate more people! Î£ â™¥ = Â¾
Learn how to award medals... and work your way up the social rankings!
SimonH
 « Reply #10 - Posted 2010-05-16 02:08:21 »

1. Get the distance and angle from the centre of the rectangle to the centre of the circle (using sqrt() and atan2()).
2. Clip this line to the rectangle (you can use tan(angle) on the relevant side/sides to do this) & get the length of the clipped line (if no clipping is required then a collision is certain - the centre of the circle must lie inside the rectangle).
3. Now if clipped_length+circle_radius<distance_between_centres then there is no collision.

Not very efficient and could indeed get iffy if either shape is moving fast, but it should generally work...

People make games and games make people
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #11 - Posted 2010-05-16 07:10:58 »

Here's an easy (and totally inefficient) way to do this:

- Implement normal circle / rectangle collision, as we talked about above.
- As an object moves, instead of moving it its full distance, move it one pixel at a time, checking for collision after each movement. If it would collide with something as part of its movement, then you will be able to stop it within the precision of one pixel, which is obviously all the granularity you need for it to look fine to the player.

As I said, it's easy to implement but very very wasteful. But it works. If you don't have too many entities and your circle / rectangle collision algorithm is fast enough, this should suit you just fine.

See my work:
OTC Software
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #12 - Posted 2010-05-16 08:44:33 »

1. Get the distance and angle from the centre of the rectangle to the centre of the circle (using sqrt() and atan2()).
2. Clip this line to the rectangle (you can use tan(angle) on the relevant side/sides to do this) & get the length of the clipped line (if no clipping is required then a collision is certain - the centre of the circle must lie inside the rectangle).
3. Now if clipped_length+circle_radius<distance_between_centres then there is no collision.

Not very efficient and could indeed get iffy if either shape is moving fast, but it should generally work...

Demonpants has posted the answer: Check for the circle center lying inside the rectangle (4 dot products), check for the rectangle edges intersecting the circle (4 closest-point-on a line-segment and distance checks).
Don't worry about motion until you know it's a problem.
SimonH
 « Reply #13 - Posted 2010-05-17 01:33:48 »