# Check out the lighting demo

I just finished porting my lighting code from the Microsoft XNA framework to SDL.NET. You can now download a cross-platform version from CodePlex.

This release includes a working demo showing off some coloured lights and their effect on the player’s FOV.

Use normal directional keys or the numeric keypad to navigate the custom map.
Press space to generate a new random dungeon.

To run this demo you will either need the .NET Framework 3.5 for Windows or Mono 1.9 for anything else.

Check out these links to get Mono and for instructions on how to use it.

Any comments on the demo and experiences on getting it to work on non-windows machines would be great.

Advertisements

# Adding some lights

I always liked the idea of having a more dynamic lighting model. My thought was that monsters and rooms should have their own light sources (not just the player). I realised that I could use my field of view (FOV) implementation to determine light values for tiles around a light source.

Using the FOV code from the previous articles I was able to simulate which tiles were lit around a specific light source. This was cool, but I also wanted to simulate light attenuation. This means that the light intensity decreases as it moves away from the light source. There are various ways to calculate this, one is the inverse square law. For my implementation I made use of a general inverse quadratic function listed below.

f(d) = 1 / (a0 + (a1 * d) + (a2 * d2))

My current implementation uses a0 = 1, a1 = 0.3 and a2 = 0. The following screen shot shows the light source around the player using the above formula to adjust the light intensity values. The next step was to add additional lights to the dungeon. This called for a rethink of my drawing routines. I came up with a layered approach.

• Draw the architecture (the dungeon)
• Draw the actors (right now only the player)
• Apply lighting to the scene.

I already had the first two steps working quite nicely, but I needed some way to take care of the lighting.

To solve this I created a new LightMap class that would handle the required processing.The LightMap class processes all the static lights in the scene and caches the results. For every render pass I recalculate all the dynamic lights (player light source) and store their values in the LightMap. For overlapping lights I made use of a simple additive algorithm to add the light values.

After rendering the scene I perform an additive alphablend of the LightMap values to produce a result as shown below. The screen shot above shows a square room with four static lights, one in each corner. I specified a different colour for each light just to show that its possible.

My FOV is currently set to a radius of 10 around the player. The player can, however, only see tiles that are lit by light sources. That’s why there’s a black area in between the player light and the four lights in the corners. I have no idea how this plays in a real game, but for now I’m happy with the aesthetics.

# Introduction

The FOV calculated using the recursive shadow casting algorithm (using the default implementation) forms a square shape around the player. This square FOV allows for an equal viewing distance in all the major directions. Unfortunately I find it a bit ugly and distracting as illustrated in the screen shot below. The effect is even more exaggerated when the player is moving around the dungeon.

I realised that I needed some way of producing a rounded FOV and thought that using a circle for trim the edges of the FOV would be a great idea.

# Implementing a Circular FOV

My algorithm to implement a circular FOV is as follows.

1. For each scan line along a particular axis.
2. Determine the minimum or maximum value (depending on the scan direction) by using the standard form equation of a circle.
3. Limit the scan start and end values to fall within the circle min and max values.

I reused my unit tests from my recursive shadow casting implementation and changed them to reflect the expected values based on a circular FOV.

[TestMethod]

public void TestScanNorthwestToNorthLeavingObstacle()

{

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

// Create test scenario

//   012

//

// 0 ii.

// 1  #.

// 2   @

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

var fov = new ShadowCastingFov {FovShape = FovShapeType.Circle};

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

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

Assert.IsFalse(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 unit test I denoted locations excluded by the circle equation with the “i” character. Lets check out the code that will make the above test pass.

private static int CalculateRadius(int circleRadius, int positionOnAxis)

{

return (int)Math.Round(Math.Sqrt((circleRadius * circleRadius) – (positionOnAxis * positionOnAxis)), 0);

}

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

{

if (distance > maxRadius) return;

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

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

int yCheck = origin.Y – distance;

if (FovShape == FovShapeType.Circle)

{

int xRadius = origin.X – CalculateRadius(maxRadius, distance);

if (xStart < xRadius) xStart = xRadius;

if (xStart > xEnd) return;

}

var 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);

}

In the above code I added a new method called CalculateRadius. This method takes the maxRadius (our maximum viewing distance) and the distance (our current viewing distance) parameters and calculates the corresponding value on the x-axis.

After I calculate the start and end values for the scan line along the x-axis. I check to see if I need to constrain these values to a circular FOV. I determine the x-coordinate given the y-coordinate (distance) and radius of the circle. If the scan line start falls outside the circle then I set the start value to that of the circle x-coordinate.

The less-than check might seem wrong, but remember that our coordinate system is switched around, we are counting up from 0 to the player location along the x-axis.

The check if the scan line start is greater-than the scan line end is there to handle the case where our scan line end was shifted outside the bounds of the circle due to earlier obstructions.

Applying the above code to all the other octants yields a circular FOV as shown below. The screen shot above shows the FOV constrained to a circle. Its definitely better than the square FOV, but not quite what I expected. Playing around with different viewing distances I found the “pointy” blocks along the main axes to be distracting. I needed something extra to create a smoothed circular FOV.

I posted the problem on the rogue-like developer forums and the consensus was to make use of a octagon FOV. Great, but Googling the equation for a octagon proved to be a bit more challenging.

# Implementing a Rounded-Square FOV

I then got the bright idea that I needed a square with rounded edges. I already had a square implementation and a circle implementation. I was sure that I could use one of these to get to the desired result.

All I needed was to smooth out the “pointy” section at the outer parts of the FOV. That is, where the current distance is equal to the FOV max radius.

Using some graph paper I came up with the smoothing out formula. I would add (radius / 2) tiles to the left and the right of the tile along the x and y axes. The following test shows the new allowed and ignored tiles.

[TestMethod]

public void TestScanNorthwestToNorthLeavingObstacle()

{

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

// Create test scenario

//   012

//

// 0 i..

// 1  #.

// 2   @

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

var fov = new ShadowCastingFov();

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 previous example both locations (0; 0) and (1; 0) where ignored. With the rounded square FOV I only expect location (0; 0) to be ignored. (It would have been in shadow anyway).

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

if ((FovShape == FovShapeType.Circle) || (FovShape == FovShapeType.RoundedSquare))

{

int xRadius;

if ((FovShape == FovShapeType.RoundedSquare) && (distance == maxRadius))

xRadius = origin.X – (maxRadius / 2);

else

xRadius = origin.X – CalculateRadius(maxRadius, distance);

if (xStart < xRadius) xStart = xRadius;

if (xStart > xEnd) return;

}

The above code snippet replaces the change I added when I implemented the circular FOV. This new code accepts both Circle and RoundedSquare Fov shape types. And everything is the same except in the case when we’re dealing with the distance equal to the maximum Fov distance. In this case we limit the x-coordinate along the circle to the max radius divided by two.

Simple enough. The new Rounded-Square Fov now looks as follows. In my opinion, a far more pleasing result, without any added complexity.

The source code for this Fov implementation can be found on CodePlex.

# 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.

# Shadow casting

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]

public void TestScanNorthwestToNorthIsLimitedToMaxRadius()

{

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

// Create test scenario

//   012

//

// 0 …

// 1  ..

// 2   @

ShadowCastingFov fov = new ShadowCastingFov();

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)

{

if (distance > maxRadius) return;

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)

{

if (map.Bounds.Contains(location)) visibleLocations.Add(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);

ShadowCastingFov fov = new ShadowCastingFov();

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)

{

if (distance > maxRadius) return;

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);

ShadowCastingFov fov = new ShadowCastingFov();

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)

{

if (distance > maxRadius) return;

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.