FOV Using Recursive Shadow Casting in c#

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.

image

The slope of a line can be calculated using the following formula :

image

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.

image

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.

image

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.

Directions Evolved

Jonathon Duerig recently posted the following comment on the Some New Direction article.

I really like this idea and was inspired to put this in my own project. However, I’m stumped on how to put in relations between into it. I want to be flexible enough for algorithms based on the directions to be able to use four-way, eight-way, up and down, etc. kinds of directions without modification.

I also want to work with directions in terms of a relationships between them. I want to be able to find the next direction clockwise of a given direction, for instance. Or choose a random direction perpendicular to a given direction. Or find the direction opposite of a given direction.

Having a flexible interface to setup these relationships at startup is proving difficult. Ideas?

-D

I rambled off an initial response without actually thinking about the problem and why he needed this functionality. I started thinking about his request and realised that it would be quite useful. Hence this blog post.

I am going to deal with the relationships between directions first. Lets say we would like to find the next clockwise direction. The test for this functionality looks as follows.

        [TestMethod]

        public void TestNextDirection()

        {

            Assert.AreEqual(Direction.Northeast, Direction.North.Next);

            Assert.AreEqual(Direction.East, Direction.Northeast.Next);

            Assert.AreEqual(Direction.Southeast, Direction.East.Next);

            Assert.AreEqual(Direction.South, Direction.Southeast.Next);

            Assert.AreEqual(Direction.Southwest, Direction.South.Next);

            Assert.AreEqual(Direction.West, Direction.Southwest.Next);

            Assert.AreEqual(Direction.Northwest, Direction.West.Next);

            Assert.AreEqual(Direction.North, Direction.Northwest.Next);

        }

In the above test we make use of the new “Next” property on the Direction class. The idea is that the “Next” property returns the next clockwise direction based on our current direction.

The code that makes the above test compile is as follows.

        /// <summary>

        /// The next clockwise direction of the current direction

        /// </summary>

        public Direction Next

        {

            get

            {

                switch (Name)

                {

                    case “North”:

                        return Direction.Northeast;

                    case “Northeast”:

                        return Direction.East;

                    case “East”:

                        return Direction.Southeast;

                    case “Southeast”:

                        return Direction.South;

                    case “South”:

                        return Direction.Southwest;

                    case “Southwest”:

                        return Direction.West;

                    case “West”:

                        return Direction.Northwest;

                    case “Northwest”:

                        return Direction.North;

                    default:

                        throw new InvalidOperationException();

                }

            }

        }

In the above listing we hardcode the next clockwise direction for the current direction using a simple case statement. I compile the code and rerun the test. It passes with no issues.

I won’t cover the implementation for the other relationships between directions as they are almost identical to the one above. The additional properties I added are “Previous”, “NextPerpendicular” and “PreviousPerpendicular”. The “Previous” property returns the next anti-clockwise direction. The “NextPerpendicular” and “PreviousPerpendicular” properties return the next clockwise and anti-clockwise perpendicular directions respectively.

The class diagram for the direction class is now as follows.

Direction class diagram

The next part of the functionality he required was to be able to limit the number of directions available. In my initial response I recommended a helper class such as the DirectionPicker class I used in my DungeonGeneration article series.

In order to support working with different combinations of directions we need to modify the DirectionPicker class to use a list of available directions for all its operations.

The current implementation picks a random direction (previously only the main compass directions north, east, south and west) and adds it to a list of directions picked. By specifying a list of available directions we can implement the same functionality by removing the direction picked from the provided available directions.

The random direction is now selected by choosing a random index within the list of available directions. This allows us to select random directions in any combination as specified by the available directions.

The code affected by these changes can be seen below (the original code has been commented out)

       public bool HasDirectionToPick

        {

            get

            {

                return directionsAvailable.Count > 0;

                //return directionsPicked.Count < 4;

            }

        }

 

        private bool MustChangeDirection

        {

            get

            {

                // changeDirectionModifier of 100 will always change direction

                // value of 0 will never change direction

                return ((directionWasPicked) || (changeDirectionModifier > RogueLib.Common.Random.Instance.Next(0, 99)));

                //return ((directionsPicked.Count > 0) || (changeDirectionModifier > RogueLib.Common.Random.Instance.Next(0, 99)));

            }

        }

 

        private Direction PickDifferentRandomDirection()

        {

            Direction directionPicked;

            do

            {

                directionPicked = directionsAvailable[RogueLib.Common.Random.Instance.Next(directionsAvailable.Count – 1)];

                //directionPicked = directionsAvailable[RogueLib.Common.Random.Instance.Next(3)];

            } while ((directionPicked == previousDirection) && (directionsAvailable.Count > 1));

            //} while ((directionPicked == previousDirection) && (directionsPicked.Count < 3));

 

            return directionPicked;

        }

 

        public Direction PickRandomDirection()

        {

            if (!HasDirectionToPick) throw new InvalidOperationException(“No directions available”);

 

            Direction directionPicked;

 

            do

            {

                directionPicked = MustChangeDirection ? PickDifferentRandomDirection() : previousDirection;

            } while (!directionsAvailable.Contains(directionPicked));

            //} while (directionsPicked.Contains(directionPicked));

 

            directionsAvailable.Remove(directionPicked);

            //directionsPicked.Add(directionPicked);

 

            directionWasPicked = true;

            return directionPicked;

        }

I created three constructors to allow me to easily configure the available directions for the DirectionPicker. The default constructor makes use of the main compass directions (north, east, south, west) as was the default behaviour before we made the above changes.

The second constructor takes a DirectionsAvailableType enum as input parameter and sets up the available directions based on the provided DirectionsAvailableType. The two available types are AllCompassDirections and MainCompassDirections.

The third constructor takes a params array of Directions as input parameter whereby the user can specify a custom list of available directions. I would use this constructor to satisfy Jonathon’s requirement of selecting a random perpendicular direction to a given direction for example.

        [TestMethod]

        public void TestSelectionOfRandomPerpendicularDirection()

        {

            Direction currentDirection = Direction.North;

            DirectionPicker directionPicker = new DirectionPicker(Direction.North, 100, currentDirection.PreviousPerpendicular, currentDirection.NextPerpendicular);

            List<Direction> directionsPicked = new List<Direction>();

            directionsPicked.Add(directionPicker.PickRandomDirection());

            directionsPicked.Add(directionPicker.PickRandomDirection());

 

            Assert.IsTrue(directionsPicked.Contains(currentDirection.PreviousPerpendicular));

            Assert.IsTrue(directionsPicked.Contains(currentDirection.NextPerpendicular));

            Assert.IsFalse(directionPicker.HasDirectionToPick);

        }

In the above test we instantiate our direction picker with the previous (West) and next (East) perpendicular directions from our current direction (North). We then instantiate a new list that will contain the directions picked and then proceed to pick two random directions. The test then asserts that both the perpendicular directions were indeed selected and that there are no more directions available for selection.

The above improvements to the Direction and DirectionPicker classes have added great flexibility to our Direction handling code. Any suggestions or comments would, as always, be appreciated.

Towards a Roguelike Framework

Its been a long time since my last post, but real life and Dota got the better of me. Fortunately I deleted Dota for the 3rd time, I just can’t stop playing that game without deleting it, and now I can carry on with some game development.

I have been playing around with field of view algorithms and settled on using recursive shadow casting for now. I got my little @ running around in the random dungeons having terrain light up as I go.

Next I started working on a framework for a roguelike. My goal has always been to design a framework so that I could easily swap out dungeon generation, FOV, and display targets i.e. console vs graphics.

This is of course easier said than done. I find it difficult to make such design decisions in the framework without the knowledge of what it would actually take to implement a specific feature in reality. And I don’t want to implement a set of features using a flawed design. (Of course no design is ever perfect.) Damn the need for perfect architecture without perfect knowledge.

My current game loop makes use of the GOF strategy pattern instead of a switch statement. I’m hoping to encapsulate each game state such as Welcome, Character Generation, Town and Dungeon into a different strategy implementation. The game loop will then just defer to the active strategy to do some processing, pass the strategy to the active renderer to produce the output and then retrieve the user intput from the active input handler and pass it on to the active strategy.

Input is quite easy to abstract as its just a mapping of the active input handler for example the .NET console to some form of generic command that can be passed to the active game strategy for processing. The game strategy/state then receives the input as a generic command for example ChangeDirection and acts upon it. This command could have come from the Keyboard, Mouse, GameController or even different key strokes in case the user customized the keyboard to command mappings.

Rendering has proven to be a bit more difficult. Firstly, the .NET console support is really limited. The amount of colours supported is very limited (this can be overcome by making some win32 API calls) and its just plain clumsy. I am also uncertain of what game information should be available to the renderer and whether it should be a completely generic implementation (per render target) or a specific implementation per render target per game strategy/state.

I started off with a generic implementation using a console render target and quickly found it to be lacking. I am currently playing around with a graphic library to see what it would take to convert the game information to graphical representation. The idea is that the experience of both styles of output will give me enough information to do a more general design that supports both cases.

That’s enough rambling for now. Any comments and suggestions would be most welcome.