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

Question

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

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

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

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

我的糟糕解决方案

使用标准的光线追踪来追踪每一个白块org，但它的性能很差。我觉得很多计算都是多余的。

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

标签： language-agnosticartificial-intelligencepath-findingraytracing

Answer 1

您可以使用诸如Bresenham 的线算法或Xiaolin Wu 的线算法之类的线算法来查找路径中的像素。

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

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