How can I change the algorithm of this line of sight to receive rays passing through corners?

Question

I am working on a Theta * -based path search algorithm, A * variant, which provides a good path-finding system that is not limited to a grid, even if the terrain / obstacles are based on a grid pattern. This system requires the line of sight algorithm to determine if a particular path is obstructing.

I found this extremely useful line-of-sight algorithm, and I have successfully implemented it in my code. Unfortunately, he considers the invalid path as follows:

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

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

Answer 1

the code you refer to does not actually allow you to explicitly handle the case where the line passes through a grid point (where four squares touch). You need to check error == 0 .

In this case, at least one of the four squares affecting the grid point may be blocked in order to still have a valid path.

Regards, Erich