简介
实现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或更⼩，它其实可以很好地⼯作，不需要进⾏后期处理（尽管还是有些⼀些伪影）。
阴影投射（点对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可见。如下所⽰，这可以解决⼀些问题但会导致其他问题。
【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。这样可以在拐⾓处提供更好的视野，但在以下情况下使单位可以透视墙壁。应该要在特殊情况下禁⽌透视墙壁，但会造成游戏物理在某些情况下不⼀致。
菱墙的⼀些功能和问题
简单更改⾜以将菱墙算法转换为对称算法，但有与标准阴影投射相同的优缺点
半宽墙（Half-width walls）
优缺点： 与菱形墙相同，但更宽容，但速度稍慢。
另⼀个类似于菱形墙的想法，分别是它使⽤的墙是通常宽度的⼀半。它也解决了在对⾓tile之间的视野问题，但在我看来过于宽容，感觉⽐菱形墙更差。由于并⾮每个墙都是相同形状，因此实施速度也稍慢。 （形状取决于是否有相邻的墙要连接。）我姑且实现了这算法，但实在不值得花这⽓⼒。
宽容的FOV（Permissive field of view）（tile to tile）
煤矿井下定位设备优点： 对称。没有盲⾓。墙壁扩展。连续可见性。
缺点： 慢。没有扩⼤的⽀柱阴影。拐⾓处的可见性可能过多。
如果从玩家tile的任何部分到⽬标tile的任何部分之间都存在⼀条畅通⽆阻的线条，则视tile为可见。此⽅法的⼤多数实现都是估算，例如仅对对⾓进⾏相互测试【并不是任何部分，⽽是只有⽬标和⾃⼰的四个边⾓点】，在某些情况下会失败。精准的实现可以适应所有情况，但是慢。我提供了⼀个精确的实现（改编⾃Jonathon Duerig[1]）。该算法的主要特征是对称，并且在拐⾓可以看很远，但对我⽽⾔有些太宽容了，所以我没有很努⼒优化这算法。可以说如果所有⽣物的视线半径都较短，那这算法感觉上和实际上都会更好。
有⼀个这算法的版本，可以在运⾏时更改宽容度（permissivity）。我玩了⼀下，把通常宽容度减半看
上去很不错，但就不再对称了，⽽且我想有个更快的算法anyway。
