Tricky Line Algorithm for a Game (language agnostic)

Question

I need help creating a specialized line-collision algorithm that allows "cutting corners" at certain angles.

In the following pictures, let the blue square represent the player and the black square represent a wall. The white squares, then, represent squares in a player's "line of sight" (valid squares), and the grey squares are squares outside a player's "line of sight" (invalid squares):

The second image is where things get more interesting as we start cutting corners:

Let's take a closer look at this line which is allowed despite passing over the corner of the wall:

The line is allowed because:

• dx <= 0.5 (with a square being 1x1)
• dx/dy is above a certain ratio (say, 2 - I'm not sure of the exact value represented in these images.)

The converse line is not allowed because the ratio (of dy/dx in this case) is too low:

Or perhaps I should talk about the angle of entry vs exit from the square....

The main problem I'm having is that I can't figure out how to generalize a solution for vectors traveling at any angle between two points on the grid. I can't decide if I should use trigonometry or what. My closest solution so far has been to use the decimal parts of line interceptions with each square as the dx and dy's and check whether it's allowed based on the slope of the line and what quadrant it's in.

Can anyone help?

I've also looked at borrowing or starting from other line algorithms, but I haven't found anything too useful. Most of them that I've seen want a line from (x1, y1) to (x2, y2) to be the same as from (x2, y2) to (x1, y1) which makes this problem quite different.

Answer 1

I suggest using circles, they are quite optimal corner wise.

I assume that coordinates are taken at the center of each pixels.

The algorithm for knowing if (xo,yo) is hiding the view from (xa,ya) to (xb,yb) would then be:

• compute (xc,yc) the nearest point to (xo,yo) on the line from (xa,ya) to (xb,yb)
• compute distance d from (xo,yo) to (xc,yc)
• if d < half a pixel, then the view is hidden

You can simplify first two stages by directly calculating the distance between point and line http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line and eventually compute squared distance if you want to avoid sqrt