roguelike tutorial 08: vision, line of sight, and field of view

It doesn't feel like we're exploring much since we see the whole level from the beginning. Ideally we can only see our immediate surroundings and remember what we've already seen. I think we can do that in one session.

The first thing we need is a way to determine if something is in our line of sight. To do this we get all the points in between us and what we want to look at and see if any of them block our vision. For this, we can create a new Line class that uses Bresenham's line algorithm to find all the points along the line.

package rltut;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Line {
    private List<Point> points;
    public List<Point> getPoints() { return points; }

    public Line(int x0, int y0, int x1, int y1) {
        points = new ArrayList<Point>();
    
        int dx = Math.abs(x1-x0);
        int dy = Math.abs(y1-y0);
    
        int sx = x0 < x1 ? 1 : -1;
        int sy = y0 < y1 ? 1 : -1;
        int err = dx-dy;
    
        while (true){
            points.add(new Point(x0, y0, 0));
        
            if (x0==x1 && y0==y1)
                break;
        
            int e2 = err * 2;
            if (e2 > -dx) {
                err -= dy;
                x0 += sx;
            }
            if (e2 < dx){
                err += dx;
                y0 += sy;
            }
        }
    }
}

If you look this all the work is done in the constructor - that's a bad sign. So says Misko Hevery of Google fame, Martian Feathers of Working Effectively With Legacy Code, and anyone who's had to deal with this before. On the other hand, it doesn't do that much work; it just creates a list of points. The points are value objects and the line itself could be a value object. I'm certainly no fan of constructors that initialize their collaborators but this seems like a special case. Since it's just a personal project and no one's life or money are on the line, I'll try it and see if it becomes a problem.

To make things a tiny bit more convenient to loop through the points in a line, we can make the class implement Iterable<Point>. All we have to do is declare that the Line implements Iterable<Point> and add the following method:

public Iterator<Point> iterator() {
        return points.iterator();
    }

I have a feeling that we will use this Line class a lot as we add more features.

---

Since creatures are the ones who are doing the seeing, it makes since to give creatures a new stat to say how far they can see and a couple methods for looking at the world.

private int visionRadius;
    public int visionRadius() { return visionRadius; }

    public boolean canSee(int wx, int wy, int wz){
        return ai.canSee(wx, wy, wz);
    }

    public Tile tile(int wx, int wy, int wz) {
        return world.tile(wx, wy, wz);
    }

I set the vision radius to 9 in the creature's constructor but you should use whatever value you prefer or even have it passed in from the creatureFactory. Since we delegate the task to seeing to the CreatureAi, that's where the work is done and what we'll add to next.

public boolean canSee(int wx, int wy, int wz) {
        if (creature.z != wz)
            return false;
    
        if ((creature.x-wx)*(creature.x-wx) + (creature.y-wy)*(creature.y-wy) > creature.visionRadius()*creature.visionRadius())
            return false;
    
        for (Point p : new Line(creature.x, creature.y, wx, wy)){
            if (creature.tile(p.x, p.y, wz).isGround() || p.x == wx && p.y == wy)
                continue;
        
            return false;
        }
    
        return true;
    }

Now that our player can see his immediate surroundings, we should update the PlayScreen to only show the monsters and tiles that can be seen. Tiles outside the line of sight are shown in dark grey.

private void displayTiles(AsciiPanel terminal, int left, int top) {
     for (int x = 0; x < screenWidth; x++){
         for (int y = 0; y < screenHeight; y++){
             int wx = x + left;
             int wy = y + top;

             if (player.canSee(wx, wy, player.z)){
                 Creature creature = world.creature(wx, wy, player.z);
                 if (creature != null)
                     terminal.write(creature.glyph(), creature.x - left, creature.y - top, creature.color());
                 else
                     terminal.write(world.glyph(wx, wy, player.z), x, y, world.color(wx, wy, player.z));
             } else {
                 terminal.write(world.glyph(wx, wy, player.z), x, y, Color.darkGray);
             }
         }
     }
 }

Try it. You should see tiles outside of the player's range in a dark grey color.

---

We need a place to store what tiles the user has seen but who tracks what's been seen? It's part of the GUI so maybe the PlayScreen? But it's heavely based on the map so maybe the World class should flag tiles that have been seen — many games do this so maybe we should too? But the Creature is the one seeing so maybe it should. But we want the player to record this, the other monsters don't need to so maybe the CreatureAi should track what the creature has seen? That last one seems right to me; the PlayerAi should track what the player has seen and the PlayScreen should use that info to determines what get's displayed. This also means that we can store what tile the player saw at each location so what the player remembers may be different than what is in the real world. So if there's a cave in, or tunnels are dug, or some other change in the world then the player will remember what was last seen and be quite surprised when returning to that area. Neat posiblities.

We need a new tile to indicate a place that has not been seen. This is similar to the out of bounds tile we have since it's not really part of the world but it makes things much easier.

UNKNOWN(' ', AsciiPanel.white)

There are several different ways of determining what is in the player's field of view this but the simplest, and therefore what I prefer, is called raycasting. It's exactly what we're already doing: draw a line from the viewer to the tile in question to see if anything is blocking the vision. Raycasting is probably the slowest way, but it's quick enough and I think has the best overall look. Other methods perform differently when columns and doorways are involved.

Let's create a new class for our field of view. We can slightly extend the common definition of ours to not only determine what is in view but to remember what has already been seen too. What's visible now and what was seen earlier are technically two different things and possibly should be implemented by two different classes, but they're close enough and we can change it later if necessary.

package rltut;

public class FieldOfView {
    private World world;
    private int depth;

    private boolean[][] visible;
    public boolean isVisible(int x, int y, int z){
        return z == depth && x >= 0 && y >= 0 && x < visible.length && y < visible[0].length && visible[x][y];
    }

    private Tile[][][] tiles;
    public Tile tile(int x, int y, int z){
        return tiles[x][y][z];
    }

    public FieldOfView(World world){
        this.world = world;
        this.visible = new boolean[world.width()][world.height()];
        this.tiles = new Tile[world.width()][world.height()][world.depth()];
    
        for (int x = 0; x < world.width(); x++){
            for (int y = 0; y < world.height(); y++){
                for (int z = 0; z < world.depth(); z++){
                    tiles[x][y][z] = Tile.UNKNOWN;
                }
            }
        }
    }
}

That seems like a good interface. We can ask if a tile is visible and we can ask what tile was last seen somewhere. We just need to add the method to update what's visible and has been seen.

public void update(int wx, int wy, int wz, int r){
        depth = wz;
        visible = new boolean[world.width()][world.height()];
    
        for (int x = -r; x < r; x++){
            for (int y = -r; y < r; y++){
                if (x*x + y*y > r*r)
                    continue;
         
                if (wx + x < 0 || wx + x >= world.width() 
                 || wy + y < 0 || wy + y >= world.height())
                    continue;
         
                for (Point p : new Line(wx, wy, wx + x, wy + y)){
                    Tile tile = world.tile(p.x, p.y, wz);
                    visible[p.x][p.y] = true;
                    tiles[p.x][p.y][wz] = tile;
             
                    if (!tile.isGround())
                        break;
                }
            }
        }
    }

Only the player is going to use this advanced field of view, all other creatures can use the default line of sight code. Add a FieldOfView variable to the PlayerAi and override the canSee method.

public boolean canSee(int wx, int wy, int wz) {
    return fov.isVisible(wx, wy, wz);
}

Since the FieldOfView requires a world to be passed in the constructor and we don't want the ai's to know about the world, we can build the FieldOfView elseware and rely on constructor injection to give it to the PlayerAi. This means it will have to be passed into the CreatureFactory from the PlayScreen too.

The PlayScreen should construct a new field of view once the world has been made and pass it to the CreatureFactory. Since the PlayScreen is also responsible for displaying the world to the user, we should keep a reference to the field of view. Then we can update it before displaying the world and rely on it for tiles outside of the player's view. After that, we just need to modify the displayTiles method.

private void displayTiles(AsciiPanel terminal, int left, int top) {
        fov.update(player.x, player.y, player.z, player.visionRadius());
    
        for (int x = 0; x < screenWidth; x++){
         for (int y = 0; y < screenHeight; y++){
             int wx = x + left;
             int wy = y + top;

             if (player.canSee(wx, wy, player.z)){
                 Creature creature = world.creature(wx, wy, player.z);
                 if (creature != null)
                     terminal.write(creature.glyph(), creature.x - left, creature.y - top, creature.color());
                 else
                     terminal.write(world.glyph(wx, wy, player.z), x, y, world.color(wx, wy, player.z));
                 else
                     terminal.write(fov.tile(wx, wy, player.z).glyph(), x, y, Color.darkGray);
             }
        }
    }
}

And there you go, line of sight and field of view. These caves are starting to feel like real caves. If only they had some more monsters....

---

I just remembered something I wanted to do with the world once we added creatures. Replace the glyph and color methods with these:

public char glyph(int x, int y, int z){
    Creature creature = creature(x, y, z);
    return creature != null ? creature.glyph() : tile(x, y, z).glyph();
}

public Color color(int x, int y, int z){
    Creature creature = creature(x, y, z);
    return creature != null ? creature.color() : tile(x, y, z).color();
}

Since the world takes care of that for us, the PlayScreen becomes simpler.

private void displayTiles(AsciiPanel terminal, int left, int top) {
    fov.update(player.x, player.y, player.z, player.visionRadius());
    
    for (int x = 0; x < screenWidth; x++){
        for (int y = 0; y < screenHeight; y++){
            int wx = x + left;
            int wy = y + top;

            if (player.canSee(wx, wy, player.z))
                terminal.write(world.glyph(wx, wy, player.z), x, y, world.color(wx, wy, player.z));
            else
                terminal.write(fov.tile(wx, wy, player.z).glyph(), x, y, Color.darkGray);
        }
    }
}

---

Instead of having doAction notify everyone nearby, it should only notify them if they can see the one doing the action.

public void doAction(String message, Object ... params){
    int r = 9;
    for (int ox = -r; ox < r+1; ox++){
        for (int oy = -r; oy < r+1; oy++){
            if (ox*ox + oy*oy > r*r)
                continue;
         
            Creature other = world.creature(x+ox, y+oy, z);
         
            if (other == null)
                continue;
         
            if (other == this)
                other.notify("You " + message + ".", params);
            else if (other.canSee(x, y, z))
                other.notify(String.format("The %s %s.", name, makeSecondPerson(message)), params);
         }
    }
}

Now you have to actually see something happen in order to be notified about it.

download the code