投影法是计算视野最常用的算法。 该算法 高效, 一致, 而且 对称。
#· #####
#·· #···# ·#####
··· ###····###···### ·······
····················# ······#
····················#
#···@···········#
·························
#················# ······#####
# ###····######·## ····#
#·· ·· ·#
#· ··
·#·#·#· ····· ·········#····
·###·#· ···· ········
·· ··· ··
· ####
········ ····
············ ####
·###····
·#· ·
·#· · ··· ····
·#·#·#· ········ ······· ####
·#·#·#· ·········· ············
解释投影法的最好方式是一步一步演示。下面就是该算法的核心函数。你可以使用下面的滑块和按钮逐步调试代码，焦点聚焦在滑块时，按方向键也可以调试。
完整的实现在文章最后。点击函数既可以跳转到定义。
def scan(row):
prev_tile = None
for tile in row.tiles():
if is_wall(tile) or is_symmetric(row, tile):
reveal(tile)
if is_wall(prev_tile) and is_floor(tile):
row.start_slope = slope(tile)
if is_floor(prev_tile) and is_wall(tile):
next_row = row.next()
next_row.end_slope = slope(tile)
scan(next_row)
prev_tile = tile
if is_floor(prev_tile):
scan(row.next())
return @
···
·#···
·······
######·##
······#·#··
·······#·#···
········#·#····
在这篇博客中 Roguelike Vision Algorithms ,Adam Milazzo 列举了视野算法应该满足的六个性质：
对称投影算法满足以上六条性质。
我第一次看到使用斜角是在Adam's的帖子上的。我们的最终算法会和这个很相似，如果你想了解细节，那你一定不能错过他的帖子.
对称投影在不同地板间具有完美的对称性。所谓的对称性是指， 若地板A在地板B的视野内，那么地板B也必定在地板A的视野内。 该性质由
is_symmetric 函数保证。
不过该性质不保证墙体也对称。举个简单的例子，该算法事先假定了视点位置的贴图并不会遮挡视线。 如果你在类似墙体这种会遮挡视线的位置使用该算法，那么你视野内的位置均看不到你（因为你的位置是墙体，你被墙体遮盖住了），这就是非对称性。不过做一些简单修改就可以让该算法消除这种非对称性。
投影算法中，视点位置为该贴图的中心点。当扫描地板时，该算法将其为中心点(is_symmetric)。但扫描到墙体时，该算法将将墙体作为一个竖向的菱形处理。
(Row.tiles).为了保证对称性，若视点位置为墙体，该算法需要将其视为菱形。
现在将视点(A)作为菱形，将会投射出两种阴影：实影(B)和半影(C)，半影部分可见，而实影完全不可见。
很显然，完全在实影中的贴图应当是不可见的。但在半影中的贴图应当处理为可见，否则，由于半影中可以看到原视点，而这就破坏了对称性。
所以，视点位为墙体时，该算法需要一些修改。
is_symmetric中的比较应当使用严格不等式。墙体延展是指，当视点处于一个凸空间内时，所有的墙体均应该为可见。
####### #·····# #@····# #######
###### #·····# #@····# ####
#
###
右图这个非墙体延展的例子来自于投影算法的一个变体，该变体用is_symmetric检查地板和墙体 这个方法快捷简单，但是会导致奇怪的阴影。
对称投影通常都会生成发散性阴影。但视点为墙体时，会出现意外情况。此时为了保证墙体延展，必须将柱子的影子设定为固定宽度。
很多 roguelike 游戏中，玩家可以斜着通过拐角。如果斜着通过角落后，玩家的位置在未通过时视野盲区的旁边，那么该拐角就是盲角。对称投影算法中不存在盲角。
···@··· ####··· #··· # ··
··· ··· ·
···@··· ####··· # ·· # ·
··· · ··· ··
右图这个盲角由未使用斜面墙而导致。
该算法尽量不使用近似，以此尽可能的减少伪影。算法使用实数，而非有理数，此外该算法很仔细地处理了舍入。
不过有些近似不可避免。毕竟这里的投影作用在网格空间，而非完备的欧几里得平面。绝大多数时候，算法的结果都符合直觉。但当墙体之间有小缝隙时，可能会出现一些异常。有时视野并不连续。
@··# ··# ··· ··· ····· ····· ····· ······ ·
·············
· ··········
····· ····
·······
··········
该算法模型有一个很大的优点：生成的阴影完美对应 Bresenham 算法。 因此，如果两个位点间可以画出一条直线，那么这两个点必定互相在对方的视野中；反之亦然。
这意味着许多远程攻击类似的操作的视野与该视野是一致的。如果你能瞄准该位点，那么该位点一定在你的视野内；反之亦然。
与其他视野算法相比，投影法通常更高效。 perform
well 防止递归出问题, 文章在结尾提供了一个 非递归的 scan 函数。
import math
from fractions import Fractiondef compute_fov(origin, is_blocking, mark_visible):
mark_visible(*origin)
for i in range(4):
quadrant = Quadrant(i, origin) def reveal(tile):
x, y = quadrant.transform(tile)
mark_visible(x, y)
def is_wall(tile):
if tile is None:
return false
x, y = quadrant.transform(tile)
return is_blocking(x, y)
def is_floor(tile):
if tile is None:
return false
x, y = quadrant.transform(tile)
return not is_blocking(x, y) def scan(row):
prev_tile = None
for tile in row.tiles():
if is_wall(tile) or is_symmetric(row, tile):
reveal(tile)
if is_wall(prev_tile) and is_floor(tile):
row.start_slope = slope(tile)
if is_floor(prev_tile) and is_wall(tile):
next_row = row.next()
next_row.end_slope = slope(tile)
scan(next_row)
prev_tile = tile
if is_floor(prev_tile):
scan(row.next())
first_row = Row(1, Fraction(-1), Fraction(1))
scan(first_row)class Quadrant:
north = 0
east = 1
south = 2
west = 3
def __init__(self, cardinal, origin):
self.cardinal = cardinal
self.ox, self.oy = origin def transform(self, tile):
row, col = tile
if self.cardinal == north:
return (self.ox + col, self.oy - row)
if self.cardinal == south:
return (self.ox + col, self.oy + row)
if self.cardinal == east:
return (self.ox + row, self.oy + col)
if self.cardinal == west:
return (self.ox - row, self.oy + col)class Row:
def __init__(self, depth, start_slope, end_slope):
self.depth = depth
self.start_slope = start_slope
self.end_slope = end_slope def tiles(self):
min_col = round_ties_up(self.depth * self.start_slope)
max_col = round_ties_down(self.depth * self.end_slope)
for col in range(min_col, max_col + 1):
yield (self.depth, col)
def next(self):
return Row(
self.depth + 1,
self.start_slope,
self.end_slope)def slope(tile):
row_depth, col = tile
return Fraction(2 * col - 1, 2 * row_depth)def is_symmetric(row, tile):
row_depth, col = tile
return (col >= row.depth * row.start_slope
and col <= row.depth * row.end_slope)def round_ties_up(n):
return math.floor(n + 0.5)
def round_ties_down(n):
return math.ceil(n - 0.5)def scan_iterative(row):
rows = [row]
while rows:
row = rows.pop()
prev_tile = None
for tile in row.tiles():
if is_wall(tile) or is_symmetric(row, tile):
reveal(tile)
if is_wall(prev_tile) and is_floor(tile):
row.start_slope = slope(tile)
if is_floor(prev_tile) and is_wall(tile):
next_row = row.next()
next_row.end_slope = slope(tile)
rows.append(next_row)
prev_tile = tile
if is_floor(prev_tile):
rows.append(row.next())
origin: 一个 (x, y) 元组。
is_blocking(x, y): 若(x, y) 阻挡视线，则返回True，否则返回False.
mark_visible(x, y): 将(x, y)标记为可见。
compute_fov 内部， 我们定义一些局部函数，将scan函数中，不同象限的细节抽象出来。
reveal,
is_wall, 和 is_floor的输入是表示相对位置的 (row, col) 元组。is_blocking
和
mark_visible 的输入是表示绝对位置的 (x, y)元组。
Quadrant 表示一个90度的，指向北，南，东，西的扇面。Quadrants 会逐行遍历. 对于东西象限，"行" 是竖向的，而非横向。
(row, col)
转换为相对原点的绝对位置元组(x, y).
Row对象表示起始斜率和终止斜率之间约束的一段tiles depth 代表该行到坐标原点的距离。tiles 函数返回一个tiles迭代器。
若视野扇区扫描到了该贴图内部的菱形，则认为该贴图在视野内，否则在视野外。若贴图内的菱形在视野扇区外，且只是和视野相切，则同样视为在视野外部。
slope函数计算新的起始斜率和终止斜率。
该函数有两个作用：
prev_tile (左贴图) 是墙体 tile (右贴图) 是地板
， 那么此时 slope 表示 起始 slope 并且应该与墙体贴图右边界相切。 prev_tile 是地板而
在这两种情况里, 视线总是和当前贴图的左边界相切，因此我们可以只用一个 slope 函数来处理 起始slope 和 终止slope。
is_symmetric函数用于检查某个floor tile与视点之间的视野是否具有对称性。
若某个贴图的中心点斜率在起始斜率和终止斜率之间，则返回True，否则返回False。 round_ties_up and round_ties_down 用于将数字舍入到最近的整数,
round_ties_up 向上舍入而 round_ties_down 向下舍入。 注意: round_ties_up 与 Python
的round并不相同. Python 的 round 会将数字向远离0的方向舍入，处理负数时，这会和我们的意图不同.
完整的实现使用了 CC0授权.