Movement

Rinostar

Basic Kinematics

First, it makes sense to know how objects move. Every physics object has a position and a rotation, obviously. Right now we’ll only look at position, because rotational kinematics is just a more complex version of regular kinematics. For every position, there’s also velocity, that describes how much an object moves. This is a vector quantity. Written in math terms, where p(t) is the final position at time t, and v(t) is velocity at time t, it would look like this: p(t) = 0tv(t)dt. Basically, this just says that the position changes based on velocity over time. Now, then there’s acceleration which describes how much the velocity changes. It’s also where the forces and different interactions get applied at. Same deal, a(t) is the acceleration function, it’s just: v(t) = 0ta(t)dt . Next up, force. Each object exerts some amount of force to other objects. The equation is simply F=ma. Force is also a vector. Since acceleration is a function, we make a = a(t), where t is the variable for time.

This code sample is just in 2d for simplicity purposes. In 3d, it’s the exact same, just with an added z component. The y on the acceleration is set to be -9.81, which exerts a constant force downwards, which you guessed it, is gravity.

Collision Detection Algorithms

There are multiple types of collision detection algorithms, which can be categorized into two types: broad phase, and narrow phase. For the most part, the algorithms you might hear the most are AABB, and SAT. AABB is a broad phase detection algorithm. SAT is the opposite; a narrow phase detection algorithm. Broad phase type algorithms are generally pretty simple and run pretty fast, but have low accuracy. Narrow phase type algorithms are, of course, the opposite. They generally are more advanced, being more accurate, but they’re a bit slower.

AABB Collision Detection Algorithm

AABB stands for Axis Aligned Bounding Box, which should give away some of how this thing works. All it does is to check if two axis aligned boxes are colliding, or inside of each other. The disadvantage of this algorithm is that it can’t check any rotated boxes (non-axis aligned), so if you were to put a box collider on two objects, they can’t be rotated to the orientation of each object.

So with that out of the way, here’s how it works. If you squash two boxes onto a 1d line, like the x axis, they look like two lines, with a start and end point for each one. If we only think about this 1d line, we can see that if the two lines are intersecting, then the boxes are possibly intersecting.

(Illustrations done by Rinostar)

The equation for this is: Av1xBv2xAv2xBv1x . Now, for the y axis. To test if they’re intersecting or not, we need to also check for the y axis.

The equation for the y axis is this: Av1yBv4yAv4yBv1y. Similar to the x axis, but instead we will be using the fourth point for the y difference (height)¹.
Putting all this together, it would look like this: (Av1xBv4xAv4xBv1x)(Av1yBv4yAv4yBv1y).
If your boxes had width and height, instead of points, it’s pretty easy to calculate the points.

For example, take this box, which has 4 points:

Let’s make v1 be the origin of the box. If we want to calculate v2 , the equation (w being width), would be: v1x+w, v1y. If we want to calculate v3 , (h benign height), it would look like v1x, v1y+h. For v4 it would be, v1x+w, v1y+h. Putting all this together in scratch as a custom block, it would look like this (v1 being the origin, v2 being (v1+w,h)):

For 3d, you’d use the z component, instead of the x or y, but it’s still the same check, with another if statement inside the two. So for any two bounding boxes, we’re now able to check if they’re colliding or not. But what about orientation, or other polygons, besides boxes?

SAT Collision Detection Algorithm

Here, we get to the good stuff: more precise and complex algorithms to tear your hair out trying to implement. Take two rotated boxes, just for simplicity. The summary of this algorithm is: if they’re not colliding, you can just draw a straight line through the two polygons, and none of the edges intersect. That’s why SAT is called “Separating Axis Theorem”.

So how do we find the separating axis? Well first, to actually implement this thing, we will have to check both polygons, switching which polygons are a and b in the second iteration. Inside that, we must check all the edges of polygon A, making a potential separating axis from each edge. How do we make a potential separating axis? Well, the separating axis can be calculated using just the normals of the current edge.
If v1is the start of the line, and v2 is the end of the line, This can be calculated like this: n=-(v2y-v1y), v2x-v1x .

As you can see, the normal is perpendicular to the current edge in the loop, which would be V1V2, or line AB. Next, we must project all the points of both polygons onto this line. If you don’t know already: it’s dot product time!

Taking the dot product of all the points, we must find the min and max points of both polygons to do a comparison similar to AABB on one axis. To do that, we must loop through all the points projected to the line and check if that point is less than the min point value, or greater than the max point value. In this example, Av1 = Amin, Av3=Amax, Bv4= Bmin, and Bv2=Bmax ². Now, we can check if both polygons could be intersecting, using a bool equation: Amin Bmax Amax Bmin. If it returns false, then we stop the loops and conclude that they aren’t intersecting. If it returns true, we will continue iterating through the loops, and if we reach the edge and the bool equation still returns true, then we can conclude that the shapes are overlapping. You may ask, “Could we possibly get collision data, such as the normal, or min depth of collision from this?” The answer is yes! It is easier in SAT than AABB, as most of the variables needed for this are already here. For the normal, you just have to normalize the axis of projection. Then, for the depth of the penetration, just get the difference between the min of the projected polygon A point, and max of polygon B’s projected point. Now, it’s time for the more fun stuff: solving these collision cases.