Engine: Improving Line of Sight With Bresenham's Line Algorithm
I have gone back to using the Manhattan distance heuristic for now. Even though the Diagonal method is far more accurate and quicker, I found that it causes my enemies to hug walls along their paths.
Previously: http://anthonydev.tumblr.com/post/53774080879/2d-engine-line-of-sight
Last week, I began to smooth out my previous Line of Sight implementation.
While testing, I noticed that in small corridors and at the edge of obstacles, enemies doing Line of Sight checks were either failing miserably or succeeding where they should not have been.
I has recently implemented a new (and improved) Pathfinding heuristic, which I also used for my previous LoS calculation. I had been using a Manhattan distance heuristic, which is a 4 direction distance heuristic. I changed it to a Diagonal distance heuristic, which takes into account 8 directions of movement. This made my pathing more accurate, but in turn it broke my Line of Sight implementation.
Hard lesson: using a pathfinding system to calculate Line of Sight may not be the greatest idea.
Above: Using pathfinding for Line of Sight. Works when breaking a direct path. Red line indicates that when pathing, it found an unwalkable area. Green line indicates what the path would look like if it continued. Previously, hitting a wall indicated a false LoS and cancelled further path checking..
Above: Again, using pathfinding for Line of Sight. With my new heuristic, it fails because it can path around objects when the destination is positioned in a way that the path check will not hit a wall. Here, it doesn't butt up against a wall, it takes a quicker route down and across.
I was able to remedy this by implementing Bresenhem's line algorithm as the Line of Sight checker.
As I noted in the previously article, when I load my world and my collidable sprites are placed, it flags the sprite positions on a 2D array. This is so the pathfinder knows where it can walk and cannot walk on the pathfinding grid. This marked grid is called the unwalkable grid.
Utilizing this 2D array, my LoS check now starts from a source (i.e. an enemy) and begins the grid check to the destination (i.e. the player) using Bresenham's algorithm. At each grid plot, we check it against the unwalkable grid. If that plot is labelled as unwalkable, LoS returns false because it would break a successful straight line check. If the line is successfully completed without any of the grid points being unwalkable, we can return true, which means an unobstructed plot from source to destination.
The algorithm, from what I have read, is commonly used for various graphics rendering, but I think works well for Line of Sight checking.
