Collision in Pygrr - P1: Generation
- generating colliders
- detecting the collision
- collision resolution
Let's start off with some context. There are 3 main types of collider - but, what is a collider? A collider is the bounds in which a shape will be able to collide with other shapes. Basically, it's the part of the model that is used to detect interaction with other objects!
Anyways, the 3 main types (in 2D space) are a circle collider, bounding box, and a convex hull.
A circle collider is what it says on the tin, a circle - this is faster than the other forms of collider, due to everything being the same distance from the centre - all you need to calculate is if a shape is closer than the radius, thus, it will be inside the collider!
A bounding box is just a square / rectangle that forms around the shape - this is a very fast method, as the height and width axis of the rectangle follows the x and y axis of the space! Here's an image of a bounding box around a polygon.
As you can see, the red bounding box just approximates the polygon's coordinates, and simplifies it. The white space inside the bounding box would return a collision, whereas there wouldn't be one. This makes the collision inaccurate.
Now, the final, and the best one - a convex hull. This one might take some thinking, so bear with me! Here's an image of a concave polygon, and a convex version of the same polygon:
A concave polygon is a polygon that has at least one concave angle (that is, an interior angle greater than 180°). A convex polygon is a polygon that has no concave angles - but you probably already realised that!
So, which one do we want? Well, if you want to use the Separating Axis Theorem (Hyperplane separation theorem - Wikipedia) for collision detection - hang on, let's move back a step. The what what now?
The separating axis theorem (SAT) states that:
If there is a straight line (an axis) that can separate or fit between the two shapes without intersecting any of them, there is not a collision. If there is no axis that can do that, then they are colliding.
Now, here's the catch. If the shapes are both convex, this works perfectly, as shown:
But as soon as we start using concave shapes, stuff like this happens:
As there is no axis that can intersect them, the output would be that there IS a collision, when, as you can see, there is not.
Now, what's a convex hull? It's just the convex shape that can group together any amount of points. Basically, it's an object that generates the smallest convex shape that contains all the points!
Here's a set of random points, and the convex hull generated from that:
So, now we know what convex hulls and all that are, let's get into the coding!
For this, in Pygrr PolyArt, the program used to draw models for your objects, we need to implement a script that can generate a convex hull for each of the points on the player's model. We're going to use Jarvis March (also known as the gift wrapping algorithm).
I won't go into the details of it, but you can read into it if you'd like! So, now we've implemented that, lets add a feature where you can toggle visibility of the collider in PolyArt, just to show off...
Awesome! Now, let's talk about efficiency.
Obviously, SAT takes some time, as does everything - so we don't want to run the algorithm unnecessarily. There's a small way I thought of how to only run it when there could be a collision, and this is using the smallest enclosing circle. This is described, as, well, the smallest possible circle that encloses all of the points in a shape.
As we realised earlier, circle colliders are the fastest one, so we can approximate the shape by using a circle collider, and if that calculates a positive collision, then we can run SAT.
This states that unless an object is inside this circle, it cannot be touching (or colliding) with the shape! This is pretty cool, as all I need to do is check if the object is closer to the centre of the circle than the radius, which is literally a single line of code - very fast!
The code for this is a bit finicky, so I'm going to borrow the code from here: Smallest enclosing circle (nayuki.io). I'm going to make sure to include the copyright notice, too!
Let's see that in PolyArt now:
Beautiful! Now we just have to add the convex hull's points, the radius of the circle, and the centre of the circle to the save file!
In case you wanted to see I know there's one particular reader who also loves JSON as much as me, here's the save file for the swan model, which I think I might actually make as a default model. pygrr.Model.swan, anyone?
{
"type": "POLYGON",
"smooth": true,
"fill": "tan",
"outline": "black",
"width": "5",
"points": [
[
-3.0,
4.0
],
[
-4.0,
3.0
],
[
-6.0,
3.0
],
[
-1.0,
2.0
],
[
-1.0,
-3.0
],
[
3.95,
-4.4
],
[
8.0,
-3.0
],
[
8.0,
-1.0
],
[
12.0,
1.0
],
[
8.0,
-0.0
],
[
11.0,
2.0
],
[
8.0,
1.0
],
[
10.0,
3.0
],
[
8.0,
2.0
],
[
9.0,
4.0
],
[
7.0,
2.0
],
[
3.0,
-0.0
],
[
1.0,
-0.0
],
[
-1.0,
3.0
]
],
"collider": {
"type": "SIMPLE",
"center": [
420.0,
260.0
],
"radius": 181.10770276274835,
"hull": [
[
-6.0,
3.0
],
[
-3.0,
4.0
],
[
9.0,
4.0
],
[
12.0,
1.0
],
[
8.0,
-3.0
],
[
3.95,
-4.4
],
[
-1.0,
-3.0
]
]
}
}
Here's the model, too:
Isaac, over and out...