The Essential Guide to HTML5

CHAPTER 7

Collision detection: token and any wall

To traverse a maze, the player must not move the token across any wall. We will enforce this restriction by

writing a function, intersect, that returns true if a circle with given center and radius intersects a line

segment. For this task, we need to be exacting in our language: a line segment is part of a line, going from

sx, sy to fx, fy. Each wall corresponds to a finite line segment. The line itself is infinite. The intersect

function is called for each wall in the array walls.

Tip: My explanation of the mathematics in the intersection calculation is fairly brief, but may be

daunting if you haven
t done any math in a while. Feel free to skip over it and accept the coding as is

if you don
t want to work through it.

The intersect function is based on the idea of a parameterized line. Specifically, the parameterized form

of a line is (writing mathematical formula, as opposed to code)

Equation a: x = sx + t*(fx-sx);

Equation b: y = sy + t*(fy-sy);

As parameter t goes from 0 to 1, the x and y take on the corresponding values of x, y on the line segment.

The goal is to determine if a circle with center cx,cy and radius rad overlaps the line segment. One way to

do this is to determine the closest point on the line to cx,cy and see if the distance from that point is less

than rad. In Figure 7-8, you see a sketch of part of a line with the line segment depicted with a solid line

and the rest of what is shown of the line indicated by dots. The value of t at one end is 0 and the other end

is 1.There are two points c1x,c1y and c2x, c2y. The c1x,c1y point is closest to the line outside the critical

line segment. The point c2x,c2y is closest somewhere in the middle of the line segment. The value of t

would be between 0 and 1.

Figure 7-8. A line segment and two points

The formula for the distance between the two points (x,y) and (cx,cy) is

distance = ((cx-x)*(cx-x)+(cy-y)*(cy-y)).5

Substituting for x and for y using equations a and b, we get a formula for distance.

Equation c: distance = ((cx-sx+t*(fx-sx))*(cx- sx + t*(fx-sx))+(cy- sy + t*(fy-

sy))*(cy- sy + t*(fy-sy))).5