Roguelike游戏的视野算法

小篱

【最近对这方面有兴趣，康了些资料顺便翻译了，出处：

Roguelike Vision Algorithmswww.adammil.net

里面还有很多资料，这没贴出来，主要是implementations和对比】

简介

实现Roguelike的一项任务是弄清楚如何计算玩家或怪物的可见区域。现有的算法很多，但是都存在缺陷，因此我着手开发一种新的算法，该算法对我来说是快速，准确和美观的。尽管我没有创建理想的算法，但我仍然认为我的算法是对其他算法的改进。

可见区域（视野/ field of view / FOV），判断单位是否可以看到地形的某个部分。这里假设地牢是很常见的基于tiles的类型。玩家是否可以“看到tile”（视线/ line of sight / LOS）有时与玩家是否可以“看到tile中的怪物”有所不同，也不同于他是否可以使用远程武器或咒语”瞄准该怪物“（瞄准线/ line of targeting / LOT）。

理想的算法属性

接下来首先描述视野算法一些常见而有用的特征，然后说明为什么大多数现有算法缺少这些特征中的一个或多个。

• 对称性（Symmetry）： 如果站在tile A上可以看到tile B，那么站在tile B上就应该能够看到tile A。而且视野不对称通常会导致战术性和公平性变差（当LOS与LOT相同）。当然如果游戏是刻意造成不对称的话是例外。
• 墙壁扩展（Expansive Walls）：站在没有凹陷的大房间时，你可以看到房间里所有的墙；而站在长走廊时，您可以看到走廊两侧所有的墙。尽管它很少影响游戏玩法，但如果算法不具有此属性，看起来就会很丑，并且会使探索变得乏味。
• 扩大柱子阴影： 当视线被柱子遮挡时，柱子应以扇形投射阴影。这通常可以提供更具战术性的玩法：更容易隐藏，伏击和逃脱。但是许多roguelike根本没有柱子，这个属性就跟他们没啥关系了。
• 没有盲角： 在拐角处可以在看到至少两个tile。因此，如果沿拐角对角移动，你就不会发现自己旁边突然出现之前看不见的怪物。这也意味着可以在进入大厅之前看到两侧至少两个tile。大多数情况下这都是可取的，如果玩家走过每个角落都必须小心翼翼就有些乏味了。一些算法允许拐角处可以看到无限远，也算保护玩家免受远程武器的伤害。
• 没有伪影（Artifacts）： 尽管对于视野算法而言什么是“正确”有讨论空间，但是算法至少应该做到本份。意思是算法应该定义如同现实世界的几何图形并准确地模拟光传播。伪影的意思是有些算法根本不符合现实世界的几何体，是使用近似而非精确的数学来实现的，并且存在bug。
• 效率： 算法不应该花费很长时间，并且最好避免重复测试同一个tile。
  

现有算法

不算详尽，涵盖了最常用的算法。

光线投射（Ray casting）

优点： 简单。相当快。扩大柱子阴影。良好的光影平衡。没有盲角。

缺点： 不对称。没有墙壁扩展。间隙很多（可见性不连续）。

这算法会将光线从玩家投射到地图边缘上的每个点（或视野半径边缘的每个点）。光线用简单的画线算法投射（如Bresenham'的算法[0]），一碰到墙就会停止。光线投射是最简单而且速度很快的算法，但是有许多问题。

• 不对称。 Bresenham的算法是不对称的，但是即使你用对称的画线算法，结果还是不对称，因为在替换位置时线条的端点不会简单地反转。
• 在可见点和阴影上也都存在间隙，并且很古怪。后期处理可以修复间隙，可以消除难看的伪影，但会减慢速度，并且无法解决其他问题。
• 会多次重复测试tile，效率有些低下，但是由于简单性，最终还是非常快，尤其是在较小的视线范围。
  

光线投射以最快的算法闻名，但是这主要是由于较复杂的算法普遍实现的较差。实现良好的阴影投射算法永远比光线投射更胜一筹。但如果撇开间隙和不对称，仅考虑光线和阴影的形状，我认为光线投射比阴影投射和菱形墙等更复杂的算法产生更好的结果。而且，随着视线半径的减小，大多数问题都变得没那么严重了；如果圆形视线半径为4或更小，它其实可以很好地工作，不需要进行后期处理（尽管还是有些一些伪影）。

代码：http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#raycode

阴影投射（点对tile或点对点）（ Shadow casting）

优点：快。扩大柱子阴影。墙壁扩展。连续的可见性。

缺点：对角线视野比平常窄得多。盲角。光束通过门扩展得太多。不对称。消除伪影的方法复杂（nontrivial）。

阴影投射是从玩家向外投射扇形光线的技术。当一个扇区碰到墙时，该扇区可能会减小角度或分成两个扇区，然后分别进行处理。实现方式各不相同，但是好的实现只会访问每个tile一次或接近一次，并且每个tile仅进行少量且大致恒定的工作。如果实现得当，阴影投射会成为最快的算法之一；但在实现不佳的情况下，它在走廊拐角和具有许多小障碍物的开放区域中的速度可能较慢。 “阴影投射”有点用词不当，因为实际投射的是光，但我还是会用这词，因为“Light casting”跟“Ray casting”有些像。在我见过的所有case，阴影投射都使用正方形的tile，但是其他形状也是可能的。

在通常的实现中，如果从玩家的tile中心到目标tile的任何部分之间都存在一条畅通的线条，则tile为可见。这是一个示例，说明阴影投射如何针对单个八分圆扇形进行工作。 （并非所有实现都可以在八分圆中工作）

↑一个45度的扇形投影到了45度八分圆处，绿线为顶部，蓝线为底部。显示的分数是直线的斜率，数值永远是0到1之间，带有圆圈的象限被视为可见。然后，算法从发射点向外工作，对于每一列，它从扇区内的tile从上倒下扫。如果找到从透明到不透明的分界，则调整扇区至不包含该不透明。

↑已经扫描了前三列，并且在第四列中发现了分界（不透明>>透明），因此向下调整了顶部。

↑找到分界（透明>>不透明），因此向上调整了底部。

↑在第五列中找到了两种分界，因此将扇区一分为二，每个扇区独立继续。当算法达到最大视距或所有扇区变空（底部斜率>顶部斜率），算法将停止。

阴影投射的一些功能和问题（使用普通的正方形tile）。

上面就是不对称性会减弱战术性的一个原因。如果可以瞄准看到的东西（LOS==LOT），那么走廊中间会比拐角具有优势，尽管拐角看上去更隐蔽。拐角的单位可以在不见攻击者的情况下被射杀。像这样的不对等就是对称性是一种理想特性的原因。但是，如果上述不对称性被逆转，则实际上它可能是优于对称算法：可以使拐角真的更加隐蔽，使游戏更具战术性（更佳的可能是LOS对称，而LOT不对称）。有一种称为“反向阴影投射”的算法可以逆转不对称性，但通常看起来更差并且运行更慢。

不过，对阴影投射代码进行小的修改就足以使其对称。这是通过更改算法来实现的，因此只有在从玩家的tile中心到目标tile中心（而不是目标tile的任何部分）有一条畅通无阻的线条时，它才判定tile可见。如下所示，这可以解决一些问题但会导致其他问题。

代码：http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#shadowcode

【key point is the strategy of how to determine a tile is visible: just need the sector cover the tile? or need to cover the center point? or cover a certain percentage of area? 发射点固定了在格子中央，但是被观察的一方则是视线稍为蹭到格子都算看见，因此不对称】

菱形墙（Diamond walls）（点对tile或点对点）

优点：相当快。扩大支柱阴影。墙壁扩展。没有盲角。可见性基本连续。

缺点：光束通过门会扩展太多。不对称；小更改即可解决，但相对会丢失墙壁扩展并导致不连续

就像阴影投射一样，如果从玩家tile的中心到目标tile的任何部分都存在一条畅通无阻的线条，则tile为可见，但是它会将墙视为菱形。这比标准阴影投射有更大的拐角可视距离空间，更好地窥视各个角落。但它本身会带来一些问题，主要是有点过于宽容，使太多的tile可见，尽管如此，这似乎也是对标准阴影投射的一种改进。 （我稍为修改阴影投射代码来实现）至于效率，它比普通阴影投射要慢一些，因为它需要为每个tile做更多的工作，但是仍然相当快。

将墙视为菱形实际上在roguelikes中很有用。原因是大多数roguelikes允许单位在对角相邻的墙之间移动，如果墙是正方形的，它们的角就会碰触，没有空间。如下图所示。使游戏的物理学更加一致【指可移动范围与可视范围有一致性？ 】。菱形墙还可以使拐角处的视野更好，通常是好事。

不幸的是，菱形墙存在理论上的问题。与菱形成切线视之为不相交；零宽度的光束仍然能照亮tile。这样可以在拐角处提供更好的视野，但在以下情况下使单位可以透视墙壁。应该要在特殊情况下禁止透视墙壁，但会造成游戏物理在某些情况下不一致。

菱墙的一些功能和问题

简单更改足以将菱墙算法转换为对称算法，但有与标准阴影投射相同的优缺点

代码：http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#diamondcode

半宽墙（Half-width walls）

优缺点： 与菱形墙相同，但更宽容，但速度稍慢。

另一个类似于菱形墙的想法，分别是它使用的墙是通常宽度的一半。它也解决了在对角tile之间的视野问题，但在我看来过于宽容，感觉比菱形墙更差。由于并非每个墙都是相同形状，因此实施速度也稍慢。 （形状取决于是否有相邻的墙要连接。）我姑且实现了这算法，但实在不值得花这气力。

宽容的FOV（Permissive field of view）（tile to tile）

优点： 对称。没有盲角。墙壁扩展。连续可见性。

缺点： 慢。没有扩大的支柱阴影。拐角处的可见性可能过多。

如果从玩家tile的任何部分到目标tile的任何部分之间都存在一条畅通无阻的线条，则视tile为可见。此方法的大多数实现都是估算，例如仅对对角进行相互测试【并不是任何部分，而是只有目标和自己的四个边角点】，在某些情况下会失败。精准的实现可以适应所有情况，但是慢。我提供了一个精确的实现（改编自Jonathon Duerig[1]）。该算法的主要特征是对称，并且在拐角可以看很远，但对我而言有些太宽容了，所以我没有很努力优化这算法。可以说如果所有生物的视线半径都较短，那这算法感觉上和实际上都会更好。

有一个这算法的版本，可以在运行时更改宽容度（permissivity）。我玩了一下，把通常宽容度减半看上去很不错，但就不再对称了，而且我想有个更快的算法anyway。

代码： http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#permissivecode

Digital FOV（菱到菱）

优点和缺点： 与宽容FOV算法相同。

Digital FOV将每个tile都视为菱形，并且如果从玩家菱形的任何部分到目标菱形的任何部分都存在一条畅通的线条，则认为该tile可见。结果，它甚至比允宽容FOV稍微宽容一些（因为墙壁的障碍性更小） 。在其他方面所有相同的特征和缺点一样，但更慢。这个想法是基于的相当笨拙的digital straight line segments概念，我没有费心实现这个。 One interesting feature of the algorithm is that the knowledge of the digital line segment from a line-of-sight calculation allows easy tracing of a projectile path through space without hitting any walls, even down somewhat twisted tunnels (such as the Kuo corridor above) 。但是复杂性似乎超过了收益。

我的算法

以上没有一个令我满意。首先除了ray casting之外，要么太宽容，要么太过局限，有时两者都有。而且ray casting有太多伪影，用不来。下面我打算修复的问题和我想要的功能。

• 没大多数其他算法那么宽松
• 比其他算法对称
• 能够做到对称（至少跟不能穿墙的怪物相对）而不会损失墙壁扩展
• 良好的拐角视野，但不能太好
• 良好的狭窄的空间视野，而不会损失墙壁扩展
• 比其他算法更少阴影间隙
• 与菱形墙相当的效率
• 没有死角
• 没有伪影
• 一致的物理
  

为此，我会将地牢的几何结构像下图一样表示。 （注意：图2中的两个角应该是斜角的。我画错了。不过，这图说明了内部正方形的用途。）

1.        如果一个墙tile的两个相邻都不是墙，则将该角切成斜角。

2.        如果光束与墙的形状相交，则墙tile可见；

3.        如果光束与中心正方形（size最大为tile的1/2）相交，则空白tile可见。

4.        与图形成切线不算相交，并且零宽度的扇形无法照亮。

带有斜角的实心墙允许在拐角处窥视并可以看到对角空间，同时避免了钻石墙的理论问题。除非光线在中心附近通过，否则不要看见空白tile，这应该会没那么宽容，减少阴影间隙，减少不对称性并搞定光线通过窄空间的行为。

图2说明了光线穿过狭窄空间的问题。不管沿着隧道走多远，扇形都会在离开走廊时打开，而其他算法会立即照亮出口上下方的tile。支柱也是同理，就像走廊的墙壁一样，扇形在穿过支柱之间后打开。不照亮光线照射的比较少的tile就可以避免这种情况，还能让柱子有效的阻挡光线。因为能防止小束光线照亮tile，应该还能减少阴影间隙。

可以通过调整斜角的角度和内部正方形的大小来调整宽容度。可以使用正方形以外的其他形状，但是起码要可以放在tile中的最大菱形区域（就是不应该比柱子大）。用正方形的话，最大值为tile长宽的1/2，测试表明这样的结果最好。使用3/8的宽度，可以在长走廊内和拐角的单位之间对称的互望，很不错，但在其他情况感觉有些局限（尤其是在有许多柱子的环境下），所以我会用1 /2。实际的实现使用了修改的阴影投射算法，只要我能避免在每个tile上做太多工作就能有不错的性能。

不对称版本的例子【1/2大小】

我的算法有两个对称版本：一个是完全对称的版本，另一个是基本对称的版本（就是单位之间是对称但穿墙单位另算）。

基本对称的版本。对称时，它不会遇到其他算法的相同问题。最重要的是不会失去墙壁扩展。这是两个对称版本中较好的，除非你需要与穿墙单位也对称

完全对称版本。它与所有穿墙单位都有对称性，但没了了墙壁扩展；虽然扩展程度比大多数算法更好（宽容FOV除外）。与对称的菱形墙非常相似但不相同

代码：http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#mycode
[0] Bresenham's algorithm: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
[1]Jonathon Duerig: https://user.xmission.com/~tyrecius/

作者：淮山
专栏地址：https://zhuanlan.zhihu.com/p/94699665