Calculate if Two Particles Come Close

Question

I'm doing some simple collision detection for a 2D game in PSM Studio.

My current method involves iterating through every game object and finding the distance between another game object, then seeing if the two are within a certain distance (usually 1/2 the width of each object combined). If they are, they are considered to have collided.

While this method works in many cases, it has a major fallback. If an object moves at a speed such that the movement per frame is greater than a potential colliding object's width (i.e. a fast moving projectile towards an enemy), the object will have essentially teleported over the other, and even if they would have collided, they don't.

I'm thinking of creating a method that tests two particles on two line segments. The line segments would consist of the start end end position of each object during the updates.

Knowing the polar movement (angle and magnitude) of each object as well as their respective line segments, can I calculate if the two particles come within that magical distance that means they have collided?

Answer 1

I also encountered this problem, and my solution was to detect collision during the movement of the objects.

If the distance moved during a cicle was greater than the size of the object, I would decompose the movement in several smaller movements, and solve collisions for each one of these decompositions.

An example:

The box is moving faster than it's own size, so detection with the red like wouldn't be detected. So the movement is decompose in smalled movements, and in each step you check for collision with the red line.

In the third step, the collision is detected.

I don't know if this solution would fit your cicle structure, but at least it could bring you some new idea.

EDIT:

Note that to ensure that a collision is detected, you must make sure you leave no gaps in the movement. In order to make this process as fast as possible, and ensure the whole area is checked, you must decompose the movement in fractions of the object's size.

For example: In the drawing above, lets imagine position of the object before the movement is 0 units, and at the end 100 units.

If the object has a size of 30 units,you will have to check in the following positions:

0, 30, 60, 90, 100

In each itearion you increment the position by the size of the object, until you reach your destination.

Keep in mind that if you are running lets say... 40 cicles per second, in the example just given the object will be moving at:

40 cicles x 100 units = 4000 units per second 

If each unit is a pixel, and you are running a 800x600 resolution, the object will be moving at more than four screens per second, which is a huge speed.

With this I just want to point out is that "High speed" is pretty relative, and unless you are working with really small objects, this process won't be happening as frequently as initially expected.