Tuesday, September 13, 2011

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

18 comments:

  1. Wow!
    Field of view! Must try it :D

    ReplyDelete
  2. FOV seems daunting but if you do something simple like raycasting, it's actually pretty simple.

    ReplyDelete
  3. Hello, I've been following the tutorial step by step (it's fantastic!), but I found that the play screen wasn't visualized as I think it should do. I thought I would have made a mistake somewhere, so I decided to download the code of this tutorial #05 and try it. But the result has been the same (here is a screenshot: https://plus.google.com/photos/107350882738141757827/albums/5705686106623958001?authkey=CJ6-4Li8sbLl7wE). Something's wrong, isn't it?

    I'm using Ubuntu 11.10 and this is the output of "java -version" command:
    java version "1.6.0_26"
    Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
    Java HotSpot(TM) Server VM (build 20.1-b02, mixed mode)

    I'll appreciate any tip you can give me.

    ReplyDelete
  4. I've just been glancing at AsciiPanel.java. I wonder if the issue (my play screen is displayed in blue scale) is in setColors() method. I'm not sure at all, however. I don't understand what is doing that method.

    ReplyDelete
    Replies
    1. A couple other people have had problems with how things look when running Ubuntu. The setColors() method creates the lookup table that maps the original black and white pixels to the background color and foreground color. I'm not sure why that would only affect Ubuntu users. Maybe it's interpreting the colors as BGR format instead of RGB? I'll look into it.

      Delete
    2. Hello again! I've found a library that can be used in place of AsciiPanel and works really fine (even in my Ubuntu computer): https://github.com/SquidPony/SquidGrid
      So, now I can continue with the tutorial!

      Delete
    3. I think the color problems have been fixed in AsciiPanel - it was actually a bug in the Linux implementation of java that AsciiPanel has to work around. I'll update the references when I can but you can get the code now at https://github.com/trystan/AsciiPanel

      Delete
    4. I was having the exact same problem (I also use ubuntu) but after updating AsciiPanel it works perfectly. Thank you!

      Delete
    5. My AsciiPanel didn't actually end up working the way I needed it to, but it's OK - I wrote my own that replaces functionality. In any case, this tutorial is great even without it, just an extra challenge for me:P

      Delete
  5. Thank you one more time. I'll look for it.

    ReplyDelete
  6. I think there's an error in your Bresenham:

    > if (e2 > -dx) ...

    should be

    > if (e2 > -dy) ...

    If I'm not mistaken.

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. For some reason my code is displaying the world as perpetually grey unless I'm within 3-4 squares of the far left side. I opened up the demo code and it's doing the same thing. Surely this isn't intended though?

    Any ideas?

    ReplyDelete
    Replies
    1. Found my problem. In the method

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

      I had return.ai.canSee(wz, wy, wz);

      Switched the wx to a wz. Tiny errors like that are so frustrating... thanks for the amazing tutorial. I hope I can be as proficient with programming java myself someday. This is a great too to get me there.

      Delete
  9. To my point of view that's what I call a good article! Do you this domain for private aims only or you basically use it to get profit from it?

    ReplyDelete
  10. My doAction is a bit different than yours. The way you have it, if a creature has a visionRadius higher than 9, they won't be able to see an action if they stand, say, 10 squares away. I got rid of the r variable in doAction and instead had it loop over every square in that layer, broadcasting to any creatures within a range defined by their own visionRadius. It's not noticeably slower and I think it's better balanced.

    ReplyDelete
  11. Its been pretty necessary for the students to understand in detail all those possible values which are indeed said to be of utmost importance and the value.

    ReplyDelete