algorithm - 计算在基于瓦片的游戏中哪些瓦片被点亮 ("raytracing")

Question

我正在编写一个基于图 block 的小游戏，我想为此支持光源。但是我的算法功力太弱了，所以才来找你帮忙。

情况是这样的:有一个基于图 block 的 map (以二维数组的形式保存)，包含一个光源和几个站在周围的项目。我想计算哪些瓷砖被光源照亮，哪些在阴影中。

大致的视觉辅助。 L 是光源，X 是阻挡光线的项目，0 是发光的方 block ，-s 是阴影中的方 block 。

0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -

当然，分数系统会更好，因为瓷砖可能由于部分遮挡而处于半阴影中。该算法不必是完美的 - 只要没有明显的错误并且速度相当快即可。

(当然，会有多个光源，但那只是一个循环。)

有人要吗？

Answer 1

roguelike 开发社区对视线、视野算法有点着迷。

这是一个关于该主题的 roguelike wiki 文章的链接: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

对于我的 roguelike 游戏，我在 Python 中实现了阴影转换算法 ( http://roguebasin.roguelikedevelopment.org/index.php?title=Shadow_casting )。将它组合起来有点复杂，但运行起来相当高效(即使在纯 Python 中)并产生了不错的结果。

“许可视野”似乎也越来越受欢迎: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View