This problem has bothered me for years (solving it linearly and quickly) and I finally got it today:
I always had weird problems with my breakout/pong clones, but no more!
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.)
I’d just use box2d
Which uses a slower and less exact method.
I don’t like using trig functions, so I as well am pondering on another method.
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.
rotating rectangle = head explosion.
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).
Keep it simple - see near the end of this thread: http://www.java-gaming.org/topics/vectors-what-s-the-point/24307/view.html
Yar! Swept tests ftw!
OP: Why not use SAT? It could handle OBBs vs Circles efficiently.
Rotating, not rotated.
The swept volume of a moving, rotating object is nontrivial.
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.
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.
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.
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.
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.
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
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.
Brilliantly said, and thanks for the new information =)
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.
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”.)
The pastebin has been updated so you can just paste the code and run it, you don’t need my library or anything.