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.)

When you say "slope the line of sight around corners", what exactly do you mean? — Djentleman
– Djentleman, Commented Jan 17, 2013 at 4:44
Best I can say is to check out a game on crawl.s-z.org. As an example, when the player is standing below a horizontal wall 5 tiles wide, the line of sight breaks above the horizontal plane of that wall - but not unrealistically beyond it. The best I've been able to approximate is keeping the line of sight at the horizontal plane of the wall. — CodeMoose
– CodeMoose, Commented Jan 17, 2013 at 17:28

Djentleman · Accepted Answer · 2013-01-17 05:05:05Z

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.

Seems like the way to go - especially bresenham's. Thanks for the help djent! — CodeMoose
– CodeMoose, Commented Jan 17, 2013 at 17:29

Will · Accepted Answer · 2013-01-17 13:16:46Z

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); } }

This is good, but I think far more than he's after if what he wants is anything like the link he posted. — Djentleman
– Djentleman, Commented Jan 17, 2013 at 13:46
Very in-depth and impressive, but djent is right - way out of my scope. Thanks for the post though! — CodeMoose
– CodeMoose, Commented Jan 17, 2013 at 17:22
@CodeMoose eh its working code; just cut-n-paste, translate literally to whatever language you're targeting. It is an implementation of Bresenham, done incrementally so it only visits each square once. If you, for each grid square, do a Bresenham line to the player, you'll find it massively slower. — Will
– Will, Commented Jan 17, 2013 at 18:22

Stack Exchange Network

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

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

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

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions