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.

Advertisements

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.

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.

Generating Random Dungeons (part 10)

Introduction

In part 9 of the Generating Random Dungeons article series we implemented the functionality to meet the requirements of step 11 and 12 of the random dungeon generation algorithm.

The requirement was to create random sized rooms and place them within the dungeon. To achieve this we added quite a lot of additional functionality. For instance, we added a new Room class which is very similar to the Map class in its structure and meaning.

In this article I will look at refactoring the Map and Room classes to reduce duplicate code. I hope to also handle placing doors in our rooms and, if there is time, to convert the Map structure from cells to tiles.

Refactoring

Below is a class diagram representation of our current Map and Room classes.

DomainModel1

We can see some commonality in the fields and properties of both the Map and Room classes. To me a Room is also a Map, albeit a special type of Map. I would not just want to inherit Room from Map in its current form as I’d be inheriting a bunch of unnecessary properties and methods used for Dungeon generation. And I guess that’s the key. We need another class that is based on a Map, but encapsulates the functionality for handling dungeon generation.

My first refactoring is therefore renaming the Map class to Dungeon and having the Dungeon class inherit from a new Map class that encapsulates the functionality for working with the Map data structure. The new class diagram is as follows.

DomainModel2 

Our new Map abstract class provides us with functionality to manage the Map data structure. Both Rooms and Dungeons are made up of cells in a rectangular shape and have bounds that need to be checked.

The Room class now only has functionality needed for room creation and placement while the Dungeon class only has functionality needed for creating a dungeon. I find the new structure a bit easier to work with, while the class name Dungeon adds a bit more meaning to what we’re actually trying to achieve.

I added a new CellLocations property which is similar to the old DeadEndCellLocations property on the Dungeon class.  Instead of returning only dead-end cell locations, this IEnumerable will return every location in our Map. The benefit is improved ease of use when having to enumerate each location within a map. Instead of having to write

            for (int x = 0; x < map.Width; x++)

                for (int y = 0; y < map.Height; y++)

we can now enumerate all the locations within our map using the following code.

            foreach (Point cellLocation in dungeon.CellLocations)

I implemented another change to the Map class so that the Map constructor properly initializes our 2-dimensional cell array. In the past the MarkCellsUnvisited and InitializeRoomCells methods performed this function, but I didn’t like the way you could instantiate the Dungeon and Room classes into an invalid state.

I renamed a few of the methods from “Mark” to “Flag” cell as visited. I felt it to be a bit more consistent with the language we’re using within our algorithm.

You will notice that I removed the room placement and scoring functionality from the Dungeon class. I felt that this was a function of Room creation and that the Dungeon class should not be making such decisions.

Just like we have a Dungeon Generator we should also have a Room Generator. The results of these classes should be Dungeons and Rooms respectively. In lieu of this I refactored the Generator class into a more explicit DungeonGenerator class and moved the room creation functionality into a new RoomGenerator class as seen below.

DomainModel3

Our DugeonGenerator is now initialized with the various parameters (these can also be changed via the properties). We offload the room generation functionality through the new RoomGenerator class which is passed to the DungeonGenerator as a parameter.

Our new RoomGenerator class is now responsible for creating and placing rooms. In the future we could possible swap out various RoomGenerators if we wanted to change the way we perform this part of the algorithm. The same holds for our DungeonGenerator class.

While moving the room placement code I found a potential bug. When we create a room we initialize the room with empty cells and cells with walls on the sides of the room boundaries. The problem comes when we place the room by copying the SideTypes of each cell to the map. By copying the SideTypes we aren’t ensuring that the cells adjacent to the room have side of SideType.Wall. The new PlaceRoom code is now as follows.

        public void PlaceRoom(Point location, Room room, Dungeon dungeon)

        {

            // Offset the room origin to the new location

            room.SetLocation(location);

 

            // Loop for each cell in the room

            foreach (Point roomLocation in room.CellLocations)

            {

                // Translate the room cell location to its location in the dungeon

                Point dungeonLocation = new Point(location.X + roomLocation.X, location.Y + roomLocation.Y);

                dungeon[dungeonLocation].NorthSide = room[roomLocation].NorthSide;

                dungeon[dungeonLocation].SouthSide = room[roomLocation].SouthSide;

                dungeon[dungeonLocation].WestSide = room[roomLocation].WestSide;

                dungeon[dungeonLocation].EastSide = room[roomLocation].EastSide;

 

                // Create room walls on map (either side of the wall)

                if ((roomLocation.X == 0) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.West))) dungeon.CreateWall(dungeonLocation, DirectionType.West);

                if ((roomLocation.X == room.Width – 1) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.East))) dungeon.CreateWall(dungeonLocation, DirectionType.East);

                if ((roomLocation.Y == 0) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.North))) dungeon.CreateWall(dungeonLocation, DirectionType.North);

                if ((roomLocation.Y == room.Height – 1) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.South))) dungeon.CreateWall(dungeonLocation, DirectionType.South);

            }

 

            dungeon.AddRoom(room);

        }

The updated PlaceRoom method now includes a step where it uses the CreateWall method to create a wall between the adjacent cells around the room borders.

The above refactoring process resulted in major structural changes to our code base. Fortunately we have a good set of unit tests and I was able to make these changes without any major headaches. Now we can look at adding doors to our dungeon.

Algorithm Step 13

For every place where the room is adjacent to a corridor or a room, add a door. (If you don’t want doors everywhere, add another parameter that determines when a door should be placed, and when an empty doorway [i.e. archway, etc.] should be placed).

For step 13 we need to determine if a room cell has a corridor cell adjacent to it. Obviously we should only evaluate the cells on the boundaries of our room i.e. the cells with walls. Our AdjacentCellInDirectionIsCorridor method on the Dungeon class will give us exactly what we need to meet this requirement.

Next we need some functionality to create a door. We already have two similar methods called CreateWall and CreateCorridor. We can create a similar method called CreateDoor to create our doorways. Let’s write a test to demonstrate this functionality.

        [Test]

        public void TestCreateDoorBetweenAdjacentCells()

        {

            Dungeon dungeon = new Dungeon(10, 10);

 

            // We now have map filled with rock.

            // Test creating doors in each direction

            dungeon.CreateDoor(new Point(0, 0), DirectionType.South);

 

            Assert.IsTrue(dungeon[0, 0].NorthSide == SideType.Wall);

            Assert.IsTrue(dungeon[0, 0].SouthSide == SideType.Door);

            Assert.IsTrue(dungeon[0, 0].WestSide == SideType.Wall);

            Assert.IsTrue(dungeon[0, 0].EastSide == SideType.Wall);

 

            Assert.IsTrue(dungeon[0, 1].NorthSide == SideType.Door);

            Assert.IsTrue(dungeon[0, 1].SouthSide == SideType.Wall);

            Assert.IsTrue(dungeon[0, 1].WestSide == SideType.Wall);

            Assert.IsTrue(dungeon[0, 1].EastSide == SideType.Wall);

 

        }

The above test makes use of a new CreateDoor method on the Dungeon class to create a Door on the South side at location (0, 0). We perform a test for this checking that the South side at (0,0) and the North side at (0, 1) are now of type SideType.Door. I excluded the other directions from this code listing (they are available in the source code download).

The code to make this test compile is as follows.

        public Point CreateDoor(Point location, DirectionType direction)

        {

            return CreateSide(location, direction, SideType.Door);

        }

The CreateDoor method is very simple. All I needed to add was the new “Door” SideType. I compile and run the test with no problems.

        [Test]

        public void TestCanPlaceDoors()

        {

            RoomGenerator roomGenerator = new RoomGenerator();

            Dungeon dungeon = new Dungeon(3, 3);

 

            // Create corridors in + shape

            Point location = new Point(1, 1);

            dungeon.CreateCorridor(location, DirectionType.North);

            dungeon.CreateCorridor(location, DirectionType.South);

            dungeon.CreateCorridor(location, DirectionType.West);

            dungeon.CreateCorridor(location, DirectionType.East);

 

            // Create and place room

            Room room = new Room(1, 1);

            room.InitializeRoomCells();

            roomGenerator.PlaceRoom(location, room, dungeon);

 

            roomGenerator.PlaceDoors(dungeon);

 

            Assert.AreEqual(SideType.Door, dungeon[1, 0].SouthSide);

            Assert.AreEqual(SideType.Door, dungeon[0, 1].EastSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].NorthSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].SouthSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].WestSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].EastSide);

            Assert.AreEqual(SideType.Door, dungeon[2, 1].WestSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 2].NorthSide);

        }

In the above test we initialize a small Dungeon and place a 1×1 room in the middle. We create corridors leading from this room in all four directions. We then call a new PlaceDoors method on the RoomGenerator class and pass in our dungeon. The test then asserts that each of the room walls have a doorway in them.

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

        public void PlaceDoors(Dungeon dungeon)

        {

            foreach (Room room in dungeon.Rooms)

            {

                foreach (Point cellLocation in room.CellLocations)

                {

                    // Translate the room cell location to its location in the dungeon

                    Point dungeonLocation = new Point(room.Bounds.X + cellLocation.X, room.Bounds.Y + cellLocation.Y);

 

                    // Check if we are on the west boundary of our room

                    // and if there is a corridor to the west

                    if ((cellLocation.X == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.West)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.West);

 

                    // Check if we are on the east boundary of our room

                    // and if there is a corridor to the east

                    if ((cellLocation.X == room.Width – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.East)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.East);

 

                    // Check if we are on the north boundary of our room

                    // and if there is a corridor to the north

                    if ((cellLocation.Y == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.North)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.North);

 

                    // Check if we are on the south boundary of our room

                    // and if there is a corridor to the south

                    if ((cellLocation.Y == room.Height – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.South)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.South);

                }

            }

        }

The CreateDoors method above is not very sophisticated. All it does is loop through each room in the dungeon and then for each room it checks every cell. It first checks if the cell lies on any of the boundaries of the room and then uses the AdjacentCellInDirectionIsCorridor method to check if there is a corridor cell in the given direction.

If the above conditions are true it creates a door in the direction provided. This implementation will create a doorway for every cell that is adjacent to a corridor even if it means that every cell on the boundary of a room will have a door. I recompile the test and it fails.

After some debugging I see that my test case produced a funny result. The test dungeon places a small 1×1 room in the middle of the ‘+’ shape. The new PlaceRoom method now creates a wall between the adjacent outside sides. This is that our definition of a corridor is determined by the number of walls a cell has. Our small 1×1 corridors are being counted as “rock” because they each have 4 walls.

I change the IsCorridor property on the Cell class to an explicit property rather than a calculated result. I updated the CreateCorridor method to explicitly set the IsCorridor property to true and the SparsifyMaze method to set the IsCorridor property to false when it removes a corridor.

I rerun the unit tests and they all pass.

Below is a screen shot of our dungeon generator using the new PlaceDoors functionality.

exampleoutput1

Our new door placement algorithm is definitely creating doors! Too bad the dungeon now looks terrible. The author doesn’t give much leading on how to place doors in his version of the algorithm. I think we can improve our current implementation by only placing one doorway per room wall as follows.

        public void PlaceDoors(Dungeon dungeon)

        {

            foreach (Room room in dungeon.Rooms)

            {

                bool hasNorthDoor = false;

                bool hasSouthDoor = false;

                bool hasWestDoor = false;

                bool hasEastDoor = false;

 

                foreach (Point cellLocation in room.CellLocations)

                {

                    // Translate the room cell location to its location in the dungeon

                    Point dungeonLocation = new Point(room.Bounds.X + cellLocation.X, room.Bounds.Y + cellLocation.Y);

 

                    // Check if we are on the west boundary of our room

                    // and if there is a corridor to the west

                    if ((cellLocation.X == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.West)) &&

                        (!hasWestDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.West);

                        hasWestDoor = true;

                    }

 

                    // Check if we are on the east boundary of our room

                    // and if there is a corridor to the east

                    if ((cellLocation.X == room.Width – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.East)) &&

                        (!hasEastDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.East);

                        hasEastDoor = true;

                    }

 

                    // Check if we are on the north boundary of our room

                    // and if there is a corridor to the north

                    if ((cellLocation.Y == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.North)) &&

                        (!hasNorthDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.North);

                        hasNorthDoor = true;

                    }

 

 

                    // Check if we are on the south boundary of our room

                    // and if there is a corridor to the south

                    if ((cellLocation.Y == room.Height – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.South)) &&

                        (!hasSouthDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.South);

                        hasSouthDoor = true;

                    }

 

                }

            }

        }

The new PlaceDoors method above keeps track of a Boolean flag for each side of the room. It will only place a door on a particular side if no doors have been placed previously. The new output can be seen in the following screen shot.

exampleoutput2

The new output is much better and looks like something to go adventuring in. This is of course still very basic and we could add additional functionality to create archways, secret doors, etc.

The next step is to convert our dungeon into a tile-based representation.

Converting to tiles

Our current cell-based dungeon representation is unsuitable for tile-based games such as roguelikes. The reason for this is that tiles normally only represent one feature of a dungeon i.e. a wall is only a wall, a door is only a door. In our current cell-based structure one cell represents four sides and can’t be displayed using a tile-based algorithm.

To convert to a tile-based structure we need to “expand” our cells into tiles, with each tile only holding one piece of information. This means that each side will be represented by a separate tile. For this process we are only interested in non-rock cells i.e. corridor or room cells.

We can represent our tiles as a 2-dimensional array of integer values. The specific values for rock, wall, floor and door can be any value we choose. For the moment I will use 0 for rock, 1 for corridor and 2 for doors. [Edit: I updated this to a Enum called TileType after an anonymous comment. I didn’t want to use the Enum originally as I wanted to decouple code using the dungeon generator from having to use my Enum. Still not sure if its a good idea, but when I’ve finished my roguelike I’ll write a post about it.]

The following test illustrates the functionality required to convert our cell-based structure to tiles.

        [Test]

        public void TestExpandWithCorridorTiles()

        {

            RoomGenerator roomGenerator = new RoomGenerator();

            Dungeon dungeon = new Dungeon(4, 4);

 

            dungeon.CreateCorridor(new Point(2, 1), DirectionType.North);

            dungeon.CreateCorridor(new Point(1, 2), DirectionType.South);

            dungeon.CreateCorridor(new Point(1, 1), DirectionType.West);

            dungeon.CreateCorridor(new Point(2, 2), DirectionType.East);

 

            // Create and place room

            Room room = new Room(2, 2);

            room.InitializeRoomCells();

            roomGenerator.PlaceRoom(new Point(1, 1), room, dungeon);

 

            int[,] dungeonTiles = DungeonGenerator.ExpandToTiles(dungeon);

 

            // Assert the dimensions are correct

            Assert.AreEqual(dungeon.Width * 2 + 1, dungeonTiles.GetUpperBound(0) + 1);

            Assert.AreEqual(dungeon.Height * 2 + 1, dungeonTiles.GetUpperBound(1) + 1);

 

            // Assert tiles were expanded correctly

            for(int x = 0; x < dungeon.Width * 2 + 1; x++)

            {

                for(int y = 0; y < dungeon.Height * 2 + 1; y++)

                {

                    if (((x == 5) & (y == 1)) ||

                    ((x == 1) & (y == 3)) ||

                    ((x == 3) & (y == 3)) ||

                    ((x == 4) & (y == 3)) ||

                    ((x == 5) & (y == 3)) ||

                    ((x == 3) & (y == 4)) ||

                    ((x == 4) & (y == 4)) ||

                    ((x == 5) & (y == 4)) ||

                    ((x == 3) & (y == 5)) ||

                    ((x == 4) & (y == 5)) ||

                    ((x == 5) & (y == 5)) ||

                    ((x == 7) & (y == 5)) ||

                    ((x == 3) & (y == 7))

                        )

                        Assert.IsTrue(dungeonTiles[x, y] == (int)TileType.Empty);

                    else

                        Assert.IsTrue(dungeonTiles[x, y] == (int)TileType.Rock);

                }

            }

        }

In the above test we create a small 4×4 dungeon with a 2×2 room in the middle. We then create a corridor in each direction from each corner of the room. We then invoke a new method on the DungeonGenerator class called ExpandToTiles. This method takes a Dungeon instance as input parameter and returns a 2-dimensional array of integer values representing the tiles.

Our test then asserts that the 2-dimensional array is twice the size + 1 of the dungeon in width and height. The reason for this is that there will always be a ring of rock around the dungeon and a tile for each of the sides are shared between the dungeon cells.

The test then loops through each value in the expanded array and tests to see if the value is either rock, corridor or a door. The above test is only testing walls and corridors. I have included a test for doors in the source code download.

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

        public static int[, ] ExpandToTiles(Dungeon dungeon)

        {

            // Instantiate our tile array

            int[, ] tiles = new int[dungeon.Width * 2 + 1, dungeon.Height * 2 + 1];

 

            // Initialize the tile array to rock

            for (int x = 0; x < dungeon.Width * 2 + 1; x++)

                for (int y = 0; y < dungeon.Height * 2 + 1; y++)

                    tiles[x, y] = (int)TileType.Rock;

 

            // Fill tiles with corridor values for each room in dungeon

            foreach (Room room in dungeon.Rooms)

            {

                // Get the room min and max location in tile coordinates

                Point minPoint = new Point(room.Bounds.Location.X * 2 + 1, room.Bounds.Location.Y * 2 + 1);

                Point maxPoint = new Point(room.Bounds.Right * 2, room.Bounds.Bottom * 2 );

 

                // Fill the room in tile space with an empty value

                for (int i = minPoint.X; i < maxPoint.X; i++)

                    for (int j = minPoint.Y; j < maxPoint.Y; j++)

                        tiles[i, j] = (int)TileType.Empty;

            }

 

            // Loop for each corridor cell and expand it

            foreach (Point cellLocation in dungeon.CorridorCellLocations)

            {

                Point tileLocation = new Point(cellLocation.X*2 + 1, cellLocation.Y*2 + 1);

                tiles[tileLocation.X, tileLocation.Y] = (int)TileType.Empty;

 

                if (dungeon[cellLocation].NorthSide == SideType.Empty) tiles[tileLocation.X, tileLocation.Y – 1] = (int)TileType.Empty;

                if (dungeon[cellLocation].NorthSide == SideType.Door) tiles[tileLocation.X, tileLocation.Y – 1] = (int)TileType.Door;

 

                if (dungeon[cellLocation].SouthSide == SideType.Empty) tiles[tileLocation.X, tileLocation.Y + 1] = (int)TileType.Empty;

                if (dungeon[cellLocation].SouthSide == SideType.Door) tiles[tileLocation.X, tileLocation.Y + 1] = (int)TileType.Door;

 

                if (dungeon[cellLocation].WestSide == SideType.Empty) tiles[tileLocation.X – 1, tileLocation.Y] = (int)TileType.Empty;

                if (dungeon[cellLocation].WestSide == SideType.Door) tiles[tileLocation.X – 1, tileLocation.Y] = (int)TileType.Door;

 

                if (dungeon[cellLocation].EastSide == SideType.Empty) tiles[tileLocation.X + 1, tileLocation.Y] = (int)TileType.Empty;

                if (dungeon[cellLocation].EastSide == SideType.Door) tiles[tileLocation.X + 1, tileLocation.Y] = (int)TileType.Door;

            }

 

            return tiles;

        }

The above ExpandToTiles method instantiates a new 2-dimensional array to the size of our dungeon.Width * 2 + 1 and dungeon.Height * 2 +1. It then loops through each position in the array and sets the value to zero (or rock).

Next the method loops through every map in the dungeon and fills the corresponding tile are with empty tiles.

Next the method loops through every “corridor” cell location in the dungeon. At every location it checks each side to determine if its empty or a door and fills the adjacent tile with appropriate TileType. I compile and run the unit tests and they pass with no problems. Our new tile-based output now looks as follows.

exampleoutput3 

In the above screen shot I made use of the ‘+’ character to indicate doors and the ‘.’ character is the floor area.

Conclusion

In part 10 of the Generating Random Dungeons article series we started by refactoring our code by creating a new Map super class and renaming the old Map class to Dungeon. We also cleaned up some of the naming conventions and moved the Room generation and placement functionality into a new RoomGenerator class.

Next we implemented functionality to add doors to our rooms. This functionality was implemented using a very basic algorithm. A lot more can be added to make door placement a bit more intelligent (or maybe meaningful). I feel that the current implementation, however, is good enough as a prototype.

After that we converted the cell-based dungeon to a tile-based representation. The tile-based representation is important if you’re going to be using the random dungeons to create tile-based games such as roguelikes.

This part concludes the series on Generating Random Dungeons. I hope you all enjoyed it and learnt something through the process. I know I did.