Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (109)
games submitted by our members
Games in WIP (537)
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  
  The perfect solution to handling circle and rectangle collisions  (Read 4013 times)
0 Members and 1 Guest are viewing this topic.
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Posted 2013-09-13 17:47:30 »

This problem has bothered me for years (solving it linearly and quickly) and I finally got it today:

http://stackoverflow.com/questions/18704999/how-to-fix-circle-and-rectangle-overlap-in-collision-response/18790389#18790389

I always had weird problems with my breakout/pong clones, but no more!

Offline Several Kilo-Bytes

Senior Member


Medals: 11



« Reply #1 - Posted 2013-09-13 19:46:45 »

I see that you're using the law of sines. That's pretty clever, I assume, but it's a long source excerpt so I will have to read and think about it for a while. I imagine that there is a shorter way, but it's not a collision type I have had to use recently, so I don't know how I would solve it either.

I noticed a user named ClickerMonkey asked, "I assume it's safe to say that the rectangle is stationary?" If I had an account at StackOverflow I would remind that user that collision between two moving objects can be solved by subtracting the velocity of one object from both objects' velocities and using a dynamic/stationary collision test with the new velocities. (Since one object's velocity becomes zero and the motion of the two objects are relative to each other.)
Offline pploco1996

Junior Member


Medals: 2
Exp: 1 year



« Reply #2 - Posted 2013-09-13 20:23:20 »

I'd just use box2d
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #3 - Posted 2013-09-13 20:53:34 »

I'd just use box2d

Which uses a slower and less exact method.

I see that you're using the law of sines. That's pretty clever, I assume, but it's a long source excerpt so I will have to read and think about it for a while. I imagine that there is a shorter way, but it's not a collision type I have had to use recently, so I don't know how I would solve it either.

I don't like using trig functions, so I as well am pondering on another method.

I noticed a user named ClickerMonkey asked, "I assume it's safe to say that the rectangle is stationary?" If I had an account at StackOverflow I would remind that user that collision between two moving objects can be solved by subtracting the velocity of one object from both objects' velocities and using a dynamic/stationary collision test with the new velocities. (Since one object's velocity becomes zero and the motion of the two objects are relative to each other.)

I didn't think about if for a second when I made that comment, for some reason I thought there would be a problem when it came to resolution... but there wouldn't be.

I also updated the pastebin code to be more efficient and return more information.

Offline Abuse

JGO Coder


Medals: 11


falling into the abyss of reality


« Reply #4 - Posted 2013-09-14 03:12:01 »

rotating rectangle = head explosion.

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

JGO Coder


Medals: 20


Game Engineer


« Reply #5 - Posted 2013-09-14 04:46:26 »

Nah, just build a matrix that rotates the rectangle and circles start and end points so that the rectangle is axis-aligned, then use the inverse of that matrix to adjust the intersection points and normal. Wouldn't be that much work XD

Heck you don't even need a matrix, just store {cos,sin} in a vector and use the vector rotate and unrotate method (given you have or know how to implement that method).

Online Roquen
« Reply #6 - Posted 2013-09-14 12:59:49 »

Keep it simple - see near the end of this thread: http://www.java-gaming.org/topics/vectors-what-s-the-point/24307/view.html
Offline relminator
« Reply #7 - Posted 2013-09-15 01:25:56 »

I see that you're using the law of sines. That's pretty clever, I assume, but it's a long source excerpt so I will have to read and think about it for a while. I imagine that there is a shorter way, but it's not a collision type I have had to use recently, so I don't know how I would solve it either.

I noticed a user named ClickerMonkey asked, "I assume it's safe to say that the rectangle is stationary?" If I had an account at StackOverflow I would remind that user that collision between two moving objects can be solved by subtracting the velocity of one object from both objects' velocities and using a dynamic/stationary collision test with the new velocities. (Since one object's velocity becomes zero and the motion of the two objects are relative to each other.)

Yar! Swept tests ftw!

OP:  Why not use SAT? It could handle OBBs vs Circles efficiently.
Offline Abuse

JGO Coder


Medals: 11


falling into the abyss of reality


« Reply #8 - Posted 2013-09-15 01:37:07 »

Nah, just build a matrix that rotates the rectangle and circles start and end points so that the rectangle is axis-aligned, then use the inverse of that matrix to adjust the intersection points and normal. Wouldn't be that much work XD

Heck you don't even need a matrix, just store {cos,sin} in a vector and use the vector rotate and unrotate method (given you have or know how to implement that method).

Rotating, not rotated.

The swept volume of a moving, rotating object is nontrivial.

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

JGO Coder


Medals: 20


Game Engineer


« Reply #9 - Posted 2013-09-15 05:16:11 »

Keep it simple - see near the end of this thread: http://www.java-gaming.org/topics/vectors-what-s-the-point/24307/view.html

I wanted to account for moving through objects and skipping corners, not hitting corner's correctly, etc. Mine is essentially a rectangle-capsule intersection with time and intersection data.

OP:  Why not use SAT? It could handle OBBs vs Circles efficiently.

If I remember SAT correctly, it doesn't account for time... sure it checks for intersections, but I want perfect resolution on top of that detection.

Rotating, not rotated.

Ahh, I wasn't paying that much attention... yeah rotating is mind boggling. I don't think a "straightforward" solution exists for that problem... I'm sure there's a linear solution if you break it out into all scenarios... but it might be quicker to just use detection + smaller deltatimes + more iterations.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Roquen
« Reply #10 - Posted 2013-09-15 08:54:51 »

I wasn't clear. An oriented rectangle is trivial from an un-oriented.  A rotation rectangle is the same as oriented, unless you're not keeping it simple.  You shouldn't be attempt to simulate a real world device...you give the player a plausible simulation that doesn't break their expectations.  Real physics that the player cannot even notice doesn't make anything fun.
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #11 - Posted 2013-09-15 13:57:02 »

I wasn't clear. An oriented rectangle is trivial from an un-oriented.  A rotation rectangle is the same as oriented, unless you're not keeping it simple.  You shouldn't be attempt to simulate a real world device...you give the player a plausible simulation that doesn't break their expectations.  Real physics that the player cannot even notice doesn't make anything fun.

Every time I've tried to make a breakout clone (note: I haven't tried in years), I would ALWAYS get collision detection bugs where I KNEW the ball should've hit one side and not the other, or it skipped a corner, or it destroyed to many blocks... etc.

Every time I made a pong clone I never got the correct bounce off corners, that was frustrating to see.

I would agree with you if I was taking into account rotational inertia of the ball or something... but I'm not. My solution is not "more realistic physics", it's simply "perfect" so that the player NEVER gets frustrated with typical crappy collision detection and poor resolution.

Of course if you have high FPS and slow balls... my formula might not help you that much... but it definitely helps with fast moving objects.

Offline relminator
« Reply #12 - Posted 2013-09-15 16:42:22 »


OP:  Why not use SAT? It could handle OBBs vs Circles efficiently.

If I remember SAT correctly, it doesn't account for time... sure it checks for intersections, but I want perfect resolution on top of that detection.



SAT and what roquen suggested should not account for time.  You maybe overcomplicating this.

Just do a "swept test" like someone suggested above and use sat or what roquen posted.
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #13 - Posted 2013-09-15 18:29:56 »

You're missing the point of this, the whole "update positions, check for intersections, and shoddily correct them" isn't sufficient sometimes, especially for fast moving objects (i.e. a ball).

My suggested method is *fast*, it's not "over complicated". If you can't acknowledge it's superior, then you're clearly not understanding it's utility... and are biased or doesn't like change. I'm not asking you to change... if you want estimated collision resolution instead of perfect, then do it your way. I'm simply stating that IF you want perfect collision detection (umm... why wouldn't you?) then my algorithm can do that for circles and rectangles in motion.

No game player wants buggy collision resolution to negatively effect the game play, it's important what angles and sides a ball hits when that is the point of the game... you can't perfect your skills and be more accurrate at playing if the game is not deterministic (in the collision resolution sense).

/soapbox






Offline Several Kilo-Bytes

Senior Member


Medals: 11



« Reply #14 - Posted 2013-09-15 19:43:53 »

There are two types of collision tests. One where you move everything and say, "Since I didn't overlap with any objects before I moved and did not overlap with any objects after I moved, there must not be any objects between my last position and my next position to impede me." The other says "I know where I am and how fast I am relative to other object. I should see how far I can move before colliding with something."

Wikipedia refers to the former as a posteriori and the latter as a priori. Personally, I only consider a priori to be collision detection, though I know this is not the standard vocabulary. Collision is something that involves moving objects. If both objects are stationary, then it's an intersection test. (The special case of a point against another shape is called a hit test.)

If you use "intersection" or "hit test" in your search terms you will always get your intended topic (a posteriori). It's entirely different from collision tests and the strengths of the algorithms are different. It has applications in GUIs (non-games included) and may give you information you can't find / don't need from collision tests (like overlapping areas). Unfortunately people do not use the same vocabulary I wish every else did, so "collision test" yields a posteriori tests as well as a priori. A posteriori works for large, slow moving objects with short time steps. There are lots of serious flaws so common that players know them when they see them, like falling through floors, walking through walls, getting stuck in geometry, and unrealistic rebounds. There are work arounds, but it's like adding duct tape to a machine trying to do something it was never made to do. Eventually the work arounds are ten times as complex as an a priori algorithm and are usually slower. It leads to hard to track down bugs for programmers, mandatory hacks for level designers, and glitchy games for players.

Looking at collisions a priori saves a lot of development time in the long run and makes the game run smoother.
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #15 - Posted 2013-09-15 19:47:52 »

Brilliantly said, and thanks for the new information =)

Online Roquen
« Reply #16 - Posted 2013-09-15 20:00:55 »

There's still a misunderstanding.  I'm not commenting either way on CM's implementation.  Intersection test or collision test, continuous or discrete there is no real added complication of a sphere or capsule vs rectangle when the rectangle is at the origin and axis aligned, arbitrary point in space, oriented or rotating.
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #17 - Posted 2013-09-15 20:47:07 »

There's still a misunderstanding.  I'm not commenting either way on CM's implementation.  Intersection test or collision test, continuous or discrete there is no real added complication of a sphere or capsule vs rectangle when the rectangle is at the origin and axis aligned, arbitrary point in space, oriented or rotating.

Are you talking WRT to SAT? If so, I see what your saying... your statement is valid. If you're not talking WRT to SAT then I'm confused, of course a rotating rectangle complicates things... in the sense that you can have a simple algorithm for a static rectangle and you have to make a more "complicated" one for a rotating one.

Online Roquen
« Reply #18 - Posted 2013-09-15 22:26:12 »

SAT or not doesn't change anything.  Either you account for a time varying orientation change of the rect during your fixed simulation time-step or you ignore it and treat it as if it is not varying for collision determination.  The latter is simple and the player cannot notice that you're not doing the former.  So it's not worth waste either your time nor the CPUs.  (Well in any case worth talking about...for anything else the rule is "don't write physics engines".)
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #19 - Posted 2013-09-17 20:12:32 »

The pastebin has been updated so you can just paste the code and run it, you don't need my library or anything.

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.

CogWheelz (16 views)
2014-08-01 22:53:16

CogWheelz (15 views)
2014-08-01 22:51:43

CopyableCougar4 (18 views)
2014-08-01 19:37:19

CogWheelz (19 views)
2014-07-30 21:08:39

Riven (27 views)
2014-07-29 18:09:19

Riven (16 views)
2014-07-29 18:08:52

Dwinin (14 views)
2014-07-29 10:59:34

E.R. Fleming (42 views)
2014-07-29 03:07:13

E.R. Fleming (13 views)
2014-07-29 03:06:25

pw (44 views)
2014-07-24 01:59:36
Resources for WIP games
by CogWheelz
2014-08-01 18:20:17

Resources for WIP games
by CogWheelz
2014-08-01 18:19:50

List of Learning Resources
by SilverTiger
2014-07-31 18:29:50

List of Learning Resources
by SilverTiger
2014-07-31 18:26:06

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

HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22
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!