Simulating "line of sight" with obstacles on 2d grid?

Question

Ran into an interesting problem. I need to figure out how to simulate line of sight - simple enough, just on a 2d grid with obstacles. Either a grid cell is visible, or it's not.

I can get something really rudimentary going - like spreading n spaces from player, or blocking horizontal propagation when an adjacent obstacle is detected, but I can't let myself live with it. Plenty of other apps are using more sophisticated methods that slope the line of sight around corners etc, and I want to be up to par.

So far DCSS has been my source of inspiration when I'm stumped, I'm hoping to get something close to what they have: http://crawl.s-z.org/.

Any insight would be appreciated - thanks for the help!

(Forgive if this is embarassingly noobish - only started game dev a few weeks ago, trying hard to catch up.)

Answer 1

Ray casting is a very fast and efficient way to determine line-of-sight. It basically involves sending a ray (think of it like an infinite laser that can't be redirected) from a certain position in a certain direction. Using this ray, you can determine things like which point(s) it intersects and how far away from the origin it was when it crossed a certain point.

So for example, in a player/enemy scenario, the ray could originate from the enemy with the direction being the location of the player. If the ray collides with a solid tile, the enemy can't see the player. If it doesn't, the enemy can see the player.

Here is an excellent tutorial that will should help.

You can also consider Bresenham's line algorithm (summed up, it creates lines) for something that might be more easily scaled to tiles.

Answer 2

I have blogged code to compute line of sight from a height-map. A simple flat map with obstacles is just a very flat height-map, and this implementation is still completely applicable.

Here it is in C++ and its O(n); if you know the maximum height in the map, you can track a scanline that has no rays remaining under that height, and early-out:

typedef std::vector<float> visbuf_t;

inline void map::_visibility_scan(const visbuf_t& in,visbuf_t& out,const vec_t& eye,int start_x,int stop_x,int y,int prev_y) {
    const int xdir = (start_x < stop_x)? 1: -1;
    for(int x=start_x; x!=stop_x; x+=xdir) {
        const int x_diff = abs(eye.x-x), y_diff = abs(eye.z-y);
        const bool horiz = (x_diff >= y_diff);
        const int x_step = horiz? 1: x_diff/y_diff;
        const int in_x = x-x_step*xdir; // where in the in buffer would we get the inner value?
        const float outer_d = vec2_t(x,y).distance(vec2_t(eye.x,eye.z));
        const float inner_d = vec2_t(in_x,horiz? y: prev_y).distance(vec2_t(eye.x,eye.z));
        const float inner = (horiz? out: in).at(in_x)*(outer_d/inner_d); // get the inner value, scaling by distance
        const float outer = height_at(x,y)-eye.y; // height we are at right now in the map, eye-relative
        if(inner <= outer) {
            out.at(x) = outer;
            vis.at(y*width+x) = VISIBLE;
        } else {
            out.at(x) = inner;
            vis.at(y*width+x) = NOT_VISIBLE;
        }
    }
}

void map::visibility_add(const vec_t& eye) {
    const float BASE = -10000; // represents a downward vector that would always be visible
    visbuf_t scan_0, scan_out, scan_in;
    scan_0.resize(width);
    vis[eye.z*width+eye.x-1] = vis[eye.z*width+eye.x] = vis[eye.z*width+eye.x+1] = VISIBLE;
    scan_0.at(eye.x) = BASE;
    scan_0.at(eye.x-1) = BASE;
    scan_0.at(eye.x+1) = BASE;
    _visibility_scan(scan_0,scan_0,eye,eye.x+2,width,eye.z,eye.z);
    _visibility_scan(scan_0,scan_0,eye,eye.x-2,-1,eye.z,eye.z);
    scan_out = scan_0;
    for(int y=eye.z+1; y<height; y++) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y-1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y-1);
    }
    scan_out = scan_0;
    for(int y=eye.z-1; y>=0; y--) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y+1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y+1);
    }
}