Custom Field-Of-View

27 03 2015

While working on a rogue-like project I’m not quite ready to announce, the need arose for a customized grid-based FoV solution. In particular, one that would permit fractional opacity values. In this blog post I aim to outline the solution I found, and open it up for discussion.

First, some requirements. The FoV would be used for an overworld map with a height-map element and varried terrain types. While this means there will be few if any elements that totally block the player’s view, there are some I want to obscure it. For example, the player should be able to see farther over an open plain or the ocean than they can into a dense forest or over rolling hills.

Representation

I intend to codify the information for this feature in two numbers, opacity, and visibility. Both will fall between zero (0) and one (1).

Opacity will be set once at startup on a per-tile (or per-tile-type) basis, and will determine how badly the tile obscures the player’s vision. It will be based on factors such as height (possibly relative height in a later iteration, adding the necessity to recalculate these values), and the type of terrain. A dense forest might use 0.4 while an open plain might have a zero (0).

Visibility is calculated each frame, and is defined as one (1) minus the sum of the opacity values of all tiles between it and the player. An opacity of one (1) means the tile is completely blocked. A visibility of zero (0) means the tile is completely obscured from where the player is standing, while a visibility of one (1) means the tile is perfectly visible. A factor of the distance between the player and the tile is also be subtracted to simulate fog.

The Algorithm

While considering how best to design my own solution I realized each tile only needed to consider the closest tile in a direct line from the tile in question to the player. If it was aware of the visibility and opacity of that tile, it could calculate its own visibility from that information. For such a system to work the algorithm would have to consider the tiles closer to the player first, and then work its way outward. As such, the algorithm I’ve designed first considers the eight (8) tiles surrounding the player, then the tiles surrounding those, and expands outwards from there.


Diagram 1 – Order in which tiles are checked. Zero (0) represents the player.
Tiles labeled with a one (1) are checked first, then two (2), and so on.

When considering a given tile, and assuming the tiles between it and the player have already been considered, the next step is to determine which tile would be next in a line drawn from it to the player. In my current iteration I’m using Atan2() to give me an angle, and checking which of the eight (8) forty-five (45) degree wedges that angle falls into. Something based on the slope would likely be faster, as it wouldn’t involve calling a trigonometric function.

Once I know what that inner tile is, the visibility of this tile is set to be the visibility of the inner tile minus the opacity of the inner tile. This is done instead of using the opacity of the current tile to allow tiles with an opacity of one (1) to still be visible. When considering a tile diagonally, the opacity to add is multiplied by 1.4f, a rough approximation of the square root of two (2), to give the effect of a more circular view.

The Code

The project I’m building makes use of the Libtcod library for input and rendering, as well as a few other features. In this particular section of the code base you will see me reference a TCODConsole class, and call methods on it which place characters and strings onto a console. I also adjust the foreground colors using the TCODColor class and an Interpolate method which blends them. Finally, there is a hand-written Vector2 class used to track positions.

At the moment I’m building the system in a test scene; the scene interface in this project contains methods explaining how to update each tick, how to render, and how to respond to input. Here I’m specifying a location for the player, a list of locations for the walls, and a temporary location for use later in the algorithm, pre-allocated for performance. Angle is also being pre-allocated for later. Range determines how far out the FoV algorithm will look, and fog is as explained earlier. Visibility and opacity are 2D float arrays used to store the values defined earlier.

public class TestScene  : IScene {
    private Vector2 player, temp;
    private float angle
    private int range = 100;
    private float fog;
    private float[,] visibility;
    private float[,] opacity;
    private List<Vector2> walls;
}

The constructor is fairly self-explanatory. I’m setting the player’s position and creating the arrays, and setting the opacity based on the presence of the walls I define.

public TestScene() {
    player = new Vector2(20, 20);
    fog = 0.1f;
    visibility = new float[Game.Settings.ScreenWidth, Game.Settings.ScreenHeight];
    opacity = new float[Game.Settings.ScreenWidth, Game.Settings.ScreenHeight];
    walls = new List<Vector2>();
    walls.Add(new Vector2(10, 10));
    walls.Add(new Vector2(11, 10));
    walls.Add(new Vector2(11, 11));

    for (int x = 0; x < Game.Settings.ScreenWidth; ++x) {
        for (int y = 0; y < Game.Settings.ScreenHeight; ++y) {
            opacity[x, y] = 0.0f;
            if (walls.Any(w => (int)w.X == x && (int)w.Y == y)) {
                opacity[x, y] = 1.0f;
            }
        }
    }
}

Inside the update method I clear the visibility array with zeros (0), save at the player’s location, which starts at one (1) so that the player can always see where they’re standing.

public void Update(float deltaTime) {
    for (int x = 0; x < Game.Settings.ScreenWidth; ++x) {
        for (int y = 0; y < Game.Settings.ScreenHeight; ++y) {
            visibility[x, y] = 0;
            if (x == (int)player.X && y == (int)player.Y) {
                visibility[x, y] = 1;
            }
        }
    }
}

The render method draws the FoV at increasing ranges, then layers the player and walls over them. I’m doing this because the visibility is rendered as arrows pointing at the square they came from, with a color based on visibility. Ideally the system wouldn’t “render” the FoV at all, but would instead simply darken less visible tiles.

public void Render(TCODConsole console) {
    for (int i = 1; i <= range; ++i) {
        RenderFovAtRange(console, player, i);
    }
    foreach (var wall in walls) {
        console.putChar((int)wall.X, (int)wall.Y, "#");
    }
    console.putChar((int)player.X, (int)player.Y, "X");
}

After this I have some code in place to handle input and allow the player to move around and adjust the range of the FoV algorithm. I’m testing it in a 50×50 area, so the range of 100 is more than enough to cover all of it.

The next block of code, RenderFovAtRange(), loops through all the tiles in a square at the defined distance from a center point. The corners are handled afterwards at the end, as they would otherwise be calculated twice. This isn’t problematic in the current version, but if I were to later add multiple sources for theFoV (as might happen to simulate lights) the addition would cause problems.

private void RenderFovAtRange(TCODConsole console, Vector2 source, int range) {
    Vector2 coords = new Vector2();
    for (int x = -range + 1; x <= range - 1; ++x) {
        coords.X = (int)source.X + x;
        coords.Y = (int)source.Y - range;
        PutFovArrow(console, source, coords);
        coords.Y = (int)source.Y + range;
        PutFovArrow(console, source, coords);
    }
    for (int y = -range + 1; y <= range - 1; ++y) {
        coords.X = (int)source.X - range;
        coords.Y = (int)source.Y + y;
        PutFovArrow(console, source, coords);
        coords.X = (int)source.X + range;
        PutFovArrow(console, source, coords);
    }
    coords.X = (int)source.X - range; coords.Y = (int)source.Y - range;
    PutFovArrow(console, source, coords);
    coords.Y = (int)source.Y + range;
    PutFovArrow(console, source, coords);
    coords.X = (int)source.X + range; coords.Y = (int)source.Y - range;
    PutFovArrow(console, source, coords);
    coords.Y = (int)source.Y + range;
    PutFovArrow(console, source, coords);
}

Finally, for each tile it considers the above method calls PutFovArrow(). Each call to this method considers where the tile is in respect to the source, determines the next closest tile, calculates the visibility, and draws an arrow pointing at the tile it referenced with a color based on the visibility it calculated. In final form it will likely do no drawing at all, instead just filling the visibility array for later use when rendering.

private void PutFovArrow(TCODConsole console, Vector2 source, Vector2 pos) {
    // No point checking if we're outside the bounds of the map anyways.
    if(pos.X < 0 || pos.X >= Game.Settings.ScreenWidth ||
        pos.Y < 0 || pos.Y >= Game.Settings.ScreenHeight) {
            return;
    }

    temp = source - pos;
    temp.Normalize();
    angle = 180.0f + (float)(Math.Atan2(temp.Y, temp.X) * (180.0 / Math.PI));
    if (angle >= 360.0f) angle -= 360.0f;

    char c = '?';
    float op = 0.0f,
            vis = 0.0f;
    if (angle != float.NaN) {
        if (angle > 337.5f || angle <= 22.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X - 1, (int)pos.Y]);
            vis = Math.Max(0.0f, visibility[(int)pos.X - 1, (int)pos.Y] - op);
            c = (char)TCODSpecialCharacter.ArrowWest;
        } else if (angle > 22.5f && angle <= 67.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X - 1, (int)pos.Y - 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X - 1, (int)pos.Y - 1] - op);
            c = (char)TCODSpecialCharacter.NW;
        } else if (angle > 67.5f && angle <= 112.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X, (int)pos.Y - 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X, (int)pos.Y - 1] - op);
            c = (char)TCODSpecialCharacter.ArrowNorth;
        } else if (angle > 112.5f && angle <= 157.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X + 1, (int)pos.Y - 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X + 1, (int)pos.Y - 1] - op);
            c = (char)TCODSpecialCharacter.NE;
        } else if (angle > 157.5f && angle <= 202.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X + 1, (int)pos.Y]);
            vis = Math.Max(0.0f, visibility[(int)pos.X + 1, (int)pos.Y] - op);
            c = (char)TCODSpecialCharacter.ArrowEast;
        } else if (angle > 202.5f && angle <= 247.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X + 1, (int)pos.Y + 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X + 1, (int)pos.Y + 1] - op);
            c = (char)TCODSpecialCharacter.SE;
        } else if (angle > 247.5f && angle <= 292.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X, (int)pos.Y + 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X, (int)pos.Y + 1] - op);
            c = (char)TCODSpecialCharacter.ArrowSouth;
        } else if (angle > 292.5f && angle <= 337.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X - 1, (int)pos.Y + 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X - 1, (int)pos.Y + 1] - op);
            c = (char)TCODSpecialCharacter.SW;
        }
    }
    visibility[(int)pos.X, (int)pos.Y] = vis;
    console.setForegroundColor(TCODColor.Interpolate(TCODColor.black, TCODColor.white, vis));
    console.putChar((int)pos.X, (int)pos.Y, c);
    console.setForegroundColor(TCODColor.white);
}

The Result

When I walk next to the walls I get a view like this:


Diagram 2 – View with wall opacity of one (1)

If I go into the code and alter the walls to have an opacity of 0.3 instead of one (1) I get:


Diagram 3 – View with wall opacity of 0.3
Advertisements

Actions

Information

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




%d bloggers like this: