algorithm - 二维阴影算法

Question

我正计划制作一款利用光线(和阴影)作为游戏玩法一部分的游戏，但我想不出一种有效的算法来实现它们，我确信有一个优雅的解决方案。

白色区域被光线直接照亮，浅灰色被直接照亮的墙壁照亮，深灰色是黑暗。

我希望以高效的方式找到这些区域。 (实时，光线可以移动)

虽然不现实，但这是我能想到的最简单的问题，欢迎任何其他包括直射光和反射光的实现。

...

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

另请注意，游戏是在 Flash 中，所以我认为我无法使用 gpu。

Answer 1

灵感来自 Ryan 的回答。

在二维网格中，将屏幕的每个点标记为点亮。然后为屏幕上的每一面墙(按接近点的顺序)在它们后面画一个阴影:在去下一堵墙之前，首先检查它的哪些部分被照亮，哪些部分没有，以免两次绘制阴影。标记为下一步绘制阴影的所有墙壁，因为这些墙壁可能已点亮。 (我们应该在下一部分之前再次检查)

对于每个点亮的线段(墙)，首先检查是否有墙与线段相交。对于每个交叉点，在交叉点处将点亮的部分一分为二。

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

第一部分应该遍历屏幕上的所有点和墙上的所有点一次。所以 O(面积 + 墙的长度)，并根据场景的复杂性(墙的数量和交叉点，第二部分应该应用第一部分大约 20 次。

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