HTML5 Canvas: Mouse and polygon collision detection

Question

So I'm making a tower defense game with HTML5 and Javascript. My sole problem is detecting when the mouse comes in contact with the attacker's pathway, which is necessary in order to stop the player from building towers on the path. The path of the attackers is determined in the MAP.js file (see the link at the bottom), by a two dimensional array (an array containing x and y pairs), so what I have to work with is a series of points that make up a path when connected. I merely want to prohibit the player from placing towers within, say, 50 pixels of the path. To be honest I am just awful with collision detection, so some help would be greatly appreciated.

Here is the link to all the code: http://shapeshifting.comuv.com/Tower_Defense/td/

As you might imagine, only the .js files are applicable, but most of the relevant code is inside the objects.js file. (PLease excuse the messiness)

Answer 1

I would approach this in steps. Let's look at what you start with. You have a path defined by points -- pairs of points define a line segment. So what you really have is a path made of line segments. When the user moves the mouse, you will get x,y coordinates of the current position. What you want to do is find the distance of the mouse point to all of the line segments. If it is less than 50 pixels from any line segment, then you don't want to allow them to build there.

To find the distance between a point and a line segment, the pseudo code looks like this. Assume that points A and B represent both ends of a line segment and point C is the mouse point.

float distancePoint2LineSegment(Point a, Point b, Point c) {
  Vector ab = b - a
  Vector ac = c - a
  Vector bc = c - b

  float e = dotProduct(ac, ab)
  if (e <= 0.0)
    return sqrt(dotProduct(ac, ac))

  float f = dotProduct(ab, ab)
  if (e >= f)
    return sqrt(dotProduct(bc, bc))

  return sqrt(dotProduct(ac, ac) - e * e / f)
}

This would answer your collision detection question but I think you'd then want to look at performance. How many line segments will be in your path and do you want to calculate the distance to each line segment every time the user moves their mouse? You can put the line segments into a quadtree so that you'd only have to test mouse point collisions against a smaller number of line segments.