Field of view determination with partially opaque cells

Question

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?

Answer 1

Fundamentally I think this is a problem with the grid-based ray casting being a pretty inaccurate and granular approximation of the 'real' thing you're trying to simulate. No matter what you'll do you'll run into problems.

Instead of thinking about it in terms of the specifics of the iteration and implementation, think of it as if your world was actually made of blocks which are the size of your grid squares.

You are casting rays as if they were going through the centre of each block. And you're modelling visibility drop as if a partially opaque block was made of some material which acted like depth fog (i.e. the visibility drop from passing through the block was proportional to the amount of block the ray passed through).

Let's assume you are standing and looking at a block 2 north and 2 east of your position. If you look at the corner of the block closest to you (the SW corner), you actually have ~1.414u of block to look through. If you look at the NW or SE corners, your vision ray passes through no block at all. It's a fundamentally flawed approximation to model visibility loss in this way. The correct way to model it would I think be to raytrace to each corner of each cell instead, and use the maximum of the 4 values. I'm guessing that is rather too expensive, and if you're stuck using an integral/Bresenhams raytrace then it simply won't be possible.

I'm also assuming that you're setting the cell visibility (i.e. how bright the cell is) based on the visibility level of the ray as it enters that cell. So a ray passing through fully transparent air sets all the cells to 100% visible, then when it hits an opaque wall the entry visibility is 100% (so the wall is fully visible) but the exit visibility is 0% (so no cells afterwards are visible).

If this case is indicative of your problem:

What you're seeing is probably made worse by the inaccuracy of the Bresenham traversal meaning that some cells appear blocked when they're actually not. I suspect what's really happening is that your visibility drop through a block isn't actually taking account of how much of a cell the ray covers. Bresenham's doesn't give you an anti-aliased line, it either hits a cell or it doesn't. But if the calculation was done at the proper resolution, you'd see that some cells have a long stretch of line passing through them, and other cells have only a short stretch (because the ray line just clips the corner of the cell). You need to make the visibility drop proportional to the length of the line in the cell with that degree of opacity. If the line just clips the corner of the 90% opaque cell, it should lose much less visibility than if it goes from corner to corner across the diagonal. To get that information you need the fractional portion of the ray traversal, i.e. you need to do the floating point math to calculate the line properly. Even then that won't fix your problem, because you're still calculating visibility at the centre of the cell rather than across the visible faces of your cell blocks, but it'll get you closer.

If you don't want to do that, I think you can get a decent workaround that won't impact on your system too much. Every time a ray terminates in a grid cell due to loss of visibility, and the grid cell is not fully opaque, then mark the grid cells just beyond as visible, at the same visibility level as the ray was when it terminated. If you later visit one of those cells with a direct ray-trace and find they're more visible, then you use the higher visibility value.

For 'just beyond', I mean one more in each direction. If the ray you're casting has any northward component, mark the cell to the north as visible, if it has any eastward component mark the cell to the east as visible, etc.

What that will do is cause a bit of visibility bleeding, such that a visible partially opaque cell will cause others nearby to also become visible, at a higher level than they should properly get.