如何确定 2D 可见性

Question

我正在开发一个人工智能沙箱，我想计算每个生物体可以看到的内容。

规则是简单地从实体的角度隐藏形状边缘后面的内容。该图像澄清了一切：

alt 文本 http://img231.imageshack.us/img231/2972 /shadows.png

我需要它作为人工智能的输入，或者以图形方式显示它，以在特定实体移动时显示它。

有什么很酷的想法吗？

Answer 1

李氏算法。它会生成一个多边形，这可能对 AI 的进一步分析有用：

1. 对于每个线段，计算实体与两个端点之间的角度。
2. 按角度对点进行排序。
3. 围绕 360°“扫描”，跟踪哪些线段与扫描线相交。当您越过线段的起始点时，您将该线段添加到集合中；当您越过线段结束点时，您将从集合中删除该线段。
4. 最接近的线段形成可见的多边形。多边形是三角形条的并集。

我意识到这个解释不太好，但我有这里有一个在线演示，您可以尝试一下，了解它是如何工作的。将其扩展到与圆圈一起使用可能还不错（著名的遗言）。

Answer 2

如果您使用简单的形状来阻挡实体的视图，我已经实现了一种简单的方法来执行此操作：

创建一个可以水平或垂直移动的 VisionWave 对象。您可以使用源坐标、与该点相交的两条线以及距源点的距离来定义 VisionWave。

您应该有 4 个波浪：一个向上、一个向下、一个向左、一个向右，定义它们的线的斜率应为 1 和 -1（即 X）。下面我的粗略绘图显示了一个波浪（向右），由 > 字符表示。

  \     /
   \   />
    \ / >
     @  >
    / \ >
   /   \>
  /     \

创建一个循环，每次将每个波传播一个像素。传播波时，您需要执行以下操作：

1. 将波接触的每个像素标记为可见。
2. 如果波接触到的任何像素阻挡了光，那么您需要将波分成两部分，并递归地传播每个像素。

我在 Roguelike 中实现了这样的系统，速度非常快。确保分析您的代码是否存在瓶颈。

如果你很聪明，你可以尝试圆形波而不是直线，但我不知道由于三角计算，它是否会更快。

Answer 3

确定哪些顶点对您的视点可见，然后将这些顶点投影到远离视点的直线上以形成新顶点。闭合形状，您将创建一个代表不可见区域的多边形。

请参阅 阴影体积 了解 3D 等效项。