I'm currently implementing the field of view of a player in a 2D-grid based game. I've chosen a standard ray tracing algorithm because he really fits the features needed in my game.
However, the cells aren't just opaques or transparents. They can be "partially opaques", which means that they decrease the length of the line of the sight more than the others (we don't see as far in water than in the air!). Concretely, the player has a given "vision potential", and each cell has a "vision cost". For each cell crosses by the ray during the ray tracing, I decrease the vision. When it hits zero, I stop the ray.
Things are OK here. But this algorithm leads to some artefacts, as described in the last part of this document:
Ok, we have thrown rays all aroung our @, flagging each cell as visible. When we move aroung the dungeon, we notice some artifacts appearing on some walls, especially when the @ is near the wall.
Since we stop the ray as soon as it reaches a wall, when the ray is almost parallel to the wall, there may be some missing wall cells in the resulting potential visible set. [...] The issue is due to the fact that the ray should keep going until it reaches the other side of the wall and not stop on the first cell. But this is not possible since we have only a boolean 'lightThrough' information and not the wall orientation.
Fortunately, there is a trivial trick which will allow us to remove those artifacts without adding more information on the cell. It is based on a simple observation : if the player sees a ground cell, he sees the wall behind it. [...]
Thus, our post-processing algorithm consist of :
loop through all cells of the visible map.
if the current cell is a hidden wall and is directly behind a visible ground cell (depending on the region the current cell is in), we can flag it as visible.
The result : on the left, the PVS [potential visible set] without the post-processing step. The yellow arrows show the missing cells. On the right, the PVS with the post-processing step.
The document suggests a post-process treatment, but it obviously doesn't work in my situation. What can I do instead?