在网格平铺地图中优化视野算法 [英] Optimize field of vision algorithm in a grid tiled map

问题描述

我正在尝试在我的游戏中实现视野算法，并且在这里遵循了很棒的教程:

如您所见，它对我来说效果很好:)

然后我尝试在平铺地图中使用此算法.它也可以正常工作，但速度稍慢，所以我现在尝试寻找一种优化算法的方法.

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

• 平铺的地图是正交的
• 所有图块的大小均相同，为32 * 32，均为正方形
• 标记为0的空格表示标记为1的空格表示障碍物
• 我已使用Connected Component Labeling算法进行预处理:
  • 所有障碍都已合并为多个区域
  • 我知道每个区域中所有顶点的位置

类似这样的东西:

说我有9个连通区域(9个多边形)和总共40个顶点.

根据上面链接中的算法，将会有:

• 射线投射:40 * 3(每个顶点3个射线投射的角度为+-0.00001)
• 边缘:40
• 边缘*射线相交测试:40 * 40 * 3 == 4800

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

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

解决方案

您正在做的事情可以得到很多优化.首先，没有必要使用所有顶点，也不需要进行任何交集测试.

获取每个多边形.对于每个顶点，请确定它是否是一个反转点.那就是从原点/眼睛获取光线，并检查邻居是否在同一侧.找出哪个方向朝着原点，然后跟随它直到找到另一个反转点.这些点之间的线段是面向原点/眼睛的线段.如果您有凸形，则只有两个，对于更复杂的形状，可以有更多.

接下来，将所有反演点转换为极坐标，并按角度对其进行排序.现在，您应该有一堆可能重叠的间隔(注意变形360-> 0).如果您的场景很简单，则间隔不会重叠，因此只需要在灯光下跟随多边形即可(无需测试).如果遇到重叠，请从现有间隔中获取反转点和当前边，并查看反转点是否与原点/眼睛在同一侧.如果是这样，则可以将光线与当前边缘相交到反转点以获取远点，并将其与反转点链接，该反转点现在将替换为当前边缘.如果存在不属于任何多边形的间隔，则光线将变为无穷大(该多边形中的所有光线都看不到).

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

因此，在您的情况下，您将仅获得9 * 2的反转点(您的多边形很简单)，并且您需要进行很少的边线*射线相交，因为它们的布局相当稀疏并且算法很快就丢弃了明显的非相交点案例.

如果这是用于某些实时应用程序，则可以利用以下事实进一步优化它:反转点基本保持不变，并且如果它们发生变化，它们通常沿着多边形沿一条边移动(如果多边形较小，则移动距离较大).

I am trying to implement Field of View algorithm in my game and I followed the great tutorial here : sight-and-light and here is what I got so far :

As you can see it works fine for me :)

And then I try to use this algorithm in a tiled map. It also works fine but just a little bit slow so I am now trying to find a way to optimize the algorithm.

Some information might help to optimize :

• The tiled map is Orthogonal
• All the tiles have the same size 32 * 32 and are square
• Tiles marked 0 means empty marked as 1 means a obstacle
• I have used Connected Component Labelling algorithm for a preprocess :
  • All the obstacles have been merged into several regions
  • I know all the vertices position in each regions

Something like this :

Say I have 9 connected regions ( 9 polygons ) and 40 vertices in total.

Based on the algorithm in the above link, there will be :

• ray-cast : 40 * 3 ( 3 ray-cast per vertices in angle +- 0.00001)
• edges : 40
• edge * ray-cast intersection test : 40 * 40 * 3 == 4800

I think there should be a way to reduce the ray cast count and the edges count that I need to do the intersection calculation in a above situation but just could not figure out a good solution.

Any suggestion will be appreciated, thanks :)

解决方案

What you are doing can be optimized a great deal. First there's not point in using all the vertices and no need to do any intersection tests.

Take each polygon. For each vertex figure out if it's an inversion point. That is take the ray from the origin/eye and check if the neighbor are on the same side. Figure out which direction goes towards the origin and follow it until you find another inversion point. The segment in between these point are the ones facing the origin/eye. If you have a convex shape there's only 2 of them, for more complex ones there can be more.

Next convert all the inversion point to polar coordinates and sort them by the angle. Now you should have a bunch of possibly overlapping intervals (take care about the warparound 360->0). If you scene is simple the intervals are non overlapping, so you only need to follow your polygons with the light (no tests needed). If you have encounter an overlap, take the inversion point and the current edge from the existing interval and see if the inversion point is on the same side as the origin/eye. If so then you can intersect the ray to the inversion point with the current edge to get the far point and link it with the inversion point which will now replace as the current edge. If there's an interval that doesn't belong to any polygon the rays will go to infinity (there's nothing to see for all rays in that polygon).

This works for all non-overlapping polygons.

So in your case you will get only 9*2 inversion points (your polygons are simple) and you need to do very few edge * ray intersections because their layout is fairly sparse and the algorithm is quick to discard obvious non-intersecting cases.

If this is for some real-time application you can optimize it further by taking advantage of the fact that the inversion points mostly remain the same, and if they change they travel along the polygon usually one edge (could be more if the polygon is small the the move distance is large).

这篇关于在网格平铺地图中优化视野算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！