如何确定 2D 中的可见性

Question

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

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

替代文本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 等效项。