Please help me with a trigonometric algorithm

Question

Here is a graphic representation of the problem: http://i.imgur.com/aBG3p.jpg

Given a starting point (x1,y1) and a destination point (x2,y2), I must determine if the path between the two points is open or, if it is not open, which coordinate the collision happens on.

It would be a trivial problem except for the special rules involved:

1. The line can intercept a point, call it (i,j) to a small and varying degree without causing a collision. If (i,j) is directly adjacent to (x1,y1), we can safely cut about 0.4 over its corners without triggering a collision. However we cannot cut 0.4 over if going directly through it, only over the corners. This number tapers off to about 0.2 as we get further away from (x,y). Unfortunately I'm just trying to reconstruct something I saw once, so I don't know the exact values, I'm just approximating them.

2. The caveat to 1: If the space directly beside (i,j), in the plane that we are intersecting, on the side that we are intersecting, is also occupied, there will be a collision no matter what. The collision will happen (i,j) if we intercept it by too much, otherwise in the relevant adjacent tile.

I've made several tries to crack this problem, always ending up with false negatives and/or the collision resulting on the wrong tile. I tried to do it without considering the angle, just by looking at the decimal points of x and y as we travel down the line. I'm not sure if it is possible to do this, or if I must use the angle in some way, or if using the angle in some way could make my life easier.

Please help if you can!

Answer 1

It seems like you could get results similar to what you describe by treating the occupied grids as containing unit circles. That would let you pass corners, but block on any 2 adjacent ones, since they contact.

So I'd try using your current collision method to check rectangles quickly, then refining it once you found a collision, by testing the line entering the box against a circle centered in it.