如何确定2D中的可见性

Question

我正在开发一个人工智能沙箱，我想计算每个活着的实体都能看到什么。

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

alt text http://img231.imageshack.us/img231/2972/shadows.png

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

有什么好主意吗？

Answer 1

如果你使用简单的形状来遮挡实体的视图，有一个简单的方法可以做到这一点，我已经实现了：

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

你应该有4个波:一个向上，一个向下，一个向左，一个向右，定义它们的线的斜率应该是1和-1 (即X)。我下面的粗略图画显示了由>字符表示的一个波(向右)。

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

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

1. 将波接触的每个像素标记为可见。
2. 如果波接触的任何像素阻挡光线，则需要将波一分为二，并递归传播每个像素。

我实现了一个这样的系统在我的流氓，它是非常快的。确保分析你的代码是否存在瓶颈。

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

Answer 2

这不是最快的算法，但它产生了一个多边形，这可能对你的AI的进一步分析有用：

对于每个线段，通过角度计算实体和两个扫描点之间的角度。

• 在360°左右“扫描”，跟踪哪些线段与扫描线相交。当你穿过线段起始点时，你将该线段添加到集合中；当你穿过线段结束点时，你从集合中删除了该线段。

• 最近的线段形成了一个可见的多边形。多边形是三角形长条的并集。

我知道这个解释不是很好，但是我有an online demo here，你可以使用它来了解它是如何工作的。将它扩展到与circles一起工作可能不是太糟糕(著名的最后一句话)。

​

​

Answer 3

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

有关3D等效项，请参见shadow volumes。