Learn to Code Asteroids – Lesson 4 – Point in Polygon Collision Detection

Our game is now starting to take shape. We’ve got full control over a player ship movement and were able to create an asteroid field full of well formed, randomly shaped vector asteroids. But a shoot-em-up game isn’t really a game until you can start shooting things. So in this lesson will be concentrating on allowing our player to shoot bullets and blowup asteroids.

To begin with we’ll need to get some player bullets on the screen. Because of the way we’ve written our code in nicely segmented functions, most of the software required to get our bullets moving around the screen has already been written. All we need to do is monitor the fire button and then generate some bullet objects which contain a position object to describe where it is on the screen and a velocity object to describe its motion.

Once we got the bullets firing on the screen we need to tackle what is probably the biggest challenge in this game. How to work out if a bullet has hit an asteroid.

In our simpler games we used a bounding box collision detection algorithm where we modelled each game object as a rectangle and simply tried to work out when certain rectangles touched or overlapped. This was quite an easy algorithm to code but it’s not going to work for us in our asteroids game. We spent a lot of time in lesson 3 writing software to build elegantly crafted randomly shaped asteroids. If we try and use a bounding box, or a bounding circle will start to get lots of false hits as a bullet gets close enough to the asteroid to enter the bounding circle but misses the actual asteroid shape because it’s indented at the point where the bullet enters.

Will find that are bounding circle collision detection is still very useful for working out which bullets are close enough to which asteroids for a hit to be possible. This algorithm is fast and lets us quickly rule out any asteroids that have definitely not been hit. But once we find a bullet close enough to an asteroid will need a much better algorithm. In this lesson I’ll talk you through the theory behind the Crossing Number algorithm (also known as the Ray Casting algorithm or Crossing Line algorithm).

This algorithm lets us take a point and work out if it is inside an irregularly shaped polygon such as one off our asteroids. The code will have to be built up in a number of steps and again I’ll be giving you a chance to develop your own solution to the problem. We also have a go at optimising the algorithm so that it executes as fast as possible and doesn’t slow our game down every time a bullet gets near to an asteroid.

As always I’ll be talking you through my full solution so that you can see how it all fits together and end up with a fully working system.

The full code for this lesson is available below.

Code for Lesson 4