algorithm - 计算在基于瓦片的游戏中哪些瓦片被点亮（“光线追踪”）

Question

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

情况是这样的：有一个基于瓦片的地图（以 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 - - - - - - -

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

（当然，会有多个光源，但这只是一个循环。）

有接盘侠吗？

score 22 · Accepted Answer

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 中）并产生了不错的结果。

“Permissive Field of View”似乎也越来越受欢迎： http ://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

score 18 · Accepted Answer

您可以通过计算遮挡等来解决各种复杂问题，或者您可以使用简单的蛮力方法：对于每个单元格，使用线条绘制算法（例如Bresenham Line Algorithm）来检查当前单元格和光线之间的每个单元格来源。如果任何已填充的单元格或（如果您只有一个光源）已经测试并发现处于阴影中的单元格，则您的单元格处于阴影中。如果你遇到一个已知被点亮的牢房，你的牢房同样会被点亮。对此的一个简单优化是将沿线遇到的任何单元格的状态设置为最终结果。

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

编辑：正如 loren 指出的那样，通过这些优化，您只需要选择沿地图边缘的像素即可进行追踪。

score 6 · Accepted Answer

在我看来，这里介绍的算法所做的计算比我认为需要的要多。我没有对此进行测试，但我认为它会起作用：

最初，将所有像素标记为点亮。

对于地图边缘的每个像素：正如 Arachnid 建议的那样，使用 Bresenham 追踪从像素到灯光的线。如果该线碰到障碍物，则将从边缘到障碍物之外的所有像素标记为处于阴影中。

score 5 · Accepted Answer

又快又脏：

（取决于数组的大小）

循环遍历每个图块
给光画一条线
如果线的任何部分击中 X，则它在阴影中
（可选）：计算线穿过的 X 的数量并做一些花哨的数学来确定阴影中瓷砖的比例。注意：这可以通过在阈值处理过程中对瓦片和灯光之间的线进行抗锯齿处理（因此沿着返回光源的路线查看其他瓦片）来完成，这些将显示为小的异常。根据所使用的逻辑，您可能会确定瓷砖在阴影中的程度（如果有的话）。

您还可以跟踪哪些像素已经过测试，因此稍微优化解决方案而不是重新测试像素两次。

如果线条是半透明的并且 X 块又是半透明的，则可以通过使用图像处理和在像素（图块）之间绘制直线来很好地实现圆顶。您可以对图像设置阈值以确定该线是否与“X”相交

如果您可以选择使用 3rd 方工具，那么我可能会接受它。从长远来看，它可能会更快，但您对游戏的了解会更少。

score 4 · Accepted Answer

这只是为了好玩：

如果您首先将瓷砖转换为线条，则可以在 2D 中复制 Doom 3 方法。例如，

- - - - -
- X X X -
- X X - -
- X - - -
- - - - L

...将减少为三条线，连接三角形中固体对象的角。

然后，做 Doom 3 引擎所做的事情：从光源的角度，考虑每一个面向光的“墙”。（在这个场景中，只考虑对角线。）对于每条这样的线，将其投影成一个梯形，其前边缘是原始线，其边位于从光源到每个端点的线上，其背面是远远的，过去的整个场景。所以，它是一个“指向”光的梯形。它包含了墙壁投下阴影的所有空间。用黑暗填充这个梯形中的每一块瓷砖。

遍历所有这些线条，您将最终得到一个“模板”，其中包括从光源可见的所有瓷砖。用浅色填充这些瓷砖。当您远离源（“衰减”）或做其他花哨的事情时，您可能希望稍微点亮瓷砖。

对场景中的每个光源重复此操作。

score 3 · Accepted Answer

要检查瓷砖是否处于阴影中，您需要将一条直线画回光源。如果该线与另一个被占用的图块相交，则您正在测试的图块处于阴影中。光线跟踪算法对视图中的每个对象（在您的情况下为图块）执行此操作。

维基百科上的光线追踪文章有伪代码。

score 3 · Accepted Answer

Here is a very simple but fairly effective approach that uses linear time in the number of tiles on screen. Each tile is either opaque or transparent (that's given to us), and each can be visible or shaded (that's what we're trying to compute).

We start by marking the avatar itself as "visible".

We then apply this recursive rule to determine the visibility of the remaining tiles.

If the tile is on the same row or column as the avatar, then it is only visible if the adjacent tile nearer to the avatar is visible and transparent.
If the tile is on a 45 degree diagonal from the avatar, then it is only visible if the neighboring diagonal tile (towards the avatar) is visible and transparent.
In all other cases, consider the three neighboring tiles that are closer to the avatar than the tile in question. For example, if this tile is at (x,y) and is above and to the right of the avatar, then the three tiles to consider are (x-1, y), (x, y-1) and (x-1, y-1). The tile in question is visible if any of those three tiles are visible and transparent.

In order to make this work, the tiles must be inspected in a specific order to ensure that the recursive cases are already computed. Here is an example of a working ordering, starting from 0 (which is the avatar itself) and counting up:

Tiles with the same number can be inspected in any order amongst themselves.

The result is not beautiful shadow-casting, but computes believable tile visibility.

score 2 · Accepted Answer

TK 的解决方案是您通常用于此类事情的解决方案。

对于部分照明场景，您可以使用它，这样如果一个图块导致处于阴影中，那么该图块会被分成 4 个图块，并且每个图块都经过测试。然后，您可以根据需要将其拆分多少？

编辑：

您也可以通过不测试与灯光相邻的任何瓷砖来对其进行一些优化 - 我猜当您有多个光源时，这样做会更重要......

score 2 · Accepted Answer

实际上，我最近才将此功能写入我的一个项目中。

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 位置。

The line function is taken from Wikipedia with very small modifications. Instead of printing out x y coordinates I changed it to return a place vector with all the points in the line. The CheckPlaceLOS function just returns true or false based on if the tile has an object on it. There's some more optimizations that could be done with this but this is fine for my needs.

score 2 · Accepted Answer

I know this is years old question, but for anyone searching for this style of stuff I'd like to offer a solution I used once for a roguelike of my own; manually "precalculated" FOV. If you field of view of light source has a maximum outer distance it's really not very much effort to hand draw the shadows created by blocking objects. You only need to draw 1/8 th of the circle (plus the straight and diagonal directions); you can use symmerty for the other eigths. You'll have as many shadowmaps as you have squares in that 1/8th of a circle. Then just OR them together according to objects.

The three major pros for this are: 1. It's very quick if implemented right 2. You get to decide how the shadow should be cast, no comparing which algorith handles which situation the best 3. No weird algorith induced edge cases which you have to somehow fix

The con is you don't really get to implement a fun algorithm.

score 1 · Accepted Answer

i have implemented tilebased field of view in a single C function. here it is: https://gist.github.com/zloedi/9551625

score 0 · Accepted Answer

如果您不想花时间重新发明/重新实现它，那里有很多游戏引擎。 Ogre3D是一个开源游戏引擎，完全支持灯光，以及声音和游戏控制。

algorithm - 计算在基于瓦片的游戏中哪些瓦片被点亮（“光线追踪”）

12 回答 12

Related

Reference