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

Collision detection is one of those old, hidden problems of coding a game. Typically people take darkpenguin's approach of precalculating in some fashion where on your static map is and is not placeable. The next step is to come up with a way to specify the most efficient collide map.

You don't want your game to do a ton of math in response to the user moving their mouse - it needs to be short and quick - so precalculating down to something quick is critical.

If your map is a grid, then you have your answer right there - the collision map is a precalculated 2D array - basically a very small black and white image with a pixel for each place on the grid. White pixels (1) are placeable and black pixels (0) are not. You just use this 2D array of true/false as a lookup. If you want to save memory you can bundle each strip of 32 spaces on the grid into a single bit flag.

If your map is not a grid, then you still want to precalculate things, but the strategy is a bit more complex. The first possibility is to perform math like Hitesh to produce a slightly higher-resolution collide map, and then the rest is exactly as the grid strategy - so for example if every 4x4 block of pixels was one collide entry, then whether a tower can be placed is a test as to whether its coordinates test out to be on top of enough 1's - you might require 100% of tests be 1's, or you might let them reach a little and let say 75% of tests be 1's.

If this still is not enough detail, you can do these more complex polygon tests, but you want them to be as simple as possible. When not using a precalculated grid, the simplest 2D collision test is 2 circles - you just calculate the distance between their centers and check if it's greater or less than the sum of their radii. If you precalculate your monster path into a trail of circles, the next step is to partition those circles into... guess what... a grid. This prevents every check from having to test every single circle on the map. This allows you to have a high number of these circles in the collision map, as the collision test is first a lookup into what grid entries the tower is currently over, followed by checking if it's colliding with just the circles it's closest to, rather than the entire map. It's important to note that this precalculated grid of circle lists will often have the same circle in multiple neighboring grid entries, because every grid entry that contains any portion of a given circle must have that circle in its collide checklist.

One of the nice things about the first 2 grid approaches is that it's very easy to QA yourself - literally store the collision map as an image and visually inspect it to ensure it looks right for the map it's based on. You can also draw it by hand if you don't want to write the code to generate them.

The circle approach gives you legitimate curves and can lead to finer collide edge detail, but it's obviously harder to test and ensure no maps have bad collide maps. It's also more work to write the map generation tool.

Good luck!

Answer 2

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.