如何确定2D中的可见性

Question

我正在开发一个AI沙箱,我想计算每个生活实体可以看到的东西.

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

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

我需要它作为人工智能的输入或图形化,以便在移动时为特定实体显示它.

有什么好主意吗？

Answer 1

这不是最快的算法,但它产生的多边形可能对您的AI进一步分析有用:

1. 对于每个线段,计算实体与两个端点之间的角度.
2. 按角度对点进行排序.
3. "Sweep" around 360°, keeping track of which line segments intersect with the sweep line. When you cross the beginning-of-segment point, you add that segment to the set; when you cross the end-of-segment point, you remove that segment from the set.
4. The closest line segments form a polygon of what's visible. The polygon is the union of triangle slivers.

I realize this explanation isn't great, but I have an online demo here that you can play with to get a sense for how it works. Extending it to work with circles probably isn't too bad (famous last words).