Introduction

After completing my Dungeon Generation article series I started hacking around some code to walk around on my generated maps. Walking around on a fully visible map is Ok but you immediately realise the need for some kind of way to determine which parts of the map are visible to the player.

This is where field of view (FOV) algorithms come into play. There are various techniques available and you can read about them on RogueBasin. I will be basing this article on the technique developed by Björn Bergström called Recursive Shadow Casting. My goal is to give his article the c# treatment and to, hopefully, expand on his explanation.

The shadow casting algorithm calculates visibility by determining which cells fall in within shadowed areas and which don’t. The crux of the algorithm is in determining these shadowed areas in an efficient manner.

An example of shadowed area can be seen in the following diagram. Obstructions are indicated by the ‘#’ character, shadowed areas by the ‘s’ character and ‘.’ characters indicate movable terrain.

//   01234

//

// 0 .ss..

// 1  .s..

// 2   .#.

// 3    ..

// 4     @

In the above diagram we observe that the obstruction at (3, 2) casts a shadow on the cells at (1, 0), (2, 0) and (2, 1) respectively. The beauty of this algorithm is that these cells weren’t visited to determine if they were visible or not. The algorithm therefore becomes more efficient with more obstructions closer to the player.

Ok so how does it work?

It’s all the in slope

The way cells are visited is determined by the start and end slope of the scan lines. The picture below shows the scan lines used in the diagram above. The line marked (a) is our starting scan line and the line marked (b) the end scan line. The slope of a line can be calculated using the following formula :

Using the above formula we calculate the slope of scan line (a) as (5 – 0) / (-5 – 0) = -1. What this means is that for each increase along the y-axis the value of x is decreased by one.

The slope of scan line (b) is calculated as undefined due to division by zero (5 – 0) / (0 – 0) = undefined. All this means is that for each increase along the y-axis the value of x stays the same i.e. 0.

Now that we have a start and end slope we can determine (for a particular y value) the start and end x values to scan. So for a y value of 1 we will scan from (-1, 1) to (0, 1). For a y value of 5 we will scan from (-5, 5) to (0, 5).

The above calculation is the basic building block for implementing the shadow casting algorithm and allows you to scan all the cells between two lines.

Lets write a test to verify that we can scan all the cells within a maximum radius in the above octant. Don’t worry I will be discussing octants shortly.

[TestMethod]

{

Map map = new Map(3, 3, TileType.Empty);

// Create test scenario

//   012

//

// 0 …

// 1  ..

// 2   @

fov.ScanNorthwestToNorth(map, new Point(2, 2), 1);

Assert.IsFalse(fov.VisibleLocations.Contains(new Point(0, 0)));

Assert.IsFalse(fov.VisibleLocations.Contains(new Point(1, 0)));

Assert.IsFalse(fov.VisibleLocations.Contains(new Point(2, 0)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(1, 1)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(2, 1)));

}

In the above test I create a new map and initialise it to empty tiles. I then instantiate a new ShadowCastingFov instance and call the ScanNorthwestToNorth method. This method takes as input parameters our map instance, the scan origin and the maximum radius (distance) to scan.

The test asserts that the tiles in row 0 are not visible because they fall outside the max radius. Next the test asserts that the tiles in row 1 (1 tile away from the origin) are both visible.

The code to make the above test compile is as follows.

public void ScanNorthwestToNorth(Map map, Point origin, int maxRadius)

{

ScanNorthwestToNorth(map, origin, maxRadius, -1, 0, 1);

}

private void ScanNorthwestToNorth(Map map, Point origin, int maxRadius, float startSlope, float endSlope, int distance)

{

int xStart = (int) Math.Floor(origin.X + 0.5 – (startSlope * distance));

int xEnd = (int)Math.Floor(origin.X + 0.5 – (endSlope * distance));

int yCheck = origin.Y – distance;

for(int xCheck = xStart; xCheck <= xEnd; xCheck++)

SetAsVisible(map, new Point(xCheck, yCheck));

ScanNorthwestToNorth(map, origin, maxRadius, startSlope, endSlope, distance + 1);

}

private void SetAsVisible(Map map, Point location)

{

}

The above code shows two overloaded ScanNorthwestToNorth methods. The public version hides the parameters of startSlope, endSlope and distance. The reason for this is that the values for startSlope, endSlope and distance are always the same when beginning a scan in the NorthwestToNorth octant.

The first line ensures that the recursion won’t repeat further than the maximum radius specified. Next we make use of the start and end slopes to caluclate the start and end x values. The formula calculates the x offset based on the slope multiplied by the distance. Therefore with a start slope of -1 (as discussed above) our x start will decrease by 1 for every increase in distance.

The yCheck variable is used to store the current y value to check and is a function of the origin y value less the distance being scanned. The yCheck variable is constant for each iteration of the ScanNorthwestToNorth method.

Next we loop for each x value from xStart to xEnd and set the location on the map as visible.

Once we’ve visited each tile along the x-axis for the current yCheck position we start a new scan one position further away. This process repeats itself until we’ve exceeded the maximum radius.

I complile the code and the test runs with no problem. We now have the functionality we need to scan the NorthwestToNorth octant for a given radius. The next step is to handle cases where we run into tiles that obstruct our vision.

Dealing with Obstacles

There are basically two types of blocking situations we need to deal with while performing a scan. When I talk about a scan I’m referring to a scan along a particular row (or column depending on the octant we’re in). The first situation occurs when we reach a tile that blocks our line of sight. The second situation occurs when we reach a non-blocking tile after passing through a section of blocking tiles.

1. Entering Obstacles

The first obstacle type will cause a change in the end slope of our next scan. I will use the following diagram to discuss this further. In the above diagram our scan origin is at the point (3,3). We start the scan process as normal by visiting positions (2, 2) and (3, 2). The next scan then starts with (1, 1) and (2, 1). When we reach position (3, 1) we find that our line of sight (LOS) is blocked. We now need to start a new scan that will start at position (0, 0) but stop at position (2, 0).

This is achieved by calculating a new end slope when we reach a blocking tile. The new end slope is calculated using the point that brushes past the bottom left corner of the blocking tile as our end point and the origin of the scan as our start point.

Using our slope formula we calculate our new end slope as (1.99999 – 3.5) / (2.99999 – 3.5) = 2.9 but this is not enough. The original slope formula we used was for lines with their origin at (0, 0) and in the above diagram we moved our origin to position (3, 3). The get the correct slope we need to invert it by dividing our original value into 1. 1 / 2.9 = 0.33

Our starting x value for the row at position 0 (distance = 3) can therefore be calculated as (3.5 – (1 * 3) = 0.5 = 0. The end x value can similarly be calculated using our new end slope as (3.5 – (0.33 * 3)) = 2.49 = 2.

Lets write a test that will illustrate this behaviour.

[TestMethod]

public void TestScanNorthwestToNorthIntoObstacle()

{

Map map = new Map(3, 3, TileType.Empty);

// Create test scenario

//   012

//

// 0 .ss

// 1  .#

// 2   @

map[2, 1] = TileBuilder.BuildTile(TileType.Rock);

fov.ScanNorthwestToNorth(map, new Point(2, 2), 2);

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(0, 0)));

Assert.IsFalse(fov.VisibleLocations.Contains(new Point(1, 0)));

Assert.IsFalse(fov.VisibleLocations.Contains(new Point(2, 0)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(1, 1)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(2, 1)));

}

In the above test we set up our map with an obstable at position (2, 1). We then perform our scan of the NotherwestToNorth octant and test to ensure that all the tiles are visible except the tiles at positions (1, 0) and (2, 0).

I run the test and it fails as expected. Lets write some code to make the test pass.

private void ScanNorthwestToNorth(Map map, Point origin, int maxRadius, float startSlope, float endSlope, int distance)

{

int xStart = (int) Math.Floor(origin.X + 0.5 – (startSlope * distance));

int xEnd = (int)Math.Floor(origin.X + 0.5 – (endSlope * distance));

int yCheck = origin.Y – distance;

bool createdNewScan = false;

for(int xCheck = xStart; xCheck <= xEnd; xCheck++)

{

Point currentLocation = new Point(xCheck, yCheck);

SetAsVisible(map, currentLocation);

if (LosIsBlocked(map, currentLocation))

{

ScanNorthwestToNorth(map, origin, maxRadius, startSlope, InverseSlope(GetCenterCoordinate(origin), PointF.Add(currentLocation, new SizeF(-0.0000001f, 0.9999999f))), distance + 1);

createdNewScan = true;

}

else

{

createdNewScan = false;

}

}

if (!createdNewScan) ScanNorthwestToNorth(map, origin, maxRadius, startSlope, endSlope, distance + 1);

}

In the above code I’ve added a check to see if the LOS was blocked for the current location. If the tile blocks our LOS we create a new scan using a new end slope calculated as discussed above. The line after we create the new scan sets a boolean flag createdNewScan to true. This allows us to control the creation of a new scan at the end of the loop in order to avoid unnecessary scans.

2. Leaving obstacles

The second obstacle type occurs when we leave a tile that was blocking the LOS and enter a non-obstructing tile. In this case we need to adjust the start slope of our next scan. The following diagram illustrates this behaviour. In the above diagram our scan origin is at the point (3,3). We start the scan process as normal by visiting positions (2, 2) and (3, 2). The next scan then starts with position (1, 1) which is immediately blocked. Since this is the first position in the scan we don’t start a new scan as before. Instead, we continue along the row and find that position (2, 1) also blocks LOS. We take no action and continue along the row. When we reach position (3, 1) we find that our LOS is no longer blocked. Now we adjust our start slope so that the scan on the next row will start at position (2, 0) and stop at position (3, 0).

The new start slope is calculated using the point that brushes past the top right corner of the blocking tile as our end point and the origin of the scan as our start point.

Using our slope formula we calculate our new end slope as (1 – 3.5) / (3 – 3.5) = 5 but this is not enough. Inverting the slope gives us 1 / 5 = 0.2 as our end slope.

Our starting x value for the row at position 0 (distance = 3) can therefore be calculated as (3.5 – (0.2 * 3) = 2.9 = 2. The end x value can similarly be calculated using our new end slope as (3.5 – (0 * 3)) = 3.5 = 3.

Lets write a test that will illustrate this behaviour.

[TestMethod]

public void TestScanNorthwestToNorthLeavingObstacle()

{

Map map = new Map(3, 3, TileType.Empty);

// Create test scenario

//   012

//

// 0 s..

// 1  #.

// 2   @

map[1, 1] = TileBuilder.BuildTile(TileType.Rock);

fov.ScanNorthwestToNorth(map, new Point(2, 2), 2);

Assert.IsFalse(fov.VisibleLocations.Contains(new Point(0, 0)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(1, 0)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(2, 0)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(1, 1)));

Assert.IsTrue(fov.VisibleLocations.Contains(new Point(2, 1)));

}

In the above test we set up our map with an obstable at position (1, 1). We then perform our scan of the NotherwestToNorth octant and test to ensure that all the tiles are visible except the tile at position (0, 0).

I run the test and it fails as expected. Lets write some code to make the test pass.

private void ScanNorthwestToNorth(Map map, Point origin, int maxRadius, float startSlope, float endSlope, int distance)

{

int xStart = (int) Math.Floor(origin.X + 0.5 – (startSlope * distance));

int xEnd = (int)Math.Floor(origin.X + 0.5 – (endSlope * distance));

int yCheck = origin.Y – distance;

Point currentLocation = new Point(xStart, yCheck);

SetAsVisible(map, currentLocation);

bool prevLocationWasBlocked = LosIsBlocked(map, currentLocation);

for(int xCheck = xStart + 1; xCheck <= xEnd; xCheck++)

{

currentLocation = new Point(xCheck, yCheck);

SetAsVisible(map, currentLocation);

if (LosIsBlocked(map, currentLocation))

{

if (!prevLocationWasBlocked) ScanNorthwestToNorth(map, origin, maxRadius, startSlope, InverseSlope(GetCenterCoordinate(origin), PointF.Add(currentLocation, new SizeF(-0.0000001f, 0.9999999f))), distance + 1);

prevLocationWasBlocked = true;

}

else

{

if (prevLocationWasBlocked) startSlope = InverseSlope(GetCenterCoordinate(origin), currentLocation);

prevLocationWasBlocked = false;

}

}

if (!prevLocationWasBlocked) ScanNorthwestToNorth(map, origin, maxRadius, startSlope, endSlope, distance + 1);

}

The first thing I did was to remove scanning the first location from the loop. The reason for this is so that we don’t start a new scan if the first location blocks the LOS.

Our loop now starts at the second location along the row. The next change was in the case when a location blocks the LOS. Previously we just started a new scan using a new end slope. I added an additional condition that we only start a new scan if the previous tile didn’t block the LOS.

The last change was for the case when a tile does not block LOS. We now do a test to see if the previous tile blocked the LOS. If it did we need to adjust our start slope using the caclulation as discussed above.

I recompile the code and all our tests still run fine. We can now handle all combinations of obstructions in the Northwest to North octant.

Why Octants?

Björn’s article immediately talks about breaking the field of view into octants. Fair enough, but I needed to know why. Here follows the best explanation I could come up with.

Breaking the FOV up into octants allow us to make some simplifications to the tile processing logic. This only becomes obvious (ok to me it did) once you actually investigate the properties of each octant.

The Northwest to North octant has the following properties. The y values are determined by our distance from the origin. The starting x value is determined by the slope of a the Northwest line and the initial ending x value is the same as the origin x value. Slope calculations are performed using inverse slope. Scans are performed row by row.

The North to Northeast octant has the following properties. The y values are determined by the distance from the origin. The initial starting x value is the same as the origin x value. The ending x value is calculated using the slope of the Northeast line. Slope calculations are performed using inverse slope. Scans are performed row by row.

The Northeast to East octant has the following properties. The x values are determined by the distance from the origin. The starting y value is calculated using the slope of the Northeast line. The the initial ending y value is the same as the origin y value. Slope calculations are performed using normal slope. Scans are performed column by column.

The East to Southeast octant has the following properties. The x values are determined by the distance from the origin. The initial starting y value is the same as the origin y value. The ending y value is calculated using the slope of the Southeast line. Slope calculations are performed using normal slope. Scans are performed column by column.

The other four octants are basically mirror images of the first and won’t be discussed any further (unless requested).

Conclusion

Well that should be all you need to know to implement your own version of recursive shadow casting. I only handled the Northwest to North octant in detail. The other octants are very similar except for the properties listed above. I will be posting a full implementation of all the octants on codeplex shortly.

Let me know if you have any comments or suggestions.