Health and Damage

To keep combat simple all attacks are successful. The only thing I customize is an actor’s health and damage. My actor class is really simple at the moment and has the bare minimum to implement the original requirements.

    9     public interface IActor

   10     {

   11         /// <summary>

   12         /// The amount of life force

   13         /// </summary>

   14         int Health { get; set; }

   15         /// <summary>

   16         /// The amount of life force an attack does

   17         /// </summary>

   18         int Damage { get; set; }

   19         /// <summary>

   20         /// The rate at which the actor does stuff

   21         /// </summary>

   22         int Speed { get; set; }

   23         /// <summary>

   24         /// Is true while health is greater than zero

   25         /// </summary>

   26         bool IsAlive { get; }

   27         /// <summary>

   28         /// The intelligence controlling this actor (AI or Human)

   29         /// </summary>

   30         IIntellect Intellect { get; set; }

   31     }

So far we’ve used the IsAlive, Speed and Intellect properties to implement death, actor turns and actions performed during a turn. To simulate combat I implemented the following test.

   14         [Test]

   15         public void TestAttackSubtractsAttackerDamageFromDefenderHealth()

   16         {

   17             var attacker = new Actor() {Damage = 1, Health = 10};

   18             var defender = new Actor() {Damage = 1, Health = 10};

   19 

   20             var command = new AttackCommand(attacker, defender);

   21 

   22             Assert.IsTrue(command.Execute());

   23             Assert.AreEqual(9, defender.Health);

   24             Assert.AreEqual(10, attacker.Health);

   25         }

In the above test I create two actors, one attacker and one defender. I then execute an AttackCommand and verify that the attacker damage is subtracted from the defender’s health.

The next step is to put it all together.

The Endgame

The game will end if any of the following conditions ever become true

  1. All the monsters are dead
  2. The player is dead

An actor is dead when it’s life has been reduced to zero or less. In order to implement the above I had to give some thought to the game loop and how the player and monsters would fit into the game.  I came up with the following unit test to describe the behaviour I was looking for.

   10         [Test]

   11         public void TestGameEndsWhenAllMonstersAreDead()

   12         {

   13             // Create a new game instance

   14             var game = new Game();

   15             // Initialize the game with a player actor and a few dead monsters

   16             game.Initialize(new Actor {HitPoints = 10},

   17                             new List<IActor>

   18                                 {

   19                                     new Actor {HitPoints = 0},

   20                                     new Actor {HitPoints = 0}

   21                                 });

   22 

   23             // Process a game turn

   24             game.ProcessTurn();

   25             // Assert that the game has ended

   26             Assert.IsFalse(game.IsActive);

   27         }

In the above test I create a new instance of my game and initialize it with a live player and some dead monsters. I foresee this initialization step to happen when we start our game, or load an existing game or maybe when changing levels. For now I’m keeping it simple.

I then foresee the game loop to keep processing turns while the game is active. Of course this will include things like rendering and reacting to player input, but I’m not worried about this right now.

The ProcessTurn method is responsible for checking if the monsters are all dead and then setting the IsActive flag to false.

The following test verifies that the game ends when the player dies.

   29         [Test]

   30         public void TestGameEndsWhenThePlayerIsDead()

   31         {

   32             // Create a new game instance

   33             var game = new Game();

   34             // Initialize the game with a dead player actor and a live monster

   35             game.Initialize(new Actor {HitPoints = 0},

   36                             new List<IActor>

   37                                 {

   38                                     new Actor {HitPoints = 5}

   39                                 });

   40             // Process a game turn

   41             game.ProcessTurn();

   42             // Assert that the game has ended

   43             Assert.IsFalse(game.IsActive);

   44         }

This test is exactly the same as before except that the player is dead and the monster alive. No real rocket science. I added the following test to make sure that the game is in fact active when both the player and at least one monster is alive.

   46         [Test]

   47         public void TestGameIsActiveWhenThePlayerIsAliveAndAMonsterIsAlive()

   48         {

   49             // Create a new game instance

   50             var game = new Game();

   51             // Initialize the game with a live player actor, a live monster,

   52             // and a dead monster

   53             game.Initialize(new Actor {HitPoints = 10},

   54                             new List<IActor>

   55                                 {

   56                                     new Actor {HitPoints = 5},

   57                                     new Actor {HitPoints = 0}

   58                                 });

   59             // Process a game turn

   60             game.ProcessTurn();

   61             // Assert that the game has ended

   62             Assert.IsTrue(game.IsActive);

   63         }

This test initializes the game with a live player and monster and a dead monster (just to mix things up a bit).

I feel the above tests have given me enough functionality to satisfy my end game requirements. I am going to have to do some work on the ProcessTurn method to implement actors taking turns and checking that dead actors don’t get a chance to act. So far I’m happy with the design (I haven’t had to make any major changes to implement a feature yet). I do have a lot of thoughts on new features I’d like to implement, but I’m trying to be really disciplined on keeping to my original scope.

The speed system

My speed system will have the following characteristics:

  • All actors (who are able) should have at least one turn per game turn.
  • Faster actors should take their turns before slower actors.
  • If Bob is twice as fast as Fred then Bob should have two turns per Fred’s one turn.
  • The game turn ends when all actors have had at least one turn.

To implement the above features I came up with the following unit tests. For all the unit tests I create a GameTurn object that is initialized with two identical actors. Each of these actors have a speed of 1 be default.

The GameTurn class is responsible for implementing the speed system features. In order for me to test the functionality I let the ProcessTurn method return a list of GameEvents completed during the turn. The GameEvent class holds information such as the actor, the action and the time interval at which a turn took place.

   50         // Every actor should have at least one turn per game turn

   51         [Test]

   52         public void TestEachActorHadLeastOneTurn()

   53         {

   54             var actions = gameTurn.ProcessTurn();

   55 

   56             Assert.IsTrue(actions.Any(x => x.Actor == actor1));

   57             Assert.IsTrue(actions.Any(x => x.Actor == actor2));

   58         }

In the above test I process the game turn and check that each actor has performed at least one action. The implementation for the above test is fairly trivial. We just loop through each of the actors and add their next action to a list and return it when we’re done.

   60         // Actors take their turns in sequence based on their speed

   61         [Test]

   62         public void TestEachActorTakesHisTurnInOrder()

   63         {

   64             actor1.Speed = 2;

   65             actor2.Speed = 3;

   66 

   67             var actions = gameTurn.ProcessTurn();

   68 

   69             Assert.IsTrue(actions[0].Actor == actor1);

   70             Assert.IsTrue(actions[1].Actor == actor2);

   71         }

In the above test I make sure that each actor is processed in the correct sequence. The sequence is determined by the actor speed. Lower speed values are processed before higher speed values. The implementation for the above test makes use of a priority queue that is keyed to the actor speed. The ProcessTurn method now asks the priority queue for the next actor until all the actors have had their turn.

   73         // The slowest actor should only act once per game turn

   74         [Test]

   75         public void TestSlowestActorHadOneTurn()

   76         {

   77             actor2.Speed = 2;

   78 

   79             var actions = gameTurn.ProcessTurn();

   80 

   81             Assert.AreEqual(1, actions.Count(x => x.Actor == actor2));

   82         }

In the above test we make sure that the slowest actor has only one turn. The game turn must end when the slowest actor has completed its turn. To implement this feature I evaluate the list of actions that have already been completed before processing the next actor. I stop processing actors when all the actors have had their turn.

   84         // The actor with half the speed should act twice per turn

   85         [Test]

   86         public void TestHalfSpeedActorHadTwoTurns()

   87         {

   88             actor2.Speed = 2;

   89 

   90             var actions = gameTurn.ProcessTurn();

   91 

   92             Assert.AreEqual(2, actions.Count(x => x.Actor == actor1));

   93             Assert.AreEqual(1, actions.Count(x => x.Actor == actor2));

   94         }

In the above test we make sure that actor1 had two turns while actor2 only had one turn. My first pass of the test failed with unexpected results. Each actor only completed one turn even though actor1 with twice the speed of actor2 was in the priority queue. The reason for the failure was that check that everyone had completed their turn was true even though actor1 had not completed it’s second turn. To solve this I added an additional check that the game turn would only end if the last actor had completed it’s turn and all other actors to act at the same time had completed theirs.

The final ProcessTurn method is implemented as follows.

   19         public IList<GameEvent> ProcessTurn()

   20         {

   21             var completedActions = new List<GameEvent>();

   22 

   23             InitializeCommandQueue();

   24 

   25             var lastTimeSlice = -1;

   26 

   27             // We process the command queue while there are actors to process

   28             while (commandQueue.Count > 0)

   29             {

   30                 // Get the next actor to process

   31                 var nextTimeInterval = commandQueue.Peek();

   32 

   33                 // stop processing if everyone has had a turn and we’re on a new time slice

   34                 if ((AllActorsHaveActed(completedActions))

   35                     && (lastTimeSlice != nextTimeInterval.Key))

   36                     break;

   37 

   38                 // Update the last time slice to the current time slice

   39                 lastTimeSlice = nextTimeInterval.Key;

   40 

   41                 // Remove dead actors from the queue

   42                 if (!nextTimeInterval.Value.IsAlive)

   43                 {

   44                     commandQueue.Dequeue();

   45                     continue;

   46                 }

   47 

   48                 // Get the next action from the actor

   49                 ICommand nextAction = nextTimeInterval.Value.GetNextAction();

   50                 if ((nextAction != null) && (nextAction.Execute()))

   51                 {

   52                     // Remove the actor from the queue if the action was successful

   53                     commandQueue.Dequeue();

   54                     // Add the successful command to the list of completed actions

   55                     completedActions.Add(new GameEvent

   56                         {   Actor = nextTimeInterval.Value,

   57                             Command = nextAction,

   58                             TimeSlice = nextTimeInterval.Key

   59                         });

   60                     // Add the actor to the queue incrementing the priority with the speed

   61                     commandQueue.Enqueue(

   62                         nextTimeInterval.Key + nextTimeInterval.Value.Speed,

   63                         nextTimeInterval.Value);

   64                 }

   65                 else

   66                     // We stop processing actions for this game loop cycle as

   67                     // the last action was unsuccessful

   68                     break;

   69             }

   70 

   71             return completedActions;

   72         }

A Circular FOV

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.

SquareFov

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.

CircleFov

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.

RoundedSquareFov

In my opinion, a far more pleasing result, without any added complexity.

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

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.