I have setup pixel perfect collision detection between two objects. It’s working well. Now I got this situation.
And now I want to align them such that no collision happens just like this.
I’m using fixed step game loop with each step having 30 ms. To do this I need to find the depth of intersection. How will you do this?
PS: I’m using Java2D
I assume your problem is that the colliding objects are moving faster than one pixel a second, and thus go too far even with a perfect collision system? Correct me if I’m wrong
Yes. The velocity of the second object is around 4 pixels per second. The first one is stationary.
There’s a problem with this approach once you go past having two objects. Let’s say you have 3 objects, object A, B and C.
The thing is that this isn’t anything rare. Put three boxes on top of each other (like a pyramid) and you already have a situation like that.
There are other folks probably more experienced with this than me, but I will offer a couple ideas and hope that they aren’t too impractical. (It is either that or go back to doing my last-minute tax returns.)
(1) If, when you get the collision indication you know the velocity, you could try a binary successive approximation: try half the move–collided or not? try 1/4 move or 3/4 move depending upon the first answer, etc. Continue until the fraction is equal to a move of one pixel.
(2) If, when you get a collision indication, you could go back to the previous point and do a successive sweep, 1 pixel velocity at a time, until you hit. (Also possible to do a backwards moving sweep test, I would think.)
(3) Whether there is a geometrical solution, that would depend on the shapes, I would guess. It would be cool if there was a way to return the intersection of the two shapes and calculate the width at the angle of the impact. I don’t know if there is such a thing, though, or if this would be any less computationally intensive than just doing one of the above series of collision tests.
(4) I’m trying to recall what I did for the simple case of bouncing off of a wall…drawing a blank. Maybe it was a matter of taking the destination and placing the object on the symmetric point on the correct side of the wall. Seems like there might be a geometric calculation available from that to find the point of collision, but the odd shapes you have make it trickier.
(5) Ah, found a start of an old game of mine with falling objects of various shapes. I just had the object stop/lose it’s momentum at the position before overlap. It would settle down (using gravity) from there. Looks a little funky though. It will be interesting to see if anyone else has a better solution.
The sweep or “binary search” might not be so bad, though. If the speed is only a few pixels per frame, that’s only a couple extra collision tests on the occasion of an overlap state arising.
Thanks for answering. However I’m having some doubts.
Doesn’t checking collisions multiple times cause slowing in game?
And how would you implement gravity? I’ll just use a greater vertical velocity for it.
Well, not checking for collision at each step could cause your object to jump through other objects.
Say object A is 10x10 pixels and moves to the right with a speed of 20px/tick, it starting position is (0, 10), measured from the top left corner, now at (15, 15) there’s an object which is 2x2 pixels in size. This object will be completely ignored if you only check for collision at (0, 10), (20, 10), (40, 10), etc. etc.
I hope this makes a little sense. 
Cheers! 
Here’s some keywords to set you on the right track:
swept volume, convex polygon, separating axis theorem.
As to the issue of multiple collisions between more than 2 actors;
IMHO The best options is: don’t write physics systems.
Roquen got it right.
However if you are still trying to do it yourself, the only way to do this is a game is to cheat. Game physics engines cheat. Plain and simple. Cheating for this sort of thing means permitting some overlap. Usually providing some extra force to push it out of overlap, but not too much or it will fly off the screen.
If you look carefully at most games, you can see lots of overlapping objects.
Think I was going too deep. I’ve started searching all this because in the platform game I’m making, the player’s collision isn’t detected unless he’s two pixels in. When I adjust him to the value using
player.setY(block.y - player.getHeight());
I’m able to see a gap between them. The gravity again pulls him into it. This is resulting in the player just moving some up and down in the game.
Previously I’ve used GameMaker. The same in it (with precise collisions) was accurate. There was a function named [icode]move_contact_solid()[/icode] which moved the player accurate to the floor. I wanted to do the same but don’t know how to implement that function.
So I started searching ways.
[quote]Doesn’t checking collisions multiple times cause slowing in game?
[/quote]
Best answer I can think of: try it and see. I am constantly being surprised by what consumes time and what doesn’t.
How many collisions are there per second? If you have one or two, and are animating at 60fps, that’s 58 game loops which are unaffected.
A few extra tests won’t make much difference. How many nanos or microseconds per test? Also, collision testing is just one of the things that happens in a game cycle, so as a percentage of time consumption, it could be very minor.