二维可见性计算
发表于2017-11-14
重要提示： 本文章中的图片为Flash，可以去原文中观看，译文中均为截图！
特此说明！
发射射线
墙体跟踪
游乐场
联合输出
使用
其他相关
来自：http://blog.csdn.net/cartzhang/article/details/46829133
特此说明！
在二维自上而下的地图中，有些时候，我们需要从一个给定的点计算可视区域。比如：你可能需要隐藏玩家当前位置看不到，或想知道火把可以照亮的区域。
拖动图上圆圈来看看在玩家位置那些是可见的。如下图：
这个算法也可以计算给定一个光源来计算被照亮的区域。每条光线运算一次，我们可以构建一个光照地图来显示那些区域被照亮了。若我们放置24个光源在上面的迷宫？(显示/隐藏光照地图)。
游戏社区已经收集了几种算法，尤其是基于网格的。删减算法是开始所有的东西都是可见的，然后减去隐藏的区域；添加算法是一开始所有都不可见的，然后添加可见的区域。我将会介绍一种添加算法，这种算法基于线分割，而不仅仅是固定块或网格。
发射射线
一个简单的办法就是从中心发射射线。这是个合理的第一步，来确定一个大致的答案。
为了精简，我们只在墙的转角点的开始或结束处发射线。由这些射线构成的三角形就是可视区域：
就是这样！算法步骤如下：
1. 计算墙开始或结束的角度。
2. 从中心发射条线到每个角。
3. 填充由这些射线组成的区域。
墙体跟踪
其实，到这里我们应该停下来，尤其是在我们已经有一个快速的发射射线的算法，我们不用去使用空间哈希，来避免与每个墙体求交。然而，一个更有效的方法是把发射射线和墙体相交组合为一个算法。我将描述这个算法，用一条线绕着圆快速扫动，碰到的所有的点根据角度来排序；也可以扩大圆的半径，碰到的所有点根据半径长度来排序，但是我们我们没有尝试这种方法。
在连续射线间的区域，我们想要找到最近的墙体。这个面墙是可被照亮的；其他的是隐藏的。我们的策略是扫描360度，处理所有的墙上所有的端点。我们所作的是，我们将跟踪与扫描线相交的墙体。
点击播放，来看扫描线的端点：
下一步是跟踪扫描线穿过的墙体。只有最近的墙上可见的。我们怎么才能知道那个是最近的墙体呢？很简单，就是计算中心到墙体的距离。然而这种方法在墙体不同形状的时候，不管用，故此示例使用一个更加复杂的方法，这里我并不打算着解释。
点下播放按钮，可以看到扫过的最近的墙绘制为白色，而其他的墙则绘制为黑色。
在最近墙的最后或一个新墙的比其他墙的都近，我们创建一个三角形的可见区域。这些三角形一起构成了从中线点的可见区域。
注意到三角形是由之前扫描射线与之前处理的墙相交求出来构成的。所以，三角形的新边可能比扫描射线长或短，三角形最长边可能比先前处理的墙要短。
游乐场
这里有一个更多活动块的游乐场。拖拽活动块到网格区域。点击播放或暂停来看算法处理过程，或拖拽中心点来看看随着玩家走动会有哪些区域可见。
我们可以设置操作方法来用有趣的方法联合输出算法。这些实现，在分析输出算法中只是布尔值操作，或渲染输出中位图操作算法。
玩家视角最简单的限制玩家视角的操作，就是把视角输出上做些可见性限制。比如：使用圆求交的算法限制你可见的半径。使用梯度填充圆，让光照随着距离而减弱。与用圆锥体来创建一个手电筒效果求交，这样你可以在你面前的看到更远，而在你背后的看不见。（可以看Dynamite Jack对于这种限制的示例）。
若你使用两只眼睛来代替玩家一只眼睛来处理，玩家视角的效果会更好。我期望你可以综合每只眼睛的输出，但是我不打算尝试。
地图对象可见性经常被用于计算火炬照亮的区域。在页顶部的示例联合了每个火炬能照亮的区域，然后在与玩家的视野范围求交。（注意算法产生的是硬阴影效果，你需要后处理输出来得到软阴影效果。）
同样的计算可以用于决定哪里是安全的相机可视的区域，哪里是需要遮蔽保护的，或一个神奇的对象离你足够近的时给你一个红包或诅咒。
AI的行为可视性也可以用来构建AI的行为。
比如：我们假设一个敌方AI试图向其中一个玩家投掷手榴弹，但是同时需要站在一个玩家打不着的地方。手榴弹需要离得足够近来击中玩家，但是也不能在障碍物后面。
这个图表显示了地图标注和AI个体可能的计算：
手榴弹扔进紫色区域可以成功伤到玩家。黄色和紫色区域是站立的危险区域；玩家可以从三个区域射击AI个体。AI需要站立在安全区域(蓝色区域)，投掷手榴弹到紫色区域，然后找隐蔽。那么该怎么计算呢？从AI 打算扔手榴弹的地点进行可视性计算，让橱柜和桌子挡住视线。
使用
我已经写了关于这个算法的haxe 3应用，代码在Apache V2的许可（简单的MIT和BSD，它可以用于商业项目）下使用。Haxe的代码可以编译成Javascript，Actionscript ，C++，Java，C#或PHP。我为这个页面编译成了JavaScript代码，对于我的其他项目我编译成Flash。我已经用以下语言编译完毕：
· l Actionscript；可读性，与haxe没有太大差别。
l Javascript（在本页中用于示例）；大部分可读
l Java；中级可读，但是不是很好。
l C#；中级可以，但是不是很好。罗伊.崔斯彻这有更好的版本。
韦德.崔斯特雷建议手动移植比使用Haxe输出移植要更清晰。我同意。若你亲手写这些代码会使你更好的理解算法。
尽管算法的主要部分是CPU的功能职责，GPU用来把三角形渲染到位图，融合位图的合成操作。（一个布尔的与操作变成位图的乘法；一个布尔的或操作变成位图的加和限定）。在我项目中性能还不是一个很明显的问题，所以没有编译GPU版本。如果你的游戏是CPU计算，考虑使用删减算法（代替添加算法），作为四元数渲染每条线的阴影。这将会增加GPU的渲染负担，但是它不需要在GPU上排序了。假如填充效率是一个问题，那就考虑在低分辨率下渲染一个光照贴图而不是游戏画面，然后缩放它。
其他相关
视角和光照说明了可见性的问题；在我的博客邮件中我有更多的链接。天际线的问题与2D可见性问题类似，除了它用笛卡尔坐标系代替了极坐标。还有艺术画廊关于摆放多个守卫，这样他们就可以看到地图的任意地方。我把未来更新此页内容做了个列表，放在我的日程管理上。
来自：http://blog.csdn.net/cartzhang/article/details/46829133