Collision Part III: Discrete Collision

64 days ago by MrMisinput

Share this post:

September 11th, 2024

Hello! Today I'll be covering discrete collision for the game. Discrete collision is the frame-to-frame collision resolution that keeps objects from overlapping. An example would be stopping an object from going through a wall, which is what I'll be demonstrating today. To do this, we will calculate the shortest vector possible to push an object out of the wall using the Minkowski Difference between the two objects.

Minkowski Difference

The Minkowski Difference is the difference between two object's positions. This means the closer the objects get to each other, the closer the difference will be to zero. Using this difference as the position, we can create a box around it by adding the widths and heights of each box together. With the resulting box, we can know if two objects are colliding if the box contains the origin. In the video below, if the box contains the origin, it turns red:

With the Minkowski box, we can find the shortest vector to add to the other object that will stop them from overlapping. Since we're using AABBs, due to the Pythagorean Theorem, we know that the shortest vector will never be the diagonal line. This means that the shortest vector will either only be on the x-axis or the y-axis.

Obstacle Class

I'll introduce a new class to represent an impassable object, the Obstacle class. It is just a GameObject that has a CollisionComponent by default:

We'll have to calculate the shortest vector every frame that another object is colliding with the Obstacle, so we'll override the OnCollisionOngoing function.

In the actual function, the first step is to create the Minkowski Box:

As stated before, the position of the box is the difference between the two object's positions, while the dimensions of both objects are added together. The Minkowski box will use the center as the coordinate. Since in my game, the top left is the coordinate, we have to offset the x-axis by half the width, and the y-axis by half the height.

We'll find the minimum and maximum values that the x and y could be:

Using this information, we can create the shortest vector. By default, we'll assume the minimum distance will be in the negative x direction, pushing the non-static object to the left. We'll then check the other sides to see if they're shorter:

After we have the minimum distance, we can add the shortest vector to the other object's position:

And that's all there is to it!

Demonstration

Here's a video of it working:

Conclusion

Implementing discrete collision was surprisingly simple. I had a hard time visualizing what was actually happening, but this video below by Dylan Falconer gave me the "A-ha" moment I needed. In the next post, I'll be covering Continuous Collision, so stay tuned!