Hi !
Featured games (85)
games approved by the League of Dukes
Games in Showcase (636)
Games in Android Showcase (178)
games submitted by our members
Games in WIP (687)
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  
  Finding the time at which intersection takes place.  (Read 1070 times)
0 Members and 1 Guest are viewing this topic.
Offline 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

Offline Jimmt
« League of Dukes »

JGO Kernel

Medals: 165
Projects: 5
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
Offline 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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd

« JGO Bitwise Duke »

Medals: 594
Projects: 4
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.

Offline 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.

music and music apps:
Offline SHC
« Reply #5 - Posted 2013-04-15 10:58:16 »


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.

Offline 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. Tongue

Cheers! Smiley
Online Abuse

JGO Ninja

Medals: 42

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!
Offline Roquen
« Reply #8 - Posted 2013-04-15 12:19:00 »

IMHO The best options is: don't write physics systems.
Offline 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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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

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
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.

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

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.

music and music apps:
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Dwinin (72 views)
2015-11-07 13:29:08

Rems19 (81 views)
2015-10-31 01:36:56

Rems19 (74 views)
2015-10-31 01:32:37

williamwoles (107 views)
2015-10-23 10:42:59

williamwoles (92 views)
2015-10-23 10:42:45

Jervac_ (106 views)
2015-10-18 23:29:12

DarkCart (134 views)
2015-10-16 00:58:11

KaiHH (116 views)
2015-10-11 14:10:14

KaiHH (156 views)
2015-10-11 13:26:18

BurntPizza (171 views)
2015-10-08 03:11:46
Rendering resources
by Roquen
2015-11-13 14:37:59

Rendering resources
by Roquen
2015-11-13 14:36:58

Math: Resources
by Roquen
2015-10-22 07:46:10

Networking Resources
by Roquen
2015-10-16 07:12:30

Rendering resources
by Roquen
2015-10-15 07:40:48

Math: Inequality properties
by Roquen
2015-10-01 13:30:46

Math: Inequality properties
by Roquen
2015-09-30 16:06:05

HotSpot Options
by Roquen
2015-08-29 11:33:11 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‑
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!