How can I modify this line of sight algorithm to accept rays which pass through corners?

Question

I am working on a pathfinding algorithm based on Theta*, a variant of A* which provides a good system for pathfinding which is not constrained to a grid, even though the terrain/obstructions are based on a grid pattern. This system requires a line of sight algorithm to determine whether or not a particular path is obstructed.

I found this extremely useful line of sight algorithm, and I've successfully implemented it in my code. Unfortunately, it considers the following to be an invalid path:

However, for my purposes, I want such a path to be considered valid. I've tried to modify the algorithm by detecting whether or not a point is on the line itself using the basic y = mx + b formula, but the algorithm's inconsistencies prevent me from relying on such a system.

Is there any efficient way to modify this algorithm to allow such a path? Is there another algorithm that would work better? Keep in mind that the start and end points of the path will not necessarily be confined to a grid, so all points use double precision.

Answer 1

the code you reference actually omits to explicitly handle the case where the line goes through a grid point (where four squares touch). You need to check for error == 0.

In this case, at most one of the four squares touching the grid point may be blocked to still have a valid path.

Regards, Erich