Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (524)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (592)
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  
  Collision and Movement  (Read 1742 times)
0 Members and 1 Guest are viewing this topic.
Offline Troncoso

JGO Coder


Medals: 20



« Posted 2012-11-25 21:47:15 »

These two things kind of puzzle me a bit. I imagine for some accurate/efficient collision, a decent algorithm would need to be in play. What my real question is, how do you implement collision in a way that it remains accurate, no matter the speed of the objects colliding?

If you don't know what I mean, it's basically that, to move an object across a screen, each frame, the x and/or y position of the object is incremented/decremented according to how fast you want it to appear moving. Well, if an object is moving very fast, then in one frame it'll be at x-coord 20, and then the next, it could be at x-coord 200. Well, if there was an object that it was suppose to collide with at position 100 that was only 50 pixels wide, then there is technically never a point of intersection between the objects. And, if coded to only check if object A has crossed into the bounds of object B, than this would definitely cause problems with detecting the collisions.

I'm going to assume there are movement/collision algorithms available in various places among the net. But, I guess I'm looking for what is most efficient/accurate, and maybe an explanation as to how that is derived.

Thanks in advance!
Offline wreed12345

JGO Knight


Medals: 25
Projects: 2
Exp: 2 years


http://linebylinecoding.blogspot.com/


« Reply #1 - Posted 2012-11-25 22:30:30 »

Instead of detecting if the object cordinates match up with the designated cordinates you could detect if the cordinates are greater then where you want them to . Thats how I did my collision detection.

heres a crude example
1  
2  
3  
if (objectY > targetY) {
//stop object from moving here
}

Offline Troncoso

JGO Coder


Medals: 20



« Reply #2 - Posted 2012-11-25 22:46:58 »

That wouldn't work well at all, especially in situations where the object is allowed to move around the target. You need to check for an actual intersection, rather than just seeing if the position is greater than the target object.

I feel like I need to be able to predict where collisions could occur...which sounds complicated.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline wreed12345

JGO Knight


Medals: 25
Projects: 2
Exp: 2 years


http://linebylinecoding.blogspot.com/


« Reply #3 - Posted 2012-11-25 22:49:51 »

You could easily implement that method to create a collision detected rectangle or square. If your trying to make a circle i have no idea how hahaha

Offline DrHalfway
« Reply #4 - Posted 2012-11-25 23:29:27 »

What you're looking for is "Continuous Collision Detection". Its something that is fairly difficult to get right and does add quite a bit of overhead to the Collision Detection. Most game engines have a hard constant of how fast an object is allowed to travel, for example, it does not try to solve a collision for an object travelling at the speed of light for example. Fast objects skipping collisions because they travel too fast is whats called "Tunneling".

For bullets or extremely fast objects like laser beams you might wish to use Ray casting instead. For Continuous collision detection you can approach it in a number of ways.

1) You can construct a polyhedral type volume from the objects previous position and current position, and perform tests to make sure nothing came in between. This scheme can EASILLY become slower than brute forcing everything.

2) You can perform a Raycast from the objects previous position in the direction of current position, if the ray hits anything it means object has missed a collision, you can re-update the objects position to the first object the ray has hit and perform a collision detection as normal.

3) Simply add a hard constant for how fast objects can travel. The maximum distance traveled per collision step should be equal to half the radius of the object. This will ensure object does not miss any collisions. This is the most primitive, simplest and easiest to implement method, and it works very good for platform games that don't require rapid movement.

There are plenty of other ways to do this, just mess around with a couple of schemes and use whichever you like. Collision Detection is a fairly difficult topic and its a nightmare trying to code anything that's even remotely robust, but I hope I gave you some implementation directions  Grin

Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #5 - Posted 2012-11-26 00:40:14 »

Easiest way is to step your world in small enough increments that you don't miss a collision. Remember that you can step many more times than the number of frames you show.

Offline Troncoso

JGO Coder


Medals: 20



« Reply #6 - Posted 2012-11-26 00:42:53 »

Easiest way is to step your world in small enough increments that you don't miss a collision. Remember that you can step many more times than the number of frames you show.

Not exactly on topic, but this is actually something that's been puzzling me. In a rudimentary setup, the more frames the machine can handle, the faster the game, runs. How can I do what you just said? Restrict the frames to something like 60, yet, be able to update as many times per second as the machine can handle?
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2012-11-26 00:53:44 »

You only need to do as many frames as are actually required to have correct logic. Running flat out is a waste of cpu cycles.

As always, you have a broad phase, where you can calculate, say, a bounding sphere of an entity, and position it at the current location. Then create a bounding sphere at the location the entity will be at the end of the tick. Connect the two and you now have a capped cylinder. Do this for all entities that travel at a velocity that would otherwise cause tunneling or other defects. Then do simple capped-cylinder vs. capped cylinder intersection tests, and if (and only if) this causes any collision, you start to simulate the physics at more fine-grained intervals. Where the interval is the inverse of the maximum velocity.

If you don't need to simulate two bullets colliding in mid-air, ignore everything I just said.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Troncoso

JGO Coder


Medals: 20



« Reply #8 - Posted 2012-11-26 03:04:43 »

You only need to do as many frames as are actually required to have correct logic. Running flat out is a waste of cpu cycles.

As always, you have a broad phase, where you can calculate, say, a bounding sphere of an entity, and position it at the current location. Then create a bounding sphere at the location the entity will be at the end of the tick. Connect the two and you now have a capped cylinder. Do this for all entities that travel at a velocity that would otherwise cause tunneling or other defects. Then do simple capped-cylinder vs. capped cylinder intersection tests, and if (and only if) this causes any collision, you start to simulate the physics at more fine-grained intervals. Where the interval is the inverse of the maximum velocity.

If you don't need to simulate two bullets colliding in mid-air, ignore everything I just said.

Yeah. I get that. My last question wasn't really related to the collision issue.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2012-11-26 15:33:06 »

That's why I answered your question in my first sentence Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Varkas
« Reply #10 - Posted 2012-11-26 15:38:32 »

But but ... I liked to warp through planets in Frontier, if a collision was unavoidable!
(high speed + full time zoom = chance to step right through a planet)

If you want to dive into math, set up a vector (new point - last point) and calculate the distance of all possible obstacles to this vector. If the distance is lower than a threshold (object radius + obstacle radius) you can try a more detaild caclulation. This isn't cheap but precise.

Edit: It's basically the same as Riven's suggestion, because the line+radius check is equal to the cylinder intersection. Sorry, didn't read all of the thread before posting Sad

if (error) throw new Brick(); // Blog (german): http://gedankenweber.wordpress.com
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2012-11-26 15:42:17 »

What you said is exactly the same as capped cylinders (line + radius).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Troncoso

JGO Coder


Medals: 20



« Reply #12 - Posted 2012-11-26 20:40:55 »

Already, so hopefully, loosely based on what was said (the language confused me a bit. Maybe I need some more math classes), I came up with this crude algorithm to either move an object the proper distance, or move them to the point of collision with another object:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
/** 
 * Pass in the distance to move, and the object to check
 * for a collision
 */

moveToCollisionX(int distance, Object o)
{  
   // We start at this object's x position
   int start = x;
   
   // For the distance parameter we'd pass in something
   // like (speed * delta), or whatever value is normally
   // used  to adjust the x position. We add that to start
   // to get the final x position that this object SHOULD
   // end up at.
   int end = x + distance;
   
   // Get bounding shape of o somehow
   
   // movePoint is the final x coord that this object
   // will move to.
   int movePoint = distance;
   
   // Here, we check every x value between start and end
   // to see if o is being collided with
   for (int i = 0; (start + i) < end; i++) {
      //Increment the x-coord to check
      int point = start + i;
     
      if (/*point intersects o bound*/) {
         // If the point ends up on touching o's bound
         // Point becomes the new x-coord to move to
         movePoint = point;
         break;
      }
   }
   // Move this object to the determined x-value
   x = movePoint;
}


This is still rather crude. I've not determined a way to get the bounds of o yet, or how to efficiently check if the point in the for loop crosses that bound.

One question I have (if this algorithm isn't completely off track), would it be more efficient to create a line object between start and end? Then I could just check if that line intersects o. I don't know if I'd still have to loop through the coordinates that make up the line or not. This is only a first draft, after all.

Keep in mind, I am only working towards collisions in a 2 dimensional space.
Offline sproingie

JGO Kernel


Medals: 202



« Reply #13 - Posted 2012-11-26 21:12:44 »

You won't need a cylinder if you're doing things in 2d obviously, but you will need rectangles.  A line will only tell you if the centers potentially intersect (or whatever you drew the line through)
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2012-11-26 21:26:21 »

I don't see why you'd switch to rectangles in 2D.

In 3D, you calculate the bounding shape as line & radius.
In 2D, you calculate the bounding shape as line & radius.


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Troncoso

JGO Coder


Medals: 20



« Reply #15 - Posted 2012-11-26 21:52:49 »

I don't see why you'd switch to rectangles in 2D.

In 3D, you calculate the bounding shape as line & radius.
In 2D, you calculate the bounding shape as line & radius.



So....does that mean my algorithm is on the right track? Is there something I'm not accounting for?
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #16 - Posted 2012-11-26 21:55:23 »

On the right track, yes, but you have to interpolate both X and Y.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Troncoso

JGO Coder


Medals: 20



« Reply #17 - Posted 2012-11-26 21:58:16 »

Can you explain that a bit more? I'll have 2 methods:  moveToCollisionX and moveToCollisionY.

These will be used directly in place of statements like:

x += speed * timeSinceLastUpdate;
y += speed * timeSinceLastUpdate;
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #18 - Posted 2012-11-26 22:00:19 »

If you interpolate over X and then over Y, you're not traversing a line, but two axis aligned lines.

1  
2  
3  
4  
5  
6  
7  
   A
   |
   |
   |      . P
   |
   |
   |_____________  B


So you'd still miss point P in your collision detection.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Troncoso

JGO Coder


Medals: 20



« Reply #19 - Posted 2012-11-26 22:31:59 »

Hmm. Well, since that makes my method very inefficient, couldn't I just go to the line theory, get the intended (x,y) coordinate, draw a line from the start point, and find where the line intersects?

If this is an approachable option, what does Java provide from drawing a line and then checking for intersection? I know that the Rectangle class has some sort of method that does that, but as far as I know, there isn't a line class with the same capabilities.

EDIT: Nevermind. I just looked at the API and the line class in Java2D does, in fact, have intersect methods. Though, they only return a true or false if there is an intersection. How can I get the actual point of intersection?
Offline Troncoso

JGO Coder


Medals: 20



« Reply #20 - Posted 2012-11-27 01:48:58 »

Double posting is bad, but I'm doing it anyway. I've come up with a new algorithm to take both X and Y movement into account at the same time:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
/**
    * Moves this object to the point of collision with obj, if
    * there is one. As well, if there is a collision, return true
    */

   public boolean moveToCollision(int xDist, int yDist, EObject obj)
   {  
         // We start at this object's x position
         Point start = new Point (xDist, yDist);
         
         // The point where this object should end up if
         // there is no collision
         Point end = new Point (x + start.x, y + start.y);
         
         // Get bounding shape of obj
         Rectangle objBound = obj.getBounds();
         
         // Create a line of possible intersection
         Line2D.Double line = new Line2D.Double (start, end);
         
         // Test for collision
         if (line.intersects (objBound)) {
            // TODO If there is a collision, move this
            //object to the point of the collision
            return true;
         }
         
         // Move this object to the normal coordinates
         moveTo (end.x, end.y);
         return false;
      }


My issue is, if they do intersect, how do I get the object to move to the proper location? Like, how do I accurately move it to the point of the collision? Do I just check the direction of movement and move the object to the opposite bounding edge of the other object? What if it collides at a diagonal? Should I stop movement altogether? Or should I continue movement towards the axis that didn't receive the collision?
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.

toopeicgaming1999 (57 views)
2014-11-26 15:22:04

toopeicgaming1999 (50 views)
2014-11-26 15:20:36

toopeicgaming1999 (10 views)
2014-11-26 15:20:08

SHC (24 views)
2014-11-25 12:00:59

SHC (24 views)
2014-11-25 11:53:45

Norakomi (27 views)
2014-11-25 11:26:43

Gibbo3771 (24 views)
2014-11-24 19:59:16

trollwarrior1 (37 views)
2014-11-22 12:13:56

xFryIx (75 views)
2014-11-13 12:34:49

digdugdiggy (52 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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!