2D Polygon Collision with Python (and Kivy, optionally)

Those of you who write video games for computers or mobile device probably know that simplifying is the rule most of the times. To avoid embarrassing conditions where object go right through each other, we need some kind of collision checking algorithm. This is very easy when the colliding objects are all rectangular and their edges are parallel to the edges of the screen, but in real life objects are often concave and have not-so-regular shapes. One solution to check collisions in video games is checking whether one object collides into a point of the other object where the image is transparent, but that gets very CPU expensive and the framerate would drop drastically. The other option, which I’m going to explain, is to draw a simplified polygon around the edges of the thing we want to check for collisions and use it in place of the thing itself, as computers are better with maths than anything else.

Getting the points of the polygon

This is the part I hate the most. You need to write down all the coördinates of the vertices of our polygon and put them into a list of tuples. I use GIMP for that, as it shows the coördinates of the point hovered by the mouse pointer.

Important! If you’re using Kivy you need to flip the image upside down, or the coördinates will be wrong! Kivy starts counting Xs and Ys from the bottom left corner, as opposed to GIMP (and GTK in general) which starts counting from the top left corner. Select the flip tool in GIMP, select Vertical in the tool options at the bottom and start writing down the coördinates.

Screenshot
Note: you do not need to draw the polygon, you just need to write down the coördinates.

This is what I’ve got for that image:

[(0, 85), (70, 170), (118, 172), (160, 135), (204, 204), (255, 204), (296, 135), (306, 153), (340, 153), (391, 82), (391, 50), (306, 0), (272, 0), (252, 33), (220, 33), (200, 0), (170, 0), (125, 50), (66, 15), (0, 50)]

Make sure all the points are in order. It doesn’t matter where you start. The first and the last are also counted as a segment like every other two points.

The algorithm

The algorithm is explained very well in this site (currently not accessible, using the WayBack Machine).

This method relies on the fact that if you draw a line starting from the point and going to the right, it’s always going to intersect an even number of times (0 is considered even) if it lies outside of it, and an odd number if it’s inside.
Looking at this picture will make it easier to understand.

insidepoly

So what we’re going to do is checking whether the point lies between the highest and the lowest vertex of the polygon, then iterate over the edges to count the number of intersections. However, we’re trying to check whether two polygons collide, not a point and a polygon. So we need to iterate over every vertex of the first polygon and see if it lies and the second one, and vice versa.

Writing the Python code

I’ll paste the code first, and then explain it:

First, we check whether the point is one of the vertices. Then, to avoid useless iterations that might slow down the game, we also check if the point lies inside or outside of the polygon’s bounding box. If it’s inside, we go on.

Now that we have a high chance of collision we go on and iterate over all the edges and start counting the intersections. We check whether the point lies between the two points’ Ys, and if it does, we intersect y=p[0] with the line that passes through the edge of the polygon we’re considering. To do that, you start with the basic equation of a line through two points, then you move x to the first member and everything else to the second.

\frac{y-y_2}{y_1-y_2} = \frac{x-x_2}{x_1-x_2}

x = x_2-x_1 \cdot \frac{y-y_1}{y_2-y_1}-x_1

If the value you get from this is less than or equal to the X of our point, we have an intersection, because it means the point is on the left of the segment.

The last line just checks if the number of collision is even or odd, and returns a bool accordingly.

Colliding two polygons

If we want to collide a polygon, we can use the previous function together with this one:

Even if it seems a little weird because of all the list sorting and reversing, what it does is actually very simple: first it checks if the two polygons are the same, then it checks whether the two polygons have common vertices, and if they don’t, it iterates over the vertices of each polygon and collides it with the other polygon.

Using it with Kivy

I’ve made some simple classes to use this collision system with Kivy. The code was a little longer, so I posted it into a gist: https://gist.github.com/Davideddu/920183c34f8914e88faf

To use it, make your widget inherit from both Polygon or MultiShapePolygon and your widget class. If you’re using Polygon, make sure you override abs_vertices with the list of vertices you got earlier. If your widget can have different shapes (e.g. different positions of the character), make sure you override _shapes with a list of dicts. Each dict must have a “vertices” key with the list of tuples you got earlier. You can set any other key if you want (e.g. you may want to add an “image” key pointing to the image file corresponding to that shape), but the “vertices” key needs to be there. When you set the shape property, the vertices will be updated according to the index of the shape you set. You can use random_shape to let the app pick a random shape for you.

Another thing you will probably want to set is the scale property, which is needed if you’re scaling the widget associated to the polygon. For example, if you’re scaling the image to half of the original size, this property should be set to 1/2. If you’re not using the polygon as a widget you will also need to set x and y. Usually these properties are set by Kivy, but if your class does not inherit from both a widget and Polygon you’ll need to update these manually.

Example:

I hope you found this useful! Let me know in the comments what you think 😉 and share!

There is a mobile optimized version of this page, view mobile Version.

Leave a Reply