Our purpose here is to determin which cells are potentially visible by the player (the little @ in the center of the screen). A cell is potentially visible if nothing blocks a ray of light going from the player to the cell. Note that even if a cell is potentially visible, it still can be hidden if there is no light on this cell (cell in darknes). 

The algorithm described here may not be the fastest on the market, but it's damn easy to implement and give a clean, artifact-free potential visible set (PVS).

We need two things :

• the position of the player, shown by the @ character
• a grid of cells around the player, each cell having a 'lightThrough' property which indicate if we can see through the cell. Walls and rock cells block the light, empty or window cells let it pass through. On following pictures, empty cells which let the light through are in dark gray, wall cells which block the light are in light gray.

First step: ray casting

The first step consist in casting rays of light all around the player position. A ray of light marks all cells it travels through as visible. It stops as soon as it reaches a light blocking cell. 

We cast rays from the player position to every cell on the border of the visible map. For this step, we need to have a function which gives us the coordinates of all the cells the ray travels through from the starting and ending cells coordinates. Fortunately, there is a well known algorithm which already does this :

The bresenham's line algorithm

Issues with bresenham ray casting

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.

Look at that case. We throw a first ray which lits some ground cells and a wall cell (the cells with a yellow border). No we cast the next ray :

Again, we have some ground cells marked as visible and a single wall cell. Now if we show all cells marked as visible for those two rays, we have :

As we can see, the cell with a cross is not marked as visible whereas it should be. 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.

The post-processing artifact killer

"The wall begin a cell" has a different signification depending on the part of the map we look at :

Here we have yellow crosses on each ground cell that has a wall cell behind it (from the player point of view). We see that we have to divide the map into four region :

• the north-west region in which a wall is behind a ground cell if it is north to a ground cell or west to a ground cell
• the north-east region in which a wall is behind a ground cell if it is north to a ground cell or east to a ground cell
• the south-west region in which a wall is behind a ground cell if it is south to a ground cell or west to a ground cell 
• the south-east region in which a wall is behind a ground cell if it is south to a ground cell or east to a ground cell

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 without the post-processing step. The yellow arrows show the missing cells. On the right, the PVS with the post-processing step.