如何查找对象看不到的网格单元格

我正在写一个VB.NET程序。

我有一个网视图,它是由多个称为网格单元的小单元组成的。

在网格视图中,我放置了一个障碍(红色框)和一个观察者(蓝色框)。

我的任务是find如何find蓝框看不到的网格单元格。 你可以参考下面的截图。

如何在黄色框中定位网格单元格?

请注意,黄色方块形状不是必需的。

1)我已经考虑遍历网格视图中的所有网格单元格,并检查它们是否被蓝框看到。

但是,在网格视图中可能会有数百万个网格单元,并且循环遍历每个网格单元会花费大量时间并且效率不高。

除了在视图中的所有网格单元中循环以外,还有没有更好的方法来定位网格单元格,而不是通过蓝色框显示?

谢谢。

您尚未指定要查找的输出types。 如果真的有数百万个网格单元看不见,find它们都必然需要处理数百万个网格单元。 所以你需要限制你的algorithmfind这些的一个子集,例如:

  1. 根据需要查找是否看不到单个细胞
  2. 在距观察者一定距离内find所有看不见的细胞
  3. 寻找最近的看不见的细胞

第一个很简单:在单元和观察者之间进行一个单一的视线testing。

第二个也很简单,只需对整个网格的一个子集进行视线testing即可。 Eric Lippert的Shadowcastingalgorithm是一个不错的方法,它可以最大限度地减less重新访问的单元格,但是我发现了一个非常简单的algorithm,可以对边界单元进行视线testing。

对于第三个,您可以重复执行从离观察者最近的细胞开始的视线testing,并逐渐向外search,例如以螺旋模式。 根据你的algorithm,你可以避免不必要的unit testing的重复 – 例如,如果一个方向相同且靠近观察者的单元被看到,我们可以假定当前单元也被观察者看到,并且避免执行完整的testing一直到观察者。 你可能仍然想限制这个search,因为如果观察者处于空场的中间,那么最近的看不见的单元可能会很远,你将不得不search很多单元。 如果你的网格特别稀疏,你可以尝试基于射线的方法search障碍物而不是单元格。

对于网格问题,我通常使用集群,而不是在单个单元格上运行,例如组5×5单元格,并通过这样的集群进行循环。 因此,不是循环遍历每个单元格,只要满足某些集群可见条件,就可以遍历由多个单元格构成的单元格集群,并循环遍历集群中的单元格。 进一步,您可以创建一个群集群并recursion地重复这个操作。

您可以search有关四叉树的更多信息: https : //en.wikipedia.org/wiki/Quadtree

你可能有一种方法可以将你的网格划分成更大的片断,并将片断的可视性确定为捷径。 例如,如果一个更大的块(比如8×8的单元组)不可见(检查4个角),则可以将整个单元格标记为不可见。

我没有尝试过,但我认为这样的事情会工作…

把你的整个网格,并把它分成宿舍。 通过检查是否可以看到该季度的任何角落来确定每个季度的可见性。 如果看不到任何角落,则将整个季度的单元格标记为不可见。 如果四分之一的任何角落都可见,则至less有一部分是可见的。 在这种情况下,recursion地将该季度分成几个小部分,并重复这个过程。