I am currently working away at Drone Tournament, Game #2 for 2016, and started implementing combat into the game. In order to make combat happen, each little drone unit in the game will be able to fire their weapon every so often, and if they hit an opponent it loses armor and can be destroyed.

The trick is how to figure out if we get a hit.

Previous Collision Detection

At the beginning of 2015 I made my first game Prism Ship with Monkey-X and it implements a little ship that shoots blocks. The collision detection there is not pretty but fairly simple because everything is kept square and straight.

Projectiles go straight up and the things they hit are coming straight down so no real fancy math is needed. I simply checked each of the corners of the projectile to see if they were inside the squares you are trying to hit.

A New Challenge

In Drone Tournament however, things can turn when they shoot which means that bullets go off at weird angles and their potential targets are not always moving directly towards them. Additionally I did not make the projectiles in this game as large as in Prism Ship. They are basically line segments.

It Has Been Solved

This problem is common enough that it has been solved before, and in a most elegant and simple manner. Here is some Monkey-X code that I derived from an implementation of the solution in Python. I will explain what is going on below. I even borrowed a picture that shows what is going on really well.

	Function LinesIntersect:Bool(pointA:Vec2D, pointB:Vec2D, pointC:Vec2D, pointD:Vec2D)

		Local abc:Bool = CounterClockwise(pointA, pointB, pointC)
		Local abd:Bool = CounterClockwise(pointA, pointB, pointD)
		Local cda:Bool = CounterClockwise(pointC, pointD, pointA)
		Local cdb:Bool = CounterClockwise(pointC, pointD, pointB)

		Return(( abc <> abd) And (cda <> cdb))
	End

        Function CounterClockwise:Bool(pointOne:Vec2D, pointTwo:Vec2D, pointThree:Vec2D)
	        Return ((pointThree.y - pointOne.y) * (pointTwo.x - pointOne.x) > 
                        (pointTwo.y - pointOne.y) * (pointThree.x - pointOne.x)) 
        End

For those of you not familiar with Visual Basic, "<>" is its way of writing "!=" (Not Equal)

Explanation

If you remember from your geometry class back in high school, line segments have a slope which just measures the change from the beginning point to the end. If you have three points A, B, and C, and the slope of the line from A to B is larger than the slope from A to C (meaning it changes more) then the points are in Clockwise (CW) order. If the slope from A to B is less than that of A to C then they are considered Counter Clockwise (CCW).

Image borrowed from here (article 1 in reference below).

So we test the two points of our particle to see whether they are CW or CCW to each edge of the Drone hit box. If 1 point is CW and the other is CCW to an edge, then we know that the lines intersect because you have a point on either side of the edge of the hit box.

Special Case I am Ignoring

There is a special case where the 2 lines lay across one another called Collinear. I am ignoring this special case because for the purposes of the game it would not really be a solid hit and is not that important. If you would like to know how to handle it you can read more about this solution at the following articles.

References

1. Line Section Intersection Algorithm
2. How To Check If Two Line Segments Intersect?
3. Stack Overflow: How Can I Check If Two Segments Intersect?

I Want to Be a Better Developer