Crafty Blog - JavaScript Game Engine Development

Development of Crafty

3 notes &

SAT Collision made easy: Part 1

This is going to be a multipart tutorial due to the length and ground to cover.

SAT (or Separating Axis Theorem) is a method of collision that can detect collision between any two convex polygons. It is currently used in the latest development version of Crafty. For this tutorial I will be pasting links that helped me learn the methods.

Convex vs Concave

First you need some basic 2D linear algebra knowledge. We need to know what a vector is, how to calculate normals for a line (a perpendicular line), normalize it (so that the vector length equals 1) and project vectors onto another vector using dot product.

Already it sounds complicated but luckily the methods are quite simple. Here are some good tutorials on basic linear algebra (Part 1, Part 2).

A vector is a direction and a magnitude. It can also represent an x, y position, a velocity or direction.

Normals

A normal is just a perpendicular vector and very easy to calculate. There is a left normal and right normal which just go in different directions. Given a vector (x, y), swap the x with the y and make the new y negative (y, -x) for a left normal or make the new x negative for a right normal (-y, x).

Left and right normals for a vector

As you can see in the diagram, the red vector is the left normal

(x, y) = (y, -x)
(2, -2) = (-2, -2)

The green line is the right normal

(x, y) = (-y, x)
(2, -2) = (--2, 2) = (2, 2)

Normalization

A normalized vector (or unit vector) is a vector in the same direction but with a length of 1. This makes life easier with certain calculations such as dot products.

To calculate a normalized vector we must divide it’s x and y by the length. How do we find the length? With good ol’ Pythagoras:

 c^2 = a^2 + b^2

Or in our case:

length = Math.sqrt( x * x + y * y )

To find the length between two vectors, you must first find the rise/run and use that as opposed to the x and y.

The mathematical notation of length is denoted by wrapping vertical bars

 | V |

This means the length of a vector, V.

Projection

Projection is a way to calculate the magnitude of one vector in the direction of another vector. To do this we need to calculate the dot product. The dot product is a method of calculating a scalar value (single number) between two vectors and is a way of finding how “similar” two vectors are (i.e. for normalized vectors it represents how much they point in the same direction, as a cosine of the angle in between them).

A • B
A.x * B.x + A.y * B.y

Metanet has a great tutorial on this.

Calculating the dot product between a normalized vector and a vector to project onto it, we get the length along the vector and can use this information when implementing SAT collision.

Projection

From the diagram the red line is vector B, the green is vector A and the blue line is the result of the projection using dot product.

That’s it for now and in the next part we will use what was learnt to implement SAT collision.

Thanks to bovicide for pointing out some errors.

  1. craftyjs posted this