基于栅格的可见性分析

在我之前的文章 使用帕斯卡三角形进行短距离直接步行 中，我解释了如何改进基于网格的寻路，以在不使用视线测试的情况下产生高度直接的步行路径。 这篇后续文章将向你展示一种称为基于网格的可见性的相关技术，该技术无需视线测试即可计算可见区域。 基于网格的可见性在计算机科学界几乎闻所未闻，但它是一种对各种人工智能应用有意义的实用方法。 它也非常容易实现，只需 3 行代码。 继续阅读，发现解决视频游戏、移动机器人或建筑设计中可见性问题的最简单选择。

1、可见区域问题

与寻路类似，可见性分析出现在涉及人工智能和空间环境的许多领域。 视频游戏开发者可能想要计算从敌方瞭望塔可见的游戏地图区域。 移动机器人工程师可能需要在测试机器人控制系统的模拟中计算机器人的视野。 建筑师可能想要分析人们在建筑物内或街道上不同位置的视野。 可见性分析还可用于估算光源照射的区域。

基本问题是：给定一个 2D 自顶向下地图，计算从一个点可见的空间区域。

如果你问计算机科学家如何解决这个问题，他们极不可能考虑我所说的基于网格的算法：一种根据相邻网格单元中的数字计算每个网格单元中的数字的方法。 可见区域问题几乎总是使用涉及视线测试的基于矢量的可见性算法来解决。 最流行的基于矢量的可见性技术之一是光线投射，其中从视点向不同方向投射大量光线。 如果你不熟悉光线投射和其他基于矢量的可见区域问题解决方案，有关 2D 可见性的 Red Blob Games 教程提供了出色的背景知识。

基于网格和基于矢量的方法在寻路和 2D 图形等其他空间应用中都很流行。 例如，我们都熟悉光栅（基于网格）和矢量图像，并且我们认识到这两种类型的图像都有优点和缺点。 那么为什么只有基于向量的方法才被广泛用于可见性呢？ 我开始相信，虽然基于网格和基于矢量的方法对于可见性问题各有优缺点，但基于网格的可见性却被奇怪地忽视了，值得更好地了解。

1、基于栅格的可见性

这是用 3 行 Python 代码编写的基于网格的可见性。

for x in range(grid.shape[0]):
    for y in range(int(x==0), grid.shape[1]):
        grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

该算法采用代表地图的网格并对其进行修改以产生可见性结果。 正如我们所看到的，转换包括循环每个网格单元并应用线性插值。 让我们将这 3 行代码放在一个简短的程序中来测试它们。 请随意复制并运行下面的 Python 脚本。

import numpy as np
import matplotlib.pyplot as plt

# Set dimensions
nx = 25
ny = 25

# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0

# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))

# Compute visibility
for x in range(grid.shape[0]):
    for y in range(int(x==0), grid.shape[1]):
        grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

该程序首先创建并显示地图，这是一个 25x25 网格，其中充满障碍物的单元格的值为 0，空单元格的值为 1。如下所示，地图有三个方形障碍物。

然后，程序将地图转换为可见性网格并显示它。 可见性网格填充有可见性分数，其近似于从左上角的视点可见每个网格单元的程度。 可见性分数范围从 0（完全阻挡）到 1（完全可见）。 这是可见性网格。

每个障碍物都会从左上角投射出阴影，尽管你会注意到阴影的边缘是模糊的。 锐化这些边缘的一种方法是提高地图的分辨率。 如果我们将两个维度的网格大小从 25 个单元格更改为 225 个单元格……

nx = 225
ny = 225

......我们得到以下结果：

在这里我们看到更清晰、更准确的阴影。 如果我们继续提高分辨率，可见度分数将会变得越来越准确。 事实上，当网格间距接近零时，结果将收敛于精确解。

根据应用程序，我们可能希望将每个网格单元分类为可见（1）或不可见（0）。 我们可以通过在循环后应用 0.5 的阈值来做到这一点。

for x in range(grid.shape[0]):
    for y in range(int(x==0), grid.shape[1]):
        grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
grid[:] = (grid >= 0.5)

将第四行插入到脚本中将得到以下结果：

重要的是要记住，基于网格的可见性是一种近似方法。 一些网格单元可以被分类为可见，即使它们应当恰好在阴影内，并且一些网格单元可以被分类为阻塞，即使它们应当仅仅在可见区域内。 但一般来说，如果网格间距与障碍物及其之间的间隙相比较小，则结果应该具有不错的准确性。

在我们继续之前，我应该承认我使用了一些技巧将算法减少到 3 行：

• 第二个 for 循环中的表达式 int(x==0) 是一个巧妙的技巧，它会跳过网格单元 [0, 0]，其中插值公式会产生被零除的错误。
• 我依赖的事实是 NumPy 库允许使用负索引访问数组。 其他编程语言可能需要更多行代码来检查这种情况。
• 上面的所有代码都假设视点位于地图的角落。 将视点移动到坐标为 x0 和 y0 的任意单元格需要重复计算四次，每个象限一次。

要将视点放置在地图中心，请将脚本的计算可见性部分中的代码替换为以下内容：

# Set viewpoint
x0 = nx//2
y0 = ny//2

# Define visibility function
def visibility_from_corner(grid):
    for x in range(grid.shape[0]):
        for y in range(int(x==0), grid.shape[1]):
            grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

# Compute visibility
visibility_from_corner(grid[x0:,y0:])
visibility_from_corner(grid[x0::-1,y0:])
visibility_from_corner(grid[x0::-1,y0::-1])
visibility_from_corner(grid[x0:,y0::-1])

以下是视点位于中心的结果：

2、Excel 的巧妙技巧

这里有一个我无法抗拒的小技巧：在 Excel 中实现基于网格的可见性：

想亲自尝试一下吗？ 请按照以下说明进行操作。 应该只需要 1 或 2 分钟。

• 打开 MS Excel 并创建一个空白工作簿。
• 选择单元格 B2，单击公式栏（或按 F2），粘贴以下文本，然后按 Enter：
  =((COLUMN(B2)-2)*A2+(ROW(B2)-2)*B1)/((COLUMN(B2)-2)+(ROW(B2)-2))
• 重新选择单元格 B2，按 Ctrl-C 进行复制，选择从 B2 到 Z26 的单元格范围，按 Ctrl-V 进行粘贴。
• 在“主页”选项卡中，选择“条件格式”、“突出显示单元格规则”、“小于”。 在第一个框中输入 0.5（“设置小于的单元格格式”），然后从右侧的下拉菜单中选择任何“填充”选项（例如“用深红色文本填充浅红色”）。 单击“确定”。
• 选择单元格 B2，然后按 1，然后按 Enter。
• 通过单击单元格 A1 上方和左侧的绿色三角形来选择所有单元格，然后单击并拖动 A 和 B 之间的垂直线以缩小单元格宽度，使所有单元格最终近似为正方形。
• 通过单击单元格并按 Backspace 键来创建障碍物。 从左上角延伸出去的阴影应该会自动出现。

观察到障碍物需要多个单元宽才能产生合理的阴影。

3、基于网格的可见性简史

基于网格的可见性的历史解释了为什么该方法从未获得广泛认可。 首先，尽管基于网格的可见性很简单，但它直到 2004 年才被发明 [2]，并且它的收敛特性直到 2008 年才被确立 [3]。 到那时，光线投射等基于矢量的方法已经变得无处不在。 计算机科学家不再寻找竞争方法。 其次，第一篇关于基于网格的可见性的论文来自称为水平集理论的数学分支，其中几何以大多数计算机科学家不熟悉的隐式方式表示。 虽然水平集可见性方法适用于 2D 或 3D 并使用线性插值，但建筑和城市信息学研究人员于 2013 年开发了一种使用双线性插值的严格 3D 替代方法 [4]。

2019 年左右，我和我的同事对基于网格的可视性产生了兴趣，将其作为分析大量计算机生成的建筑设计的手段。 在我们的开放获取期刊论文“基于网格的导航的路径计数”[1] 中，我们做出了以下观察：

• 原始水平集可见性方法很容易适应计算机科学家熟悉的显式几何。 本文顶部附近的 Python 代码是将原始插值公式与显式基于网格的几何结构相结合的实现示例。
• 可以增加网格邻域的大小以产生更准确的结果。 到目前为止，本文中的示例使用了 4 邻域，其中信息流向北、南、东和/或西。 我和我的同事在论文和名为 SpaceAnalysis 的建筑设计工具中都使用了 8 邻域，它允许信息对角流动。
• 基于网格的可见性结果可以使用概率论（特别是中心极限定理）收敛于精确解。 水平集社区的原始证明使用了数值分析[3]。
• 线性插值产生的可见度分数可以重新解释为远离视点且未被障碍物阻挡的最短网格路径的分数。

最后的观察表明，基于中心网格的寻路（本文和我之前的 Medium 文章的主题）与基于网格的可见性基于相同的基础数学。 事实上，可以通过简单地计算路径来计算可见区域。

为了通过计数来证明可见性，我们将像以前一样假设视点位于左上角。 我们首先在那个角落放置一个 1，然后重复向下和向右复制数字。 当两个数字汇聚在同一个网格单元上时，我们将它们加在一起。 结果是每个网格单元都包含远离视点并最终到达该单元的网格路径的数量。 例如，从视点到右下角有742条这样的路径。

在我们的计数寻路方法中，我们采用了两组路径计数并将它们相乘。 在通过计数可见性中，我们获取两组路径计数并进行划分。 获取每个网格单元的实际路径数（上面的第一个动画），然后除以该单元的最大可能路径数（第二个动画），我们最终得到每个网格单元的可见性得分。 然后，如果每个单元格的得分至少为 0.5，我们将其分类为可见。 例如，在可能的 2002 条网格路径中，有 742 条到达右下角的单元格。 其可见性分数为 472/2002，或大约 0.37，并且被分类为不可见。

我们在论文中再次证明，通过计数计算出的可见度分数在数学上等同于原始插值公式产生的可见度分数。 换句话说，这两种方法都是解决可见区域问题的可行方法。 然而，如果我们选择通过计数来实现可见性，我们必须记住路径计数随着距离呈指数增长。 如果我们使用 64 位浮点数表示这些计数，则在从视点移动达到 1030 个网格后，路径计数将溢出。 因此，我认为在实现基于网格的可见性时默认使用线性插值方法是有意义的。 同时，我觉得与路径计数的联系很有趣，值得分享。

4、较大的邻域

对于基于网格的可见性，你可能担心的一个问题是其准确性，特别是因为某些基于矢量的可见性方法被认为可以为可见区域问题提供精确的解决方案。 以下是精确解的现实情况：只有输入几何形状精确时，它们才是精确的，但在实践中很少出现这种情况。 当对现实环境的模型执行可见性分析、寻路分析或任何类型的空间分析时，由于离散误差、测量误差以及在某些情况下的构造误差，模型几乎总是近似值。 事实上，基于网格的可见性引入了一些额外的错误，这可能是也可能不是一个严重的缺点，具体取决于应用程序。

话虽如此，有一种方法可以在不增加网格分辨率的情况下提高基于网格的可见性结果的准确性。 到目前为止，我们的示例仅使用了 4 邻域，这是最简单但精度最差的 2D 网格邻域。 如前所述，我们可以选择更大的网格邻域以获得更准确的结果。 下图描绘了矩形网格的 4、8 和 16 邻域，以及三角形网格的 6 和 12 邻域。

为了查看更大邻域的效果，我们将重写本文顶部的 Python 脚本。 在该程序的这个新版本中，visibility_within_cone 函数计算由两个向量包围的圆锥体内的可见性分数。 这可能不是最有效的实现，但它将帮助我们理解过渡到更大的网格邻域意味着在更多数量的细锥体中应用相同的算法。

import numpy as np
import matplotlib.pyplot as plt

# Set dimensions
nx = 25
ny = 25

# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0

# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))

# Define visibility function
def visibility_within_cone(grid, u_direction, v_direction):
    u = np.asarray(u_direction, dtype=int)
    v = np.asarray(v_direction, dtype=int)
    origin = np.array([0,0], dtype=int)
    dims = np.asarray(grid.shape, dtype=int)
    m = 0
    k = 0
    position = np.array([0,0], dtype=int)
    while np.all(position < dims):
        while np.all(position < dims):
            if not np.all(position == 0):
                pos = tuple(position)
                pos_minus_u = tuple(np.maximum(origin, position - u))
                pos_minus_v = tuple(np.maximum(origin, position - v))
                grid[pos] *= (m*grid[pos_minus_u] + 
                              k*grid[pos_minus_v]) / (m + k)
            k += 1
            position += v
        m += 1
        k = 0
        position = m*u

# Compute visibility
visibility_within_cone(grid, [1,0], [0,1])

# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

由于我们使用向量 [1,0] 和 [0,1] 调用该函数，因此我们仍然使用 4 邻域。 结果与我们的第一个脚本产生的结果相同。

但现在我们可以轻松修改代码以使用 8 邻域。 为此，请将计算可见性部分中的代码替换为以下代码。 可见性函数现在应用两次，第一次在对角线 [1,1] 和网格轴 [1,0] 之间的圆锥体内，然后在 [1,1] 和 [0,1] 之间。

# Compute visibility
visibility_within_cone(grid, [1,1], [1,0])
visibility_within_cone(grid, [1,1], [0,1])

以下是 8 邻域的结果。 阴影边缘变得锐利。

最后，我们可以通过在 4 个锥体内应用可见性函数来过渡到 16 邻域。

# Compute visibility
visibility_within_cone(grid, [2,1], [1,0])
visibility_within_cone(grid, [2,1], [1,1])
visibility_within_cone(grid, [1,2], [1,1])
visibility_within_cone(grid, [1,2], [0,1])

以下是 16 个邻域的结果。

16 邻域似乎可以为大多数应用提供足够的精度。 但是，如果需要更高质量的结果，可以继续升级到 32 邻域、64 邻域等。

这会处理矩形网格。 三角形网格，也称为六角形网格，实现起来比较棘手，因为没有理想的方法来索引网格单元。 有关六角网格的 Red Blog Games 教程中描述了各种索引策略，其中包括有关使用视线测试的可见性的部分。 我将在三角形网格上实现基于网格的可见性作为对您的挑战。

5、结束语

基于网格的可见性是光线投射和其他基于矢量的可见性方法的简单实用的替代方案。 由于其发现的时间和背景，计算机科学家对这种方法仍然知之甚少。 但我希望你会同意，现在是基于网格的可见性变得可见的时候了，并且我希望你能找到机会在自己的人工智能项目之一中使用它。

原文链接：A Quick and Clear Look at Grid-Based Visibility

BimAnt翻译整理，转载请标明出处