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.

Advertisements

One thought on “A Circular FOV

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s