计算基于图块的游戏中的哪些图块点亮（“光线跟踪”）
我正在写一个基于平铺的小游戏，为此我想支持光源。 但是我的algorithm太弱了，所以我来找你帮忙。
情况是这样的：有一个基于瓦片的地图（作为一个二维arrays），包含一个光源和几个项目。 我想要计算哪些瓦片是由光源点亮的，哪些在阴影下。
大概是什么样子的视觉辅助。 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 XXXX 0 0 0 0 0 - - - - - 0 0 0 - - - - - - - 当然，分数系统会更好，因为部分模糊的情况下，瓷砖可能处于半影状态。 该algorithm不一定要完美 – 只是不明显错误和相当快。
（当然，会有多个光源，但这只是一个循环。）
任何接受者？
roguelike开发社区对视线，视野algorithm有一点点痴迷。
这里有一个关于这个主题的roguelike wiki文章的链接： http ://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision
对于我的roguelike游戏，我在Python中实现了一个阴影投射algorithm（ http://roguebasin.roguelikedevelopment.org/index.php?title=Shadow_casting ）。 把它放在一起有点复杂，但是运行起来非常有效（甚至在纯Python中）并且产生了很好的结果。
“宽容视野”似乎越来越受欢迎： http : //roguebasin.roguelikedevelopment.org/index.php? title=Permissive_Field_of_View
你可以通过计算遮挡等来解决各种复杂问题，也可以使用简单的powershell方法：对于每个单元，使用Bresenham线algorithm等线绘制algorithm来检查当前单元与光源之间的每个单元资源。 如果任何已经被testing过并且被发现在阴影中的细胞或者（如果你只有一个光源的话）细胞，你的细胞就处于阴影中。 如果遇到已知点亮的细胞，您的细胞也将被点亮。 一个简单的优化就是把你所遇到的任何单元格的状态设置为最终的结果。
这或多或less是我在2004年IOCCC获奖作品中使用的 。 显然，这并不是很好的示例代码。 ;）
编辑：正如洛伦指出的，通过这些优化，你只需要select沿着地图边缘的像素来追踪。
这里介绍的algorithm似乎在做比我想象的更多的计算。 我还没有testing过，但我认为它会工作：
最初，将所有像素标记为点亮。
对于地图边缘上的每个像素：如Arachnid所build议的，使用Bresenham从像素到光线追踪一条线。 如果该线遇到障碍物，则将所有像素从边缘标记为超出障碍物的位置。
快速和肮脏：
（取决于数组的大小）
- 循环通过每个瓷砖
- 画一条线
- 如果该线的任何一个点击一个X，那么它在阴影中
- （可选）：计算线经过的X的数量，并进行花式算术以确定阴影中的瓷砖的比例。 注意：在阈值处理过程中，可以通过在瓦片和光线之间消除锯齿线（因此沿着返回到光源的路线查看其他瓦片）来完成这些操作，这些将显示为小的不规则分布。 根据所使用的逻辑，你可以确定瓷砖在阴影中有多less（如果有的话）。
您还可以跟踪哪些像素已经过testing，因此优化一下解决scheme，而不是重新testing像素两次。
通过使用image processing和在像素（瓦片）之间绘制直线，这可能是圆顶非常好如果线是半透明的，并且X块再次是半透明的。 您可以对图像进行阈值判断，以确定该线是否与“X”
如果您有select使用第三方工具，那么Id可能会采取。 从长远来看，它可能会变得更快，但是你对游戏的理解会更less。
这只是为了好玩：
如果您首先执行一个步骤来将您的图块转换为行，则可以在2D中复制Doom 3方法。 例如，
- - - - - - XXX - - XX - - - X - - - - - - - L
…将被缩减为连接三angular形中的立体对象的angular落的三条线。
然后，做Doom 3引擎做的事情：从光源的angular度来看，考虑每个面向光的“墙”。 （在这个场景中，只考虑对angular线）。对于每一条这样的线，将其投影成一个梯形，其前缘是原线，其两侧位于从光源通过每个端点的线上，并且其背面是远远的，过去的整个场景。 所以，这是一个“指向”灯光的梯形。 它包含了墙上投影的所有空间。 把这个梯形的每一块瓷砖都填满黑暗。
继续完成所有这些线路，最终会有一个“模板”，其中包含从光源可见的所有瓦片。 用浅色填充这些瓷砖。 当你远离源（“衰减”）或做其他奇特的事情时，你可能希望点亮一点点。
重复你场景中的每个光源。
要检查瓷砖是否在阴影中，您需要绘制一条直线回到光源。 如果该线与另一个占用的图块相交，那么您正在testing的图块就是阴影。 光线追踪algorithm为视图中的每个对象（在您的案例视图中）执行此操作。
维基百科上的光线跟踪文章有伪代码。
这是一个非常简单但相当有效的方法，它在屏幕上使用线性时间。 每个瓦片都是不透明的或透明的（这是给我们的），每个瓦片都可以是可见的或阴影的（这就是我们正在计算的）。
我们首先将头像标记为“可见”。
然后，我们应用此recursion规则来确定剩余的图块的可见性。
- 如果拼贴与化身在同一行或列上，则只有在邻近化身的相邻拼贴是可见且透明的情况下才可见。
- 如果瓦片与化身之间的angular度为45度，则仅当邻近的对angular瓦片（朝向化身）可见并且透明时才可见。
- 在所有其他情况下，考虑比相关瓦片更接近头像的三个相邻瓦片。 例如，如果这个瓦片在（x，y）处并且在化身的右上方，则要考虑的三个瓦片是（x-1，y），（x，y-1）和（x- 1，y-1）。 如果这三个贴图中的任何一个可见且透明，则可以看到问题贴图。
为了使这个工作，瓷砖必须按照特定的顺序检查，以确保已经计算了recursion情况。 这里是一个工作顺序的例子，从0开始（这是头像本身）并计数：
9876789 8543458 7421247 6310136 7421247 8543458 9876789
相同数量的瓷砖可以按照任意顺序进行检测。
结果不是美丽的阴影投射，而是计算可信的瓦片可见度。
传统知识的解决scheme是你通常会用于这种事情的解决scheme。
对于局部照明的情况，你可以这样做，所以如果一个瓷砖导致在阴影中，该瓷砖然后被分成4个瓷砖，并且每个都被testing。 那么你可以尽可能多地把它分开？
编辑：
你也可以通过不testing与灯光相邻的任何瓷砖来优化它 – 当你有多个光源时，这将是更重要的，我猜…
我其实刚刚写了这个function到我的一个项目中。
void Battle::CheckSensorRange(Unit* unit,bool fog){ int sensorRange = 0; for(int i=0; i < unit->GetSensorSlots(); i++){ if(unit->GetSensorSlot(i)->GetSlotEmpty() == false){ sensorRange += unit->GetSensorSlot(i)->GetSensor()->GetRange()+1; } } int originX = unit->GetUnitX(); int originY = unit->GetUnitY(); float lineLength; vector <Place> maxCircle; //get a circle around the unit for(int i = originX - sensorRange; i < originX + sensorRange; i++){ if(i < 0){ continue; } for(int j = originY - sensorRange; j < originY + sensorRange; j++){ if(j < 0){ continue; } lineLength = sqrt( (float)((originX - i)*(originX - i)) + (float)((originY - j)*(originY - j))); if(lineLength < (float)sensorRange){ Place tmp; tmp.x = i; tmp.y = j; maxCircle.push_back(tmp); } } } //if we're supposed to fog everything we don't have to do any fancy calculations if(fog){ for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){ Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog); } }else{ bool LOSCheck = true; vector <bool> placeCheck; //have to check all of the tiles to begin with for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){ placeCheck.push_back(true); } //for all tiles in the circle, check LOS for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){ vector<Place> lineTiles; lineTiles = line(originX, originY, maxCircle[circleI].x, maxCircle[circleI].y); //check each tile in the line for LOS for(int lineI = 0; lineI < (int) lineTiles.size(); lineI++){ if(false == CheckPlaceLOS(lineTiles[lineI], unit)){ LOSCheck = false; //mark this tile not to be checked again placeCheck[circleI] = false; } if(false == LOSCheck){ break; } } if(LOSCheck){ Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog); }else{ LOSCheck = true; } } } }
那里有一些额外的东西，你不需要，如果你适应自己的使用。 为了方便起见，typesPlace被定义为x和y位置。
线function取自维基百科，修改很less。 我不是打印出xy坐标，而是将其改为返回一个包含所有点的位置向量。 CheckPlaceLOS函数根据瓦片上是否有对象返回true或false。 还有更多的优化可以完成，但这对我的需求是很好的。
我知道这是几年前的问题，但是对于那些寻找这种风格的人来说，我想提供一个我曾经用过的自己的roguelike的解决scheme; 手动“预先计算”FOV。 如果光源视野的距离最大，则手绘阴影所产生的阴影效果并不是很好。 你只需要绘制圆的1/8（加上直线和对angular方向）。 你可以使用对称的其他eigths。 你会有一个圆圈的八分之一有很多的阴影地图。 然后根据物体把它们放在一起。
这三个主要的优点是：1.如果实施正确的话，这是非常快的2.您可以决定如何投射阴影，不用比较哪种algorithm处理哪种情况是最好的3.没有奇怪的algorithm会引起边缘情况，您必须以某种方式修复
con是你真的不能实现一个有趣的algorithm。
如果你不想花时间重新实现这个，那么就有很多游戏引擎。 Ogre3D是一款完全支持灯光以及声音和游戏控制的开源游戏引擎。
我已经在一个C函数中实现了基于tile的视野。 这里是： https ： //gist.github.com/zloedi/9551625
