Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (579)
games submitted by our members
Games in WIP (500)
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 600 times)
0 Members and 1 Guest are viewing this topic.
Offline SHC
« Posted 2013-04-15 07: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

Online Jimmt
« League of Dukes »

JGO Kernel


Medals: 114
Projects: 4
Exp: 3 years



« Reply #1 - Posted 2013-04-15 07: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 07: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
« Reply #3 - Posted 2013-04-15 09: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.
Offline philfrei
« Reply #4 - Posted 2013-04-15 11: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.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline SHC
« Reply #5 - Posted 2013-04-15 12: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.

Offline Regenuluz
« Reply #6 - Posted 2013-04-15 14: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
Offline Abuse

JGO Coder


Medals: 10


falling into the abyss of reality


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

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

JGO Coder


Medals: 22


Computers can do that?


« Reply #9 - Posted 2013-04-15 15: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 16: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.

Offline philfrei
« Reply #11 - Posted 2013-04-15 21: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.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
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.

xsi3rr4x (35 views)
2014-04-15 18:08:23

BurntPizza (31 views)
2014-04-15 03:46:01

UprightPath (46 views)
2014-04-14 17:39:50

UprightPath (29 views)
2014-04-14 17:35:47

Porlus (46 views)
2014-04-14 15:48:38

tom_mai78101 (67 views)
2014-04-10 04:04:31

BurntPizza (127 views)
2014-04-08 23:06:04

tom_mai78101 (227 views)
2014-04-05 13:34:39

trollwarrior1 (192 views)
2014-04-04 12:06:45

CJLetsGame (199 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
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!