在二维网格上用障碍物模拟“视线”?

进入一个有趣的问题。 我需要弄清楚如何模拟视线 – 很简单,就在一个有障碍物的二维网格上。 网格单元格是可见的,或者不是。

我可以得到一些非常基本的东西 – 比如从玩家那里传播n个空格,或者在发现一个相邻的障碍时阻止水平传播,但是我不能让自己和它一起生活。 许多其他的应用程序正在使用更复杂的方法,以避免在角落等视线,我想达到平等。

到目前为止,当我被困时,DCSS一直是我的灵感来源,我希望能够接近他们所拥有的东西: http : //crawl.sz.org/ 。

任何有识之士将不胜感激 – 感谢您的帮助!

(如果这是不好意思的话,原谅 – 几周前才开始游戏开发,努力追赶。)

光线投射是确定视线的非常快速有效的方式。 它基本上涉及从某一方向以某一方向发射一束光线(将其想象为一种无法重新定向的无限激光)。 使用这个射线,你可以确定它相交的点和离原点相距多远的点。

因此,例如,在玩家/敌人的情况下,射线可以源自敌方,方向是玩家的位置。 如果光线与坚实的瓷砖相撞,敌人就看不到玩家。 如果没有,敌人可以看到玩家。

这是一个很好的教程,应该有所帮助。

你也可以考虑布雷森汉姆的线algorithm (总结,它创建线)的东西,可以更容易地缩放到瓷砖。

我有博客代码从高度图计算视线。 有障碍物的简单平面地图只是一个非常平坦的高度图,这个实现仍然是完全适用的。

在这里输入图像描述

这里是C ++和它的O(n) ; 如果您知道地图的最大高度,则可以跟踪在该高度下没有光线的扫描线,并提前:

 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.xx), y_diff = abs(eye.zy); 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); } }