从单个光源光线追踪整个 2D 网格

Question

在已知边界的二维网格世界中，有：-

1. 一个光源（蓝色org）
2. 墙壁（灰色）

如何从网格中 每个 白色块的 中心 光线追踪到 中心 org 有效？
对于每个块，我想要一个布尔值 - 它是否点亮。

换句话说，我想确定 org 是否可以直接看到每个块（对于整个世界）。

我的拙劣解决方案

使用标准光线追踪将每个白色块追踪到org，但其性能非常糟糕。感觉很多计算都是多余的

相关 : https://en.wikipedia.org/wiki/Any-angle_path_planning : 该算法仍然针对一个白色块 - 而不是整个世界。

Answer 1

您可以使用 Bresenham's line algorithm or Xiaolin Wu's line algorithm 等直线算法来查找路径中的像素。

1. 从要计算是否点亮的像素点开始
2. 沿光的方向遍历像素。
3. 如果你先打灯，它就会亮。
4. 如果你击中了一个被遮挡的像素，那么它就是黑暗的。

同样可以用于多个灯。这将是高效的，因为您只为每个像素计算一条线。

Answer 2

首先制作一个 std::map 包含成对的 double。这将保持 org 可见的角度范围。最初用 [0,2*PI]

填充它

然后，按照与 org 的距离顺序处理正方形。对于每个正方形：

1. 使用 lower_bound 查找包含从 org 到块中心的角度的范围，如果有的话。如果角度在范围之一内，则块可见。
2. 如果方块是灰色的，则移除、拆分、and/or 调整附近的范围以移除它隐藏方块的角度。

这将在 O(N log N) 时间内工作，这还不错。一旦您对它的工作方式感到满意，您就可以进行一系列优化。最重要的是，如果您按预定义的顺序处理正方形，以便按顺序访问范围集，那么您可以使用向量而不是地图，因为您不必进行搜索。这将使运行时间减少到 O(N)。