Collision and Movement

Newbie & Debugging Questions
#1

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!

#2

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


if (objectY > targetY) {
//stop object from moving here
}
#3

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.

#4

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

#5

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 ;D

#6

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.

#7

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?

#8

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.

#9

Yeah. I get that. My last question wasn’t really related to the collision issue.

#10

That’s why I answered your question in my first sentence :slight_smile:

#11

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 :frowning:

#12

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

#13

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:

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

#14

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)

#15

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.

#16

So…does that mean my algorithm is on the right track? Is there something I’m not accounting for?

#17

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

#18

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;

#19

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


   A
   |
   |
   |      . P
   |
   |
   |_____________  B

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

#20

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?