计算在基于图块的游戏中点亮哪些图块("光线跟踪")

Question

我正在写一个基于平铺的小游戏,为此我想支持光源.但是我的算法太弱了,所以我来找你帮忙.

情况是这样的:有一个基于图块的地图(作为二维阵列保存),包含一个光源和几个站在周围的物品.我想计算哪些瓷砖被光源点亮,哪些瓷砖处于阴影中.

大约是它的外观的视觉辅助.L是光源,X是阻挡光线的项目,0是点亮的瓷砖,-s是阴影中的瓷砖.

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

Answer 2

您可以通过计算遮挡等来解决各种复杂问题,或者您可以选择简单的强力方法:对于每个单元格,使用线绘制算法(如Bresenham线算法)检查当前单元格与光线之间的每个单元格资源.如果任何已填充的单元格或(如果您只有一个光源)已经过测试并发现处于阴影中的单元格,则您的单元格处于阴影中.如果您遇到已知点亮的电池,您的电池也会被点亮.对此进行简单的优化是将沿线遇到的任何单元格的状态设置为最终结果.

这或多或少都是我在2004年IOCCC获奖作品中使用的.但显然,这并不是很好的示例代码.;)

编辑:正如洛伦指出的那样,通过这些优化,您只需要沿着地图边缘选择要跟踪的像素.

Answer 3

这里提出的算法似乎比我认为需要做更多的计算.我没有测试过这个,但我认为它会起作用:

最初,将所有像素标记为已点亮.

对于地图边缘的每个像素:正如Arachnid建议的那样,使用Bresenham来跟踪从像素到光线的线条.如果该线撞击障碍物,则将所有像素从边缘标记为刚好在阴影之外的障碍物.

Answer 4

又快又脏:

(取决于阵列的大小)

• 循环遍历每个图块
• 在Light上划一条线
• 如果线的任何一个pary击中X,那么它就在阴影中
• (可选):计算线经过的X量,并进行花式数学计算以确定阴影中瓷砖的比例.注意:这可以通过对瓦片和光线之间的线进行抗锯齿来进行(因此在阈值处理过程中查看沿着路径返回光源的其他瓦片)这些将显示为小的异常.根据所使用的逻辑,您可能会确定瓷砖在阴影中的数量(如果有的话).

您还可以跟踪已测试的像素,因此稍微优化解决方案,而不是重新测试像素两次.

通过使用图像处理和在像素(瓦片)之间绘制直线,这可能是圆顶很好.如果线条是半透明的并且X块再次是半透明的.您可以对图像进行阈值处理以确定线条是否与"X"相交

如果您可以选择使用第三方工具,那么Id可能会接受它.从长远来看,它可能会变得更快,但你对游戏的了解较少.