47

I'm writing a little tile-based game, for which I'd like to support light sources. But my algorithm-fu is too weak, hence I come to you for help.

The situation is like this: There is a tile-based map (held as a 2D array), containing a single light source and several items standing around. I want to calculate which tiles are lit up by the light source, and which are in shadow.

A visual aid of what it would look like, approximately. The L is the light source, the Xs are items blocking the light, the 0s are lit tiles, and the -s are tiles in shadow.

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 - - - - - - -

A fractional system would be even better, of course, where a tile can be in half-shadow due to being partially obscured. The algorithm wouldn't have to be perfect - just not obviously wrong and reasonably fast.

(Of course, there would be multiple light sources, but that's just a loop.)

Any takers?

2
  • Thanks for all your answers. I will go through them in detail and implement/post an algorithm once I get home.
    – Zarkonnen
    Oct 6, 2008 at 16:12
  • 1
    Have you made any further progress on this? I would be interested to hear how you have got on.
    – TK.
    Oct 14, 2008 at 14:00

12 Answers 12

23

The roguelike development community has a bit of an obsession with line-of-sight, field-of-view algorithms.

Here's a link to a roguelike wiki article on the subject: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

For my roguelike game, I implemented a shadow casting algorithm (http://roguebasin.roguelikedevelopment.org/index.php?title=Shadow_casting) in Python. It was a bit complicated to put together, but ran reasonably efficiently (even in pure Python) and generated nice results.

The "Permissive Field of View" seems to be gaining popularity as well: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

2
  • 2
    +1 for shadow casting. I use this in my roguelike and once you get it working it's great, and super fast. I don't like permissive field of view, I think it's too, well, permissive.
    – rlbond
    Jun 12, 2009 at 3:19
  • It's not just rougelikess. FOV and LOS are basic geometric tests needed to make AI sensors that simulate visual constraint properly, i.e. if any kind of stealth is possible. In a 2D physics system LOS can be done with a segment query and LOS by checked the dot product of the facing unit vector with the direction vector of the target. Nov 2, 2014 at 14:58
18

You can get into all sorts of complexities with calculating occlusion etc, or you can go for the simple brute force method: For every cell, use a line drawing algorithm such as the Bresenham Line Algorithm to examine every cell between the current one and the light source. If any are filled cells or (if you have only one light source) cells that have already been tested and found to be in shadow, your cell is in shadow. If you encounter a cell known to be lit, your cell will likewise be lit. An easy optimisation to this is to set the state of any cells you encounter along the line to whatever the final outcome is.

This is more or less what I used in my 2004 IOCCC winning entry. Obviously that doesn't make good example code, though. ;)

Edit: As loren points out, with these optimisations, you only need to pick the pixels along the edge of the map to trace from.

6

The algorithms being presented here seem to me to be doing more calculations than I think are needed. I have not tested this but I think it would work:

Initially, mark all pixels as lit.

For every pixel on the edge of the map: As Arachnid suggested, use Bresenham to trace a line from the pixel to the light. If that line strikes an obstruction then mark all pixels from the edge to just beyond the obstruction as being in shadow.

3
  • Good point about only having to use pixels along the edge. I think that's actually what I used - it's just been too long for me to recall clearly. :) Oct 6, 2008 at 15:29
  • A pure bresenham ray trace tends to leave artifacts at the edges of the light radius. It tends to miss squares which should be lit.
    – Dana
    Oct 6, 2008 at 15:31
  • You will probably need to re-iterate through the world to pick up any 'un-tested' tiles. Therefore simply iterating thruogh the array should have pretty much the same effect (assuming that you have a record of the tiles already tested).
    – TK.
    Oct 6, 2008 at 15:38
5

Quick and dirty:

(Depending on how big the array is)

  • Loop through each tile
  • draw a line to the Light
  • If any pary of the line hits an X, then it is in shadow
  • (Optional): calculate the amount of X the line passes through and do fancy maths to determint the proportion of the tile in shadow. NB: This could be done by anti-aliasing the line between the tile and the Light (therefore looking at other tiles along the route back to the light source) during the thresholding procedure these will appear as small anomolies. Depending on the logic used you could potentially determine how much (if at all) the tile is in shadow.

You could also keep a track of which pixels have been tested, therefore optimize the solution a little and not re-test pixels twice.

This could be dome pretty well by using image manipulation and drawing straight lines between pixles (tiles) If the lines are semi transparent and the X blocks are semi-transparent again. You can threshold the image to determine if the line has intersected an 'X'

If you have an option to use a 3rd party tool, then Id probably take it. In the long run it might turn out to be quicker, but you'd understand less about your game.

4

This is just for fun:

You can replicate the Doom 3 approach in 2D if you first do a step to convert your tiles into lines. For instance,

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

...would be reduced into three lines connecting the corners of the solid object in a triangle.

Then, do what the Doom 3 engine does: From the perspective of the light source, consider each "wall" that faces the light. (In this scene, only the diagonal line would be considered.) For each such line, project it into a trapezoid whose front edge is the original line, whose sides lie on lines from the light source through each end point, and whose back is far away, past the whole scene. So, it's a trapezoid that "points at" the light. It contains all the space that the wall casts its shadow on. Fill every tile in this trapezoid with darkness.

Proceed through all such lines and you will end up with a "stencil" that includes all the tiles visible from the light source. Fill these tiles with the light color. You may wish to light the tile a little less as you get away from the source ("attenuation") or do other fancy stuff.

Repeat for every light source in your scene.

3

To check if a tile is in shadow you need to draw a straight line back to the light source. If the line intersects another tile that's occupied, then the tile you were testing is in shadow. Raytracing algorithms do this for every object (in your case tile) in the view.

The Raytracing article on Wikipedia has pseudocode.

3

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.

  1. 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.
  2. 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.
  3. 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:

9876789
8543458
7421247
6310136
7421247
8543458
9876789

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.

3

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.

2

TK's solution is the one that you would generally use for this sort of thing.

For the partial lighting scenario, you could have it so that if a tile results in being in shadow, that tile is then split up into 4 tiles and each one of those is tested. You could then split that up as much as you wanted?

Edit:

You can also optimise it out a bit by not testing any of the tiles adjacent to a light - this would be more important to do when you have multiple light sources, I guess...

2

I've actually just recently wrote this functionality into one of my projects.

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;
            }
        }
    }

}

There's some extra stuff in there that you wouldn't need if you're adapting it for your own use. The type Place is just defined as an x and y position for conveniences sake.

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.

1

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

0

If you don't want to spend the time to reinvent/re-implement this, there are plenty of game engines out there. Ogre3D is an open source game engine that fully supports lighting, as well as sound and game controls.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.