我正在写一个小瓷砖的游戏，我想为其支持的光源照亮。但是我的算法太弱，所以我来找你帮忙。计算可瓦片在基于区块的游戏（“光线追踪”）
的情况是这样的：有一个基于区块的映射（保持为2D阵列），其包含单个光源和若干项站在附近。我想计算哪些瓦片由光源照亮，哪些瓦片在阴影中。
大概是什么样的视觉辅助。 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 - - - - - - -
小数系统甚至会更好当然，在一个瓦片可以在半阴影的，由于被部分遮蔽。该算法不一定非常完美 - 只是没有明显的错误和相当快的速度。
（当然，会有多个光源，但是这只是一个循环。）
赞成吗？
roguelike开发社区对视线，视野算法有点迷恋。
下面就关于这个问题的roguelike维基文章的链接： 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
快速和肮脏的：
（根据阵列有多大）
您还可以跟踪哪些像素已经过测试，因此优化解决方案一点，而不是重新测试像素两次。
通过使用图像处理和在像素（瓦片）之间绘制直线，这可能会圆顶很好。如果线条是半透明的，并且X块再次是半透明的。您可以门槛的图像，以确定线已经交叉的“X”
如果你必须使用第三方工具选项，然后标识可能采取它。从长远来看，它可能会变得更快，但你对游戏的理解会更少。
要检查瓷砖是否在阴影中，您需要绘制一条直线回到光源。如果该线与另一个占用的图块相交，则您正在测试的图块在阴影中。光线追踪算法为视图中的每个对象（在您的案例视图中）执行此操作。
在维基百科上的Raytracing article有伪。
如果你不想花重塑/重新实现这个的时候，有很多的游戏引擎在那里。 Ogre3D是一款完全支持灯光以及声音和游戏控制的开源游戏引擎。
你可以通过计算遮挡等来解决各种复杂问题，或者你可以使用简单的强力方法：对于每个单元格，使用线条绘制算法（如Bresenham Line Algorithm）来检查当前单元格与光源。如果任何已填充的细胞或（如果您只有一个光源）细胞已经过测试并发现处于阴影中，则您的细胞处于阴影中。如果您遇到已知点亮的细胞，您的细胞也会同时点亮。一个简单的优化就是设置沿线所遇到的任何单元格的状态，以达到最终结果。
这或多或少是我在我的2004 IOCCC winning entry中使用的。显然，这并不是很好的示例代码。 ;）
编辑：正如loren指出的，通过这些优化，您只需要选取沿着地图边缘的像素来追踪。
TK的解决方案是一个你通常会使用这样的事情。
对于部分照明场景，可以这样做，以便如果某个图块导致处于阴影中，则该图块将被拆分为4个图块并对其中的每一个进行测试。那么你可以尽可能多地将它分割出来吗？
编辑：
您还可以通过测试没有任何相邻的光瓷砖的优化它了一点 - 这将当你有多个光源做更重要的是，我猜...
这里所呈现的算法似乎我做更多的计算比我想是必要的。我没有测试过这一点，但我认为这是可行的：
最初，标记所有像素为点亮
对于地图边缘上的每个像素：如Arachnid建议的，使用Bresenham从像素到光线追踪线条。如果该线遇到障碍物，则将所有像素从边缘标记为仅在遮挡物之外，因为它处于阴影中。
关于只使用边缘像素的好处。我认为这实际上是我用过的 - 我清楚地回忆起这段时间太长了。 :) – 2008-10-06 15:29:46
这仅仅是为了好玩：
可以复制在2D的Doom 3的方法，如果你先做一步将你的瓷砖转换成线条。例如，
- - - - -
- X X X -
- X X - -
- X - - -
- - - - L
...将被缩减为连接三角形中实心物体角落的三条线。
然后，做Doom 3引擎的功能：从光源角度考虑，每个面向光的“墙”。（在这个场景中，只考虑对角线）。对于每条这样的线，将其投影成梯形，其前边缘是原始线，其两侧位于从光源通过每个端点的线上，并且其背面是远远的，过去的整个场景。所以，这是一个“指向”灯光的梯形。它包含了墙上投影的所有空间。在这个梯形中填充每个瓦片与黑暗。
继续执行所有这些线条，最终会生成一个“模板”，其中包含所有可从光源看到的贴图。用浅色填充这些瓷砖。你可能希望当你远离源（“衰减”）或做其他花哨的东西时少点点灯。
对场景中的每个光源都重复一次。
我其实刚刚写了这个功能到我的一个项目中。
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;
}
}
}
}
那里有一些额外的东西，如果你将它改编以供自己使用，那就不需要了。为了方便起见，类型Place被定义为x和y位置。
该行功能取自维基百科，修改量很小。我不是打印出xy坐标，而是将其改为返回一个包含该行中所有点的位置向量。 CheckPlaceLOS函数根据瓦片上是否有对象返回true或false。还有更多的优化可以完成，但这对我的需求很好。
这是一个非常简单但相当有效的方法，它在屏幕上的瓦片数量中使用线性时间。每个瓷砖都是不透明的或透明的（这是给予我们的），并且每个瓷砖都可以是可见的或阴影的（这就是我们试图计算的）。
我们首先将头像标记为“可见”。
然后，我们应用此递归规则来确定剩余图块的可见性。
为了做到这一点，必须按照特定顺序检查瓷砖，以确保已经计算出递归情况。这里是一个工作顺序的一个例子，从0开始（这是化身本身）和向上计数：
9876789
8543458
7421247
6310136
7421247
8543458
9876789
瓷砖具有相同数量的可在彼此之间以任何顺序进行检查。
结果并不是美丽的阴影投射，而是计算可信的瓷砖可见度。
我已经在一个C函数中实现了基于tile的视野。这里是： https://gist.github.com/zloedi/9551625
我知道这是几年前的问题，但对于任何人寻找这种风格的东西，我想提供一个解决方案，我曾用过一次我自己的roguelike;手动“预先计算”FOV。如果光源视野的外部距离最大，则手动绘制阻挡对象创建的阴影并不是很费功夫。你只需要绘制圆的1/8（加上直线和对角方向）;你可以使用对称的其他eigths。你将拥有和圆圈1/8的方格一样多的shadowmaps。然后根据物体将它们组合在一起。
造成这种情况的三个主要优点是：1。 这是非常快的，如果实施正确的 2.您有权决定阴影应该如何投，没有比较了该algorith操纵哪些情况下的最佳 3.不怪异algorith引发边缘情况下，你必须以某种方式修复
该con是你真的不会实现一个有趣的算法。
感谢您的所有答案。一旦我回家，我会详细介绍它们并实现/发布算法。 – Zarkonnen 2008-10-06 16:12:29
你有没有在这方面取得进一步的进展？我会很有兴趣听听你是怎么做的。 – 2008-10-14 14:00:37