Basic collision

Methods to check if two shapes overlap, for different combinations of shapes. This kind of checks is normally used to check if two objects collide with each other.

• On fixed point
• 2D collision
  • Point vs. box
  • Box vs. box
  • Point vs. circle
  • Circle vs. circle
• 3D collision
  • 3D point vs. box
  • 3D box vs. box
  • Point vs. sphere
  • Sphere vs. sphere
  • Point vs. cylinder
  • Cylinder vs. cylinder
• More complex shapes

On fixed point

The article about speed physics tells you to use fixed point values to improve accuracy. However, you'd be dealing with 32-bit values which for some of these checks could become a pain to cope with.

Collision can afford to be more coarse. If you just take the integer part, you may get away with 16-bit numbers, which will make this a lot simpler (when working in assembly) and faster (in general). If you're using 1px = 65536 as suggested in the article, then it means the first word of the number will be the integer half which you can read as-is (avoiding even the bit shifting).

Point vs. box

The simplest type of collision is to check if a point is inside a box (e.g. rectangle or square). This is useful when trying to point at something, or for checks against small things (like a bullet).

To achieve this we need to do a range check (i.e. check if a value is within a given range) to both X and Y axes, with the range being the box boundaries. A range check is pretty simple, just compare the value against the minimum and maximum boundaries of the range, if it's between them then the value is inside:

(x ≥ min) and (x ≤ max)

Do this to both axes and you have a way to check if a point is inside a box (if both range checks success then the point is inside the box):

if (point_x >= box_x1) and
   (point_x <= box_x2) and
   (point_y >= box_y1) and
   (point_y <= box_y2)
then
   ...
end

Box vs. box

A more common type of check however is box against a box. Most (or all) objects in a game will have a "collision box", which is referring to this. It's not really harder than point against a box but may be a bit trickier to understand.

In this case what we need is to check if two ranges overlap instead. It looks like below, the idea is to ensure that the minimum of one range doesn't go past the maximum of the other range (and vice versa):

(1st range min ≤ 2nd range max) and (1st range max ≥ 2nd range min)

Now take it to both axes and you get a box vs. box collision check:

if (box1_x1 <= box2_x2) and
   (box1_x2 >= box2_x1) and
   (box1_y1 <= box2_y2) and
   (box1_y2 >= box2_y1)
then
   ...
end

Point vs. circle

Sometimes you have an object that's more circlar than rectangular (and large enough for the difference to stick out). In this case, if may be more appropriate to check against a circular shape.

To check if a point is within a circle, you need to know the distance between the point and the circle's center. If the distance is within the radius of the circle, then the point is inside.

To get the distance we need to use Pythagoras' theorem:

distance² = X difference² + Y difference²

If you wanted the actual distance you'd need a square root, but since we just need to compare against it, we can avoid the square root and compare the squared values directly. Then only the multiplications are left, but as long as the values are 16-bit it's not a big deal for the 68000 (note: the 68000 will produce a 32-bit result, so don't worry about numbers becoming too big either).

Putting all together, it looks something like this:

delta_x = circle_x - point_x
delta_y = circle_y - point_y
limit = circle_radius

if (delta_x * delta_x) +
   (delta_y * delta_y) <= (limit * limit)
then
   ...
end

Circle vs. circle

Again, rather than point against a circle it may be more useful to check between two circles (e.g. two balls colliding). The idea here is similar, so refer to that to understand what's going on.

To check if two circles overlap you need to compare the distance between their centers. If you add up the radius of both and the distance is under that, it means the two circles are overlapping (i.e. collision).

delta_x = circle2_x - circle1_x
delta_y = circle2_y - circle1_y
limit = circle2_radius + circle1_radius

if (delta_x * delta_x) +
   (delta_y * delta_y) <= (limit * limit)
then
   ...
end

3D point vs. box

Working in 3D? (maybe an isometric game?) Then you're going to need to extend collision checks to work in three dimensions too.

This one is an extension to the 2D point against box check. The only difference is that we throw in the Z axis as an additional check, otherwise it works the same way.

if (point_x >= box_x1) and
   (point_x <= box_x2) and
   (point_y >= box_y1) and
   (point_y <= box_y2) and
   (point_z >= box_z1) and
   (point_z <= box_z2)
then
   ...
end

3D box vs. box

Extending the box against box check to 3D works the same way as for the previous case: add one more range overlap check for the Z axis, otherwise works the same way.

if (box1_x1 <= box2_x2) and
   (box1_x2 >= box2_x1) and
   (box1_y1 <= box2_y2) and
   (box1_y2 >= box2_y1) and
   (box1_z1 <= box2_z2) and
   (box1_z2 >= box2_z1)
then
   ...
end

Point vs. sphere

The 3D equivalent to point against circles is point against spheres. If you understood that one, then this one is easy: throw in the Z axis into the additions as well and now you have a point against spheres check.

delta_x = sphere_x - point_x
delta_y = sphere_y - point_y
delta_z = sphere_z - point_z
limit = sphere_radius

if (delta_x * delta_x) +
   (delta_y * delta_y) +
   (delta_z * delta_z) <= (limit * limit)
then
   ...
end

Sphere vs. sphere

The 3D equivalent to circles against circles is spheres against spheres. As with point against sphere, it pretty much involves including the Z axis in the addition.

delta_x = sphere2_x - sphere1_x
delta_y = sphere2_y - sphere1_y
delta_z = sphere2_z - sphere1_z
limit = sphere2_radius + sphere1_radius

if (delta_x * delta_x) +
   (delta_y * delta_y) +
   (delta_z * delta_z) <= (limit * limit)
then
   ...
end

Point vs. cylinder

Another useful shape in 3D is cylinders. A check between cylinders is like a mix of a circle check for two of the axes and box check for the remaining axis.

This is an example that should give an idea. The cylinder shape checked for is upright, so the "box" check goes to the Z axis, but it can be applied to either of the three axes.

delta_x = cylinder_x - cylinder_x
delta_y = cylinder_y - cylinder_y
limit = cylinder_radius

if (point_z >= cylinder_z1) and
   (point_z <= cylinder_z2) and
   ((delta_x * delta_x) + (delta_y * delta_y) <= (limit * limit))
then
   ...
end

Cylinder vs. cylinder

This is the cylinder equivalent of box against box or circle against circle. Like point against cylinder, the idea is to do a circle check for two of the axes and a box check for the remaining axis.

delta_x = cylinder2_x - cylinder1_x
delta_y = cylinder2_y - cylinder1_y
limit = cylinder2_radius + cylinder1_radius

if (cylinder1_z1 >= cylinder1_z2) and
   (cylinder1_z2 <= cylinder1_z1) and
   ((delta_x * delta_x) + (delta_y * delta_y) <= (limit * limit))
then
   ...
end

More complex shapes

Some objects may have more complex shapes where these simpler ones would stick out pretty badly. In these cases, you could try doing multiple checks against them. For example, a large L-shaped object could be handled as two boxes.