本文翻译自： https://sites.google.com/site/jicenospam/visibilitydetermination

本文目的是：在Roguelike游戏中计算出，相对于Player哪些Cells是可见的（Player一般显示为@，且位于屏幕中央）。如果由Player向一个Cell投射的光线（A ray of light）中途没有遮挡（Block），那么这个Cell是可见的。值得说明的是，即使一个Cell是潜在可见的，若光线（由于距离等因素）并未照射到它（Cell in darkness），那么它仍然处于隐藏状态之下。

这里即将展示的算法并不是效率最高的，但是它实现起来足够简单，并且给了我们一个清晰、真实的潜在可见集（Potential visible set，PVS——计算机图形学术语，简单理解就是视野范围内经过遮挡关系处理后余下的必要数据集合）。

光线投射 （Ray casting）

首先我们需要在Player周围投射多条光线。每条光线经过的每个Cell都将被标记为可见（Visible），直到这条光线到达一个可遮挡光线（Light blocking）的Cell为止。

如上图所示，以Player位置为中心，我们向地图可见边界上的每一个Cell投射了光线。这里我们需要编写一个函数，它应当可以返回每条光线经过的所有Cells的坐标集合。幸运的是，有一个广为人知的算法实现了以上功能：

The bresenham’s line algorithm（布雷森汉姆直线算法）

布雷森汉姆直线算法存在的问题

好的，假设我们实现了以上算法，并在Player（@）周围投射了光线，然后将所有光线所经过的Cells标记为了可见。此时若我们在地图中四处移动，可以发现，某些墙块（Wall，也是一种Cell）会出现不真实的可见性表现，特别是当Player靠近墙面时。

这是由于，当某条光线投射到某个墙块时，若该光线与该墙块所在的墙面近乎平行，则PVS中可能会错误的遗失这样的墙块（Cell）。

如上图所示，我们投射了一条光线，并将它经过的Cells标上了黄色方框。

如上图所示，我们又投射了一条光线， 同样将它经过的Cells标上了黄色方框。

如上图所示，最后我们将两次光线投射所标记的黄色方框放在一起。带黑叉的Cell表示它应当被标上黄色方框（可见），可结果却没有。这个问题的产生原因是：当某条光线到达某个墙块时，事实上该光线应当继续经过该墙块旁边的墙块，而不应当就此停止；但假如我们仅拥有一个用于表示光线穿透（LightThrough）的布尔信息，而不考虑墙块方位，那么要解决这个问题明显是行不通的。

幸运的是，我们可以运用一个小技巧解决上述问题，并且无需为Cell添加额外信息。该小技巧的规则是：

如果Player能够看到一个表示地板的Cell（Ground cell），那么他就能看到该地板后边的墙块。

真实性的后续打磨

根据下图的区域划分（红色虚线），“Cell以墙块为始”（“The wall begin a cell”）拥有不同的相对含义：

注：以上段落的翻译准确性有待商议，期待您提出更准确的翻译。原文——“ The wall begin a cell” has a different signification depending on the part of the map we look at : ”。

如上图所示，相对于Player所见，我们将每一个墙块前方的地板Cell表上了绿叉。此时，可将地图划分为四个区域：

• 左上区域。地板后方的墙块位于该地板的左方或上方。
• 右上区域。地板后方的墙块位于该地板的右方或上方。
• 左下区域。地板后方的墙块位于该地板的左方或下方。
• 右下区域。地板后方的墙块位于该地板的右方或下方。

接着，我们所需实现的算法内容包括：

在地图中遍历所有可见Cells。

如果某个墙块不可见，但是它直接位于某个可见地板后方，那么我们该墙面标记为可见。

最终结果：

如上图所示。左边场景中，PVS中遗失了某些可见墙块（黄色箭头所指）。右边场景中，我们通过上述算法解决了左边的问题。