Monday 14 August 2017

Line-of-sight problem description

The line-of-sight problem or LOSP can be compared to Nth Prime Number problem with difference that prime numbers are easier, yet I think no solution has been found to Nth problem for 2300 years. Like Nth the LOSP is seemingly easy, but still impossible to solve. In theory line-of-sight always works in infinite precision, but in 2D map of a roguelike it's not infinite, but an approximation that can "flip" the location of line to "wrong" tile depending on floating point calculations in that particular processor.

This image shows the problem in action. The red line is line-of-sight in infinite theoretic space and the blue line is an approximation in 2D map (green is wall). The black tile is often called an artifact of the result where line drawing stops before it reaches the required wall tile. In finite space the line simply stops in walls before that one artifact location.

There are number of ways to fix this problem, but none of them actually can do anything about the finite precision conversion. One of the solutions is find those artifacts and fix them using a simple routine to check their location in context to origin point of the FOV calculation. The issue with fixes are that they make the FOV routine often about two times slower, or even more. So is it a problem in modern computers? I think it is. If you want to keep the speed of game loop at least somewhere in 20-50ms (using one core) then you need a fast FOV routine.

FOV becomes critical in situation where other than player character have it, similar to more advanced path finding routines. It's possible to make the game very slow very easily with slow routines. That's why finding a solution to this problem could be nice.

No comments: