algorithm - 二维阴影算法

Question

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

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

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

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

...

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

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

Answer 1

受瑞恩回答的启发。

在 2d 网格中，将屏幕的每个点标记为点亮。然后为屏幕上的每一面墙（按照靠近点的顺序）在它们后面画一个阴影，如下所示：在去下一堵墙之前，首先检查它的哪些部分被点亮，哪些部分没有，以免两次绘制阴影. 标记为下一步绘制阴影的所有墙壁，因为这些是可能被点亮的墙壁。（我们应该在下一部分之前再次检查）

对于每个点亮的线段（墙），首先检查是否有任何墙与线段相交。对于每个交叉点，在交叉点将点亮的段分成 2 段。

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

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

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

Answer 2

你不需要画所有的光线，只需要画重要的。例如，一个点光源和一个线，你只需要解决两个交叉点。

对于反射照明，您将从强度为 n 的点光源开始，然后每次此光与墙壁相交时，您将墙壁分成更小的部分，并在照明部分上添加强度为 n-1 的线性光源。您可以根据需要多次执行此操作。