一个2D阴影算法

Question

我计划制作一款利用光（和阴影）作为游戏玩法的游戏，但我想不出一个有效的算法来实现它们，我相信有一个优雅的解决方案。

白色区域直接受到光照，浅灰色受到直接照射的墙壁照明，深灰色是黑暗。

我希望以有效的方式找到这些区域。（实时的，光能够移动）

虽然不太现实，但这是我可以想到的问题最简单的方法，任何包括直接光和反射光的其他实现都可以接受。

我的第一次尝试是从光线到屏幕周边画线，并找到它们相交的第一堵墙。但是重复这个算法来标记“环境”光照亮的每个部分的墙是不可行的。

此外，请注意，游戏是在Flash中进行的，因此我认为我无法利用GPU。

- csiz

---

你是否想过那些GPU在忙些什么... 你考虑过使用专有库来高效地访问GPU吗？ - PinnyM

抱歉我没有提到，我也打算用Flash制作这个。 - csiz

你可能想在你的问题中添加一个 flash 标签。这里有一个关于阴影的 flash 相关讨论。 - PinnyM

你会说这个游戏中的灯光是你想要的吗？http://www.kongregate.com/games/Jiggmin/neverending-light - Marty

@PinnyM：只有在存在许多多边形的情况下才是真的。在二维中，特别是在很少的线条情况下，这要简单得多。这远不及三维照明复杂。 - user824425

Answer 1

受Ryan答案的启发。

在2D网格中，将屏幕上的每个点标记为亮。然后对于屏幕上的每堵墙（按距离排序），绘制其背后的阴影，如下所示： 在进入下一面墙之前，首先检查哪些部分被照亮，哪些部分没有被照亮，以免重复绘制阴影。标记所有已绘制阴影的墙壁，作为下一步的可能照亮的墙壁。（我们应该在下一部分之前再次检查）

对于每个亮线段（墙壁），首先检查是否有任何墙壁与该线段相交。对于每个交点，在交点处将亮线段分成两部分。

对于每条线段的端点，在临时数组中重复第一部分，并在最后将所有照亮的点添加到最终数组中。

第一部分应遍历屏幕上的所有点和所有墙上的点一次。因此，时间复杂度为O（区域+墙长），并且根据场景的复杂性（墙数和交叉点数），第二部分应该大约应用第一部分20次。

这可能可以实时工作，但请确保在灯光不移动时存储照亮区域。

- csiz

---

我认为，与其从明亮的区域开始绘制灰色部分，不如假设一切都是黑暗的，然后绘制照亮的部分会更容易些。 - Lie Ryan

那会改善事情，你仍然需要重新绘制一些阴影，但总体上速度会更快。 - csiz

Answer 2

你不需要画出所有的光线，只需要画出重要的部分。例如，对于一个点光源和一条直线，你只需要解决两个交点。

对于反射光照，你可以从一个强度为n的点光源开始，每当这个光线与墙壁相交时，将墙壁分成更小的段，并在被照亮的段上添加一个强度为n-1的线性光源。你可以重复这个过程多次。

- Lie Ryan

---

据我所知，我可以在每条线的后面构建多边形，并填充阴影。然而，这意味着我将不得不为每条线填充大约1/4的屏幕区域。假设有20条线，那就意味着5个屏幕区域。再假设屏幕大小为400600。那就至少需要进行4006005次操作。如果我最初照亮了200个墙壁点，那么我将无法在合理的时间内运行它。相比之下，我的算法涉及向周长的每个点绘制长度为2-300的线段。因此，一个光源需要绘制2000条线段，大约需要进行3002000次操作。 - csiz

如果按照距离源的远近对墙壁进行排序，那么通过检查是否存在更远的墙壁被照亮来构建多边形，算法可以改进以填充屏幕约一次。然而，“半影”仍然是最大的问题，因为即使填充屏幕200次也太困难了。 - csiz

@csiz：线性光源的数学计算只比计算两个点光源稍微复杂一些。屏幕大小和线性光源的长度并不重要。 - Lie Ryan

@Ryan：起初我认为有一些特殊情况不能仅考虑直线，但是通过先检查直线是否相交可以解决这些问题。 - csiz