网格贴图中的视觉优化算法

Question

我正在尝试在我的游戏中实现视场算法，我在这里学习了一个很棒的教程：光与视，这是我到目前为止得到的结果：

​

​

如你所见，它对我来说很好:)

然后我试着在平铺地图上使用这个算法。它也很好，但只是有点慢，所以我现在试图找到一种方法来优化算法。

一些信息可能有助于优化：

• 平铺地图是正交的。
• 所有的瓷砖都是一样大小的32 * 32并且是方形的。
• 标记为0的瓷砖表示空标记为1表示障碍物
• 我在预处理中使用了连接组件标记算法：。
  • 所有的障碍都被并入了几个地区。
  • 我知道每个地区的所有顶点位置

​

就像这样：

​

​

假设我有9个连通区域(9个多边形)和40个顶点。

根据上述链接中的算法，将有：

• 射线投射: 40 *3( +- 0.00001角的每个顶点3次射线投射)
• 边缘: 40
• 边缘*射线投射交叉试验: 40 * 40 *3 == 4800

我认为应该有一种方法来减少光线投射计数和边缘计数，在上述情况下，我需要做交集计算，但无法找到一个很好的解决方案。

如有任何建议，将不胜感激:)

Answer 1

你正在做的事情可以得到很大的优化。首先，使用所有顶点没有意义，也不需要做任何交集测试。

取每一个多边形。对于每个顶点，求出它是否是一个反转点。也就是说，从原点/眼睛获取光线，并检查邻居是否在同一一侧。找出指向原点的方向，然后沿着它走，直到你找到另一个反转点。在这两个点之间的部分是面向原点/眼睛的部分。如果你有一个凸的形状，只有两个，对于更复杂的，可以有更多。

接下来，将所有的反演点转换为极坐标，并按角度对它们进行排序。现在，您应该有一堆可能重叠的间隔(请注意warparound 360->0)。如果你的场景是简单的，间隔是不重叠的，所以你只需要跟随你的多边形与光(不需要测试)。如果遇到重叠，请从现有区间取反演点和当前边缘，看看倒置点是否与原点/眼在同一一侧。如果是这样的话，那么你可以将射线与当前边缘交叉到反转点，得到远点，并将其与反转点连接起来，后者现在将被替换为当前边缘。如果有一个不属于任何多边形的间隔，光线就会无限大(该多边形中的所有射线都看不见)。

这适用于所有不重叠的多边形。

因此，在你的情况下，你只会得到9*2个反转点(你的多边形很简单)，你需要做很少的边缘*射线交叉，因为它们的布局相当稀疏，而且算法很快就会丢弃明显的非相交的情况。

如果这适用于某些实时应用程序，您可以利用以下事实进一步优化它:反转点大部分保持不变，如果它们变化，则沿着多边形(通常是一个边)移动(如果多边形较小，移动距离很大，则可能更多)。