Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (569) Games in Android Showcase (154) games submitted by our members Games in WIP (618) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Finding the time at which intersection takes place.  (Read 852 times) 0 Members and 1 Guest are viewing this topic.
SHC
 « Posted 2013-04-15 05:13:36 »

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

Jimmt
« League of Dukes »

JGO Kernel

Medals: 159
Projects: 4
Exp: 3 years

 « Reply #1 - Posted 2013-04-15 05:17:19 »

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
SHC
 « Reply #2 - Posted 2013-04-15 05:19:14 »

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.

theagentd

« JGO Bitwise Duke »

Medals: 423
Projects: 2
Exp: 8 years

 « Reply #3 - Posted 2013-04-15 07:44:03 »

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.
- A and B collide at time index 0.5 (= precisely inbetween the current and previous frames), so you solve the collision by going to 0.5 and applying a force to push them away from each other.
- Then you realize that A and C collided at 0.1.
- Oh, and after that you realize that B and C ALSO collided.

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.

Myomyomyo.
philfrei
 « Reply #4 - Posted 2013-04-15 09:01:47 »

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.

"We all secretly believe we are right about everything and, by extension, we are all wrong." W. Storr, The Unpersuadables
SHC
 « Reply #5 - Posted 2013-04-15 10:58:16 »

@philfrei

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.

Regenuluz
 « Reply #6 - Posted 2013-04-15 12:02:32 »

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!
Abuse

JGO Knight

Medals: 17

falling into the abyss of reality

 « Reply #7 - Posted 2013-04-15 12:12:37 »

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;

- check all collisions that occur within the next frame, looking for the earliest.
- step your simulation to that point, and resolve the single collision that occurs.
- repeat until you've processed all collisions that occur that frame.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Roquen
 « Reply #8 - Posted 2013-04-15 12:19:00 »

IMHO The best options is: don't write physics systems.
delt0r

JGO Knight

Medals: 33
Exp: 18 years

Computers can do that?

 « Reply #9 - Posted 2013-04-15 13:30:18 »

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.

I have no special talents. I am only passionately curious.--Albert Einstein
SHC
 « Reply #10 - Posted 2013-04-15 14:02:47 »

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

 1 `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
 `move_contact_solid()`
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.

philfrei
 « Reply #11 - Posted 2013-04-15 19:26:25 »

Quote
Doesn't checking collisions multiple times cause slowing in game?

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.

"We all secretly believe we are right about everything and, by extension, we are all wrong." W. Storr, The Unpersuadables
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Riven (21 views) 2015-04-16 10:48:47 Duke0200 (34 views) 2015-04-16 01:59:01 Fairy Tailz (26 views) 2015-04-14 20:13:12 Riven (26 views) 2015-04-12 21:36:37 bus hotdog (44 views) 2015-04-10 02:39:32 CopyableCougar4 (45 views) 2015-04-10 00:51:04 BurntPizza (45 views) 2015-04-06 22:06:58 ags1 (49 views) 2015-04-02 10:58:48 Riven (49 views) 2015-04-01 18:27:05 ags1 (66 views) 2015-03-31 10:55:12
 BurntPizza 24x theagentd 21x wessles 15x 65K 12x Rayvolution 12x kingroka123 11x alwex 10x KevinWorkman 9x kevglass 8x SHC 8x ra4king 8x phu004 8x Hanksha 7x Olo 7x Ecumene 7x chrislo27 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 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