Collision detection: Irregular polygons (Asteroids) using the crossing number algorithm

Testing for collision with an irregular polygon is the exact same problem as if you were doing collision detection for an Asteroids game clone. If you don’t know what Asteroids is you can learn about it here. As this helps us visualize the problem I will present this whole tutorial in those terms. This collision detection method is much more complex than the previous methods we have discussed. So be sure to read all the articles in the Recommended preparation tutorials section above. Also make sure you are comfortable with OOP in either C++ or Java.

It doesn’t have to be hard work, however. What we need to do is take a moment to consider a strategy that will work for us. This tutorial will focus on the code rather than an explanation of the math. Understanding the math relies on an understanding of Trigonometry, in particular sine and cosine functions. If this interests you you could start with Using trigonometric functions in 2d games.
The code samples are in Java because it was Java that I implemented it in a game. Also, because there appears to be very few Java examples on the Web but already a few C++ do exist although I haven’t seen any that talk through the stages of adding it to an actual game.

Apart from the class syntax and the member variable access specifiers during declaration (public, private, whatever) there would be virtually no changes between the Java or C++ code. There will obviously be a difference between some of the method/function names and the classes/libraries you will need to import/#include.

Planning for irregular polygon collision detection

What we want to know is when a point from another object(we will focus on the points of the triangle shaped ship) goes inside the asteroid. It is not enough to just detect an intersection because this is ambiguous with rotating irregular polygons.

Although we will not be detecting any asteroid on asteroid collisions in this tutorial, as you will see when our collision detection nears completion, achieving asteroid on asteroid collision detection would not present much of an extra challenge. It would, however, put an extra strain on the device’s CPU. In addition, once you get this system working, it will be trivial to implement bullet (single vertex) collision with an asteroid.

Colliding with an asteroid

We need to find out if any single vertex from the ship crosses into the space contained by the vertices of the asteroid. An additional problem is that the asteroid is not only a moving target but also a rotating one. We will not only have to rotate and translate all the vertices of the objects but the asteroids as well. We don’t want to do this every frame.

Being more specific, we need to calculate any vertex of the ship crossing the line made between each pair of vertices on the asteroid. The first problem, as already mentioned is, that detecting the intersection of a point is ambiguous with a rotating irregular polygon.

Fortunately at this point we can fall back on a clever and simple algorithm, devised and refined by mathematicians far greater than myself.

We will use the Crossing Number algorithm. Here is how it works.

The Crossing Number algorithm

We compute the line made by a pair of vertices and use conventional trigonometry to see if a particular vertex from the object being tested crossed that line. If it did we increment a variable from 0 to 1. Next, we test the same point against each and every line made by each vertex pair from an asteroid, incrementing our variable each time it does. If after testing the vertex against every line, using the crossing number algorithm our variable is odd, we have a hit. If it is even, no collision has occurred.

Of course, if no collision has occurred we must proceed to test each and every vertex from the object being tested against each and every line formed out of the vertex pairs on the asteroid. Here is a visual representation of the crossing number algorithm in action.

Notice in the previous image that all the cases where the vertex is inside the asteroid, the value is odd.

With complex calculations going on we will definitely want to do a simple first-phase test to see if it is likely there has been a collision, before doing the complex tests.

The steps and overview of asteroid collision detection

The radius overlap test is quite appropriate when testing a single vertex like a bullet, a spinning triangle like a ship or indeed a rotating asteroid. With this in mind, here is an overview of the whole process we will use for testing for collisions between asteroids:

1. Has the radius of the ship overlapped with the radius of an asteroid?
2. If yes has the first vertex of the object crossed the first line of the asteroid
3. if yes crossingNumber ++
4. Repeat step 2 with each line on the object
5. If crossingNumber is odd return true to calling code because a collision has occurred.
6. If crossingNumber is even no collision has occurred(yet) repeat steps 2, 3 and 4 with the next vertex of the object being tested.
7. If all vertices have been tested and we have reached here then no collision has occurred

Game programming patterns are beyond the scope of this tutorial so I want to present an object-oriented solution that is simple to grasp and easily adapted. We will set up a collision detection class called CD. It will have a detect() method that will test for collisions with asteroids and will be called for the ship against each and every asteroid each frame.

Doing the calculations outside of the objects themselves means we will need a whole bunch of data about the objects we will be testing, made accessible to our new CD class.

Coding a collision detection solution for irregular polygons in C++ or Java

The first class we will call CollisionPackage. So we know we need a certain set of data to do our detections properly. This class will hold all the data that our collision detection class will need. Every object that we need to detect collisions (asteroids and ship) will have an  CollisionPackage instance.

When the time comes to rotate all the points to their real world location, our collision package will need to know which way the object is facing. For this we have a float called facingAngle.

We will need a copy of the un-rotated model space vertices. We will not go to the trouble of updating these every frame and will do so only after the first phase of collision detection shows a collision is likely/possible. We will also hold a pre-computed value for the length of the array that holds these vertices. It can potentially save time in the collision detection process.

Therefore, we will also need the world coordinates of the object. This is a single point in the centre of the object. This we will update every frame. Each object will have a pre-computed radius variable which is the size of the object from its centre to its furthest vertex. This will be used in our detect() method to do the radius overlapping, phase one detection.

We will also have a couple of PointF objects, currentPoint and currentPoint2 which are just handy objects that will hold the vertices currently being tested.

The CollisionPackage class

Create a new class, call it CollisionPackage and implement the members we have just discussed.

/*
	All objects which can collide have a collision package.
	Asteroids, ship, bullets. The structure seems like slight
	overkill for bullets but it keeps the code generic,
	and the use of vertexListLength means there isn't any
	actual speed overhead. Also if we wanted line, triangle or
	even spinning bullets the code wouldn't need to change.
*/

public class CollisionPackage {

    /*
		All the members are public to avoid multiple calls
		to getters and setters.

		The facing angle allows us to calculate the
		current world coordinates of each vertex using
		the model-space coordinates in vertexList.
	*/
    public float facingAngle;

    // The model-space coordinates
    public PointF[] vertexList;

    /*
		The number of vertices in vertexList
		is kept in this next int because it is pre-calculated
		and we can use it in our loops instead of
		continually calling vertexList.length.
	*/
    public int vertexListLength;

    // Where is the centre of the object?
    public PointF worldLocation;

    /*
		This next float will be used to detect if the circle shaped
		hitboxes collide. It represents the furthest point
		from the centre of any given object.
		Each object will set this slightly differently.
		The ship will use height/2 an asteroid will use
		whatever the max length of a line can be.
		This tutorial doesn't cover randomly generating
		the asteroid vertices. For this tutorial, 25
		is assumed. As long as the real length isn't greater
		the value will work for you to.
	*/
    public float radius;

    // A couple of points to store results and avoid creating new
    // objects during intensive collision detection
    public PointF currentPoint = new PointF();
    public PointF currentPoint2 = new PointF();

Next, in the same class, we have a simple constructor that will receive all the necessary data from each object at the end of each object’s constructor. Implement the CollisionPackage constructor as shown. The code implies that your class (ship/asteroid/whatever) needs to be able to supply the necessary data for the arguments when you call it.

public CollisionPackage(
	PointF[] vertexList,
	PointF worldLocation,
	float radius,
	float facingAngle){
	vertexListLength = vertexList.length;

   this.vertexList = new PointF[vertexListLength];

	// Make a copy of the array
	for (int i = 0; i < vertexListLength; i++) {
		this.vertexList[i] = new PointF();
		this.vertexList[i].x = vertexList[i].x;
		this.vertexList[i].y = vertexList[i].y;
	}

   this.worldLocation = new PointF();
   this.worldLocation = worldLocation;
   this.radius = radius;
   this.facingAngle = facingAngle;

}// End constructor

}// End class

That’s all the data we need to do our advanced collision detection.

Adding collision packages to the game objects

Add a new member of the type CollisionPackage to each class that you want to detect collisions with asteroids, including the asteroids themselves. Also, add an array of PointF objects called points and the other variables your class will need to call the CollisionPackage constructor. A common mistake is to initialize the points array with world space coordinates. They must be model space coordinates and the world space coordinates will be calculated, when necessary, from the model space and worldLocation.

// Inside Ship, Asteroid, Whatever class
CollisionPackage cp;

// Next, a 2d representation using PointF of
// the vertices. Used to build shipVertices
// and to pass to the CollisionPackage constructor
PointF[] points;
PonitF worldLocation;
float radius;
float facingAngle;

/*
	Your code to initialize the points array,
	location and angle of your ship goes here.
	This will vary depending upon how your game is implemented
	Initialize the above variables to represent your ship/object
	...
	...
	...
*/

It is possible that a vertex from the asteroid might sneak inside the ship. Remember that we will only be testing for vertices from the ship entering the asteroid. This next image shows the problem.

We could completely solve this problem by testing all the asteroids vertices against all of the ship’s lines as well as what we are planning to do (testing all the ship’s vertices against all the asteroids lines). This would slow the game down.

For this reason, it might also be worth adding three extra model space coordinates to the ship. Your drawing code does not need to know about these. They are positioned in the middle of each of the three lines which make the ship. We do this to make it harder for a vertex of an asteroid to drift inside the ship without a vertex of the ship being inside the asteroid. Just adding a few extra points to the ship does produce near-perfect detection as shown next.

Now our object has been initialized we can initialize the collision package.

Creating a CollisionPackage for the ship

Here is how the code might look in the constructor of the class that represents a ship. Be sure to read the comments too.

// Initialize the collision package
// The code assumes you have
// initialized points, worldLocation, radius and facingAngle

cp = new CollisionPackage(
	points,
	worldLocation,
	radius,
	facingAngle);

Creating the CollisionPackage for the asteroid

As stated, we will also need a collision package in the class that represents an asteroid. Use the exact same steps above. Obviously, the way that you decide the model space coordinates and location in the world is specific to your implementation. As long as you have an initialized CollisionPackage, called cp, the rest of the tutorial will work. There is one BIG gotcha to be aware of!

Synchronise the collision package each frame

The code in the update section of your game objects (ship/asteroid/whatever) would look like this. Notice we do not do anything with the array of vertices.

// Update the collision package
cp.facingAngle = facingAngle;
cp.worldLocation = WorldLocation;

Now we can code the actual collision detection.

The CD (Collision Detection) class

What we will do now is implement the first phase of collision detection. As we have discussed, the algorithms we will use are computationally expensive and we only want to use them when there is a realistic chance of a collision. For this reason, we will check the ship against every asteroid using the radius overlapping method. You could go further than this tutorial and implement neighbour checking before this as well.

These first checks will decide whether we then move on to do the more accurate and computationally expensive checks. We will implement these second phase checks a bit later, which will use more advanced algorithms and put the data in our collision packages to full use.

To get started create a new class and call it CD. Add a member PointF object and initialize it. We will use it to avoid creating new objects during the critical parts of the code.

private static PointF rotatedPoint = new PointF();

Now for the method.

Implementing radius overlapping for asteroids and ship

Let’s add our method to the CD class to detect collisions between the ship and asteroids. As we discussed, we are only implementing the first part of this method for now. Here is the implementation of the radius overlapping code.

The code works by making a virtual triangle with a missing side and then using Pythagoras’ theorem to calculate the missing side, which is the distance between the centre points of the two objects. Then if the combined radii of the two objects are greater than the distance between the two object centres we have an overlap.

Add the detect() method with the radius overlapping code. Notice we return true if the radii overlap. This one line of code will be replaced with the more accurate detection code in a minute.

public static boolean detect(
	CollisionPackage cp1,
	CollisionPackage cp2) {

	boolean collided = false;

	// Check circle collision between the two objects

	// Get the distance of the two objects from
	// the centre of the circles on the x axis
	float distanceX = (cp1.worldLocation.x)
		- (cp2.worldLocation.x);

	// Get the distance of the two objects from
	// the centre of the circles on the y axis
	float distanceY = (cp1.worldLocation.y)
		- (cp2.worldLocation.y);

	// Calculate the distance between the center of each circle
	double distance = Math.sqrt(
		distanceX * distanceX + distanceY * distanceY);

	// Finally, see if the two circles overlap
	// If they do it is worth doing the more intensive
	// and accurate check.
	if (distance < cp1.radius + cp2.radius) {

		// todo  Eventually we will add the
		// more accurate code here
		// todo and delete the line below.
		collided = true;
	}

	return collided;
}

Now we can test for the ship hitting an asteroid, although only with radius overlapping method.

Your code in the update part of the main game loop to check an array full of asteroid objects against an object called ship, might look something like this next code.

// Check collisions between asteroids and ship
// Loop through each asteroid in turn

for (int asteroidNum = 0;
	asteroidNum < numAsteroids;
	asteroidNum++) {

	/*
		In a real game you might have a way to
		check whether a specific asteroid is
		currently active before testing
		No point doing anything if asteroid blew up last frame
	*/

	// Perform the collision checks by
	// passing in the collision packages
	if (CD.detect(ship.cp, asteroids[asteroidNum].cp)) {

		// hit!
		// What happens here is specific to your game
	}

}

At this point, you could play your game and our rudimentary collision detection will work. But fly too close to an asteroid and you will lose a life without actually needing to touch it. We want to be able to skim the surface of an asteroid and only get a hit when a point actually crosses into the exact space of another object.

Precise collision detection with asteroids

Once we have rotated and translated the asteroid’s vertices we will need to handle them in pairs of vertices that each forms a line. It is these lines that we will test against each and every vertex from the spaceship. This test will enable us to use our crossing number algorithm which we have discussed.
We need to do all of this within the body of the

if (distance < cp1.radius + cp2.radius) { ...}

where we previously just returned true.

There is quite allot of code so we will split it into chunks so we can see what is going on at each stage. Also, the code indentation will not always be consistent from block to block. This is so the format is in the most readable way possible for a web page. The next few blocks of code are the entire contents of the aforementioned if block that needs replacing.

Before we jump into the for loops, we will compute a few things that won’t change for the duration of this method. The sine and cosine of the facing angle from each of the two collision packages.

if (distance < cp1.radius + cp2.radius) {

	// todo  Eventually we will add the
	// more accurate code here
	// todo and delete the line below.
	// collided = true;

	double radianAngle1 = ((cp1.facingAngle / 180) * Math.PI);
	double cosAngle1 = Math.cos(radianAngle1);
	double sinAngle1 = Math.sin(radianAngle1);

	double radianAngle2 = ((cp2.facingAngle / 180) * Math.PI);
	double cosAngle2 = Math.cos(radianAngle2);
	double sinAngle2 = Math.sin(radianAngle2);

	int numCrosses = 0; // The number of times we cross a side

	float worldUnrotatedX;
	float worldUnrotatedY;

Now we loop through all the vertices from cp2 then test each in turn with all the sides (vertex pairs) from cp1. Remember an asteroid has an extra vertex of padding which is the same as the first. So we can test the last side/line of the asteroid. So we must always pass in the asteroid collision package as the SECOND argument when calling CD.detect().

In the next block of code, we translate then rotate the object being tested against an asteroid.

for (int i = 0; i < cp1.vertexListLength; i++) {

	worldUnrotatedX = cp1.worldLocation.x + cp1.vertexList[i].x;
	worldUnrotatedY = cp1.worldLocation.y + cp1.vertexList[i].y;

	// Now rotate the newly updated point, stored in currentPoint
	// around the centre point of the object (worldLocation)
	cp1.currentPoint.x = cp1.worldLocation.x +
		(int) ((worldUnrotatedX - cp1.worldLocation.x)
		* cosAngle1 - (worldUnrotatedY - cp1.worldLocation.y) *
		sinAngle1);

	cp1.currentPoint.y = cp1.worldLocation.y +
		(int) ((worldUnrotatedX - cp1.worldLocation.x)
		* sinAngle1 + (worldUnrotatedY - cp1.worldLocation.y) *
		cosAngle1);

	// cp1.currentPoint now hold the x/y
	// world coordinates of the first point to test

Now, using a pair of vertices at a time, from the asteroid, we translate and rotate both to their final world-space coordinates, ready for the next block of code where we will use the vertex locations calculated in the previous block and this block.

/*
	Use two vertices at a time to represent the line we are testing
	We don't test the last vertex because we are testing pairs
	and the last vertex of cp2 is the padded extra vertex.
	It will form part of the last side when we test vertexList[5]
*/

for (int j = 0; j < cp2.vertexListLength - 1; j++) {

	// Now we get the rotated coordinates of
	// BOTH the current 2 points being
	// used to form a side from cp2 (the asteroid)
	// First we need to rotate the model-space
	// coordinate we are testing
	// to its current world position
	// First update the regular un-rotated model space coordinates
	// relative to the current world location (centre of object)

	worldUnrotatedX = cp2.worldLocation.x + cp2.vertexList[j].x;
	worldUnrotatedY = cp2.worldLocation.y + cp2.vertexList[j].y;

	// Now rotate the newly updated point, stored in worldUnrotatedX/y
	// around the centre point of the object (worldLocation)

	cp2.currentPoint.x = cp2.worldLocation.x +
		(int) ((worldUnrotatedX - cp2.worldLocation.x)
		* cosAngle2 - (worldUnrotatedY - cp2.worldLocation.y) *
		sinAngle2);

	cp2.currentPoint.y = cp2.worldLocation.y +
		(int) ((worldUnrotatedX - cp2.worldLocation.x)
		* sinAngle2 + (worldUnrotatedY - cp2.worldLocation.y) *
		cosAngle2);

	// cp2.currentPoint now hold the x/y world coordinates
	// of the first point that
	// will represent a line from the asteroid

	// Now we can do exactly the same for the
	// second vertex and store it in
	// currentPoint2. We will then have a point and a line (two
	// vertices)we can use the
	// crossing number algorithm on.

	worldUnrotatedX = cp2.worldLocation.x
		+ cp2.vertexList[i + 1].x;

	worldUnrotatedY = cp2.worldLocation.y
		+ cp2.vertexList[i + 1].y;

	// Now rotate the newly updated point, stored in worldUnrotatedX/Y
	// around the centre point of the object (worldLocation)
	cp2.currentPoint2.x = cp2.worldLocation.x +
		(int) ((worldUnrotatedX - cp2.worldLocation.x)
		* cosAngle2 - (worldUnrotatedY - cp2.worldLocation.y)
		* sinAngle2);

	cp2.currentPoint2.y = cp2.worldLocation.y +
		(int) ((worldUnrotatedX - cp2.worldLocation.x)
		* sinAngle2 + (worldUnrotatedY - cp2.worldLocation.y)
		* cosAngle2);

Here we detect if the current vertex being tested crosses the line formed by the current vertex pair of the asteroid. If it does we increment numCrosses.

// And now we can test the rotated point from cp1 against the
// rotated points which form a side from cp2

if (((cp2.currentPoint.y > cp1.currentPoint.y)
	!= cp2.currentPoint2.y > cp1.currentPoint.y))
	&&(cp1.currentPoint.x <
	(cp2.currentPoint2.x - cp2.currentPoint2.x)
	*(cp1.currentPoint.y - cp2.currentPoint.y)
	/ (cp2.currentPoint2.y 	- cp2.currentPoint.y)
	+ cp2.currentPoint.x)){

	numCrosses++;
} // end if
} // end inner for loop
} // end outer for loop

We could have made a separate method to rotate angles as we do this so often. It is not as straightforward as it might seem, however. If we put the rotation code in a method we would either have to put the initial sine and cosine calculations in it which would make it slow or pre-compute them before the method call and the for loops which is kind of untidy itself.

Also if you consider that we need more than one value for both sine and cosine of an angle, the method needs to ‘know’ which to use, which isn’t rocket science but it starts to get even less compact than we might have initially imagined. So I opted for avoiding the method call altogether, even if the code is a little sprawling.

So if you want to tidy things up, go ahead. I just thought it was worth discussing why I did things this way.

Finally, we use the modulus operator to determine if numCrosses is odd or even. As discussed, we return true (collision) for odd and false (no collision) for even.

// So do we have a collision?
if (numCrosses % 2 == 0) {
	// even number of crosses(outside asteroid)
   collided = false;
} else {
	// odd number of crosses(inside asteroid)
   	collided = true;
}

}// end if

You can now fly your ship right up to the asteroids and only get hit when it really looks like you should.

You can see the simple Asteroids game I adapted this code from by downloading the GameCodeSchool app from GooglePlay.