Cell Lighting Propagation Problem

Question

I have in place a cell-based lighting system that works basically like this: (Not my actual code)

    //Light moves up
    for (int x = 0; x < width; x += 1)
    {
        for (int y = 0; y < height; y += 1)
        {
            light[x,y] = light[x,y+1] - amount;
        }
    }

    //Light moves down
    for (int x = width; x < 0; x -= 1)
    {
        for (int y = height; y < 0; y -= 1)
        {
            light[x,y] = light[x,y-1] - amount;
        }
    }

    //Light moves left
    for (int x = 0; x < width; x += 1)
    {
        for (int y = 0; y < height; y += 1)
        {
            light[x,y] = light[x+1,y] - amount;
        }
    }

    //Light moves right
    for (int x = width; x < 0; x -= 1)
    {
        for (int y = height; y < 0; y -= 1)
        {
            light[x,y] = light[x-1,y] - amount;
        }
    }

The variable amount is determined in each for() loop by if there is a block at x,y.

This should make it so that light darkens faster if there is a block at the position, but the light shows up looking like this:

Light shine out sides oddly

Light is in a tunnel, as you can see the top and bottom blocks are solid but they are not being lit up

Verical tunnel, but it seems to work correctly

Up and down dont seem to work quite right

I should also mention that changing the order of the passes changes in which direction the light propagates incorrectly. For example, if I change the order from up,down,left,right as shown above to left,right,up,down, the light is spread correctly in a horizontal tunnel and incorrectly in a vertical tunnel.

SO MY QUESTION IS: What is wrong with my code that creates this obvious miscalculation?

If you need to see more code or explanation or screenshots, I'll be happy to provide.

Answer 1

You should put the calculated values into a copy of the light double-array, to avoid having the order in which you read the lightvalue of the tiles influence the each other. So read all values from the first doublearray over into a new one, then use the new one for the actual lighting.

Answer 2

As written, your down and right loops don't run (I'm assuming that's a mistake in your example code). Beyond that you have overlap in the updates, so the order you run the loops gets amplifications in different directions. I suggest making a single pass over the lit area, and calculating the light value based on the distance from the source.

for (int x = 1 - width; x < width; x += 1)
{
    for (int y = 1 - height; y < height; y += 1)
    {
        light[x,y] = light[x,y] + LightValueAt(x,y, sourceX, sourceY);
    }
}

This does mean doing a line of sight check to get shadows. Check out Amit Patel's excellent article on 2D visibility.

Answer 3

Basically, what Xnafan told is one of the possible ways to do it right. What (I assume) he wanted to say is:

int* light_src;
int* light_dst;

// then in your code (i showed only one block but oyu need to do it for all :-) )
for (int x = 0; x < width; x += 1) {
    for (int y = 0; y < height; y += 1) {
        light_dst[x,y] = light_src[x,y+1] - amount;
    }
}
swap(light_src, light_dst);

Also, I am not sure how do you iterate through your 2d array and it is hard to see what is solid on your images and what is not.

I thought this was a nice effect so I did this :-) One possible way: we need to go opposite to light. there are 4 possible directions 1) right, down 2) left, down 3) right, up 4) left, up Here I show only one for right down, others are similar (just switch + for - where appropriate). I use texture of unsigned chars [0..255]

float fadeK = 253.0f/255.0f;
float fadeSolidK = 200.0f/255.0f;

// assume lx, ly - is indices of cell where the light is
// first fill right part of horizontal line where the light is
for(int x=lx+1; x< width; ++x) {
    unsigned char prev_v = light[ly*width + x-1];
    float fade = is_solid(x-1, ly) ? fadeSolidK : fadeK;
    float propagation = 1.0f*fade*prev_v;
    light[ly*width + x] = (unsigned char)propagation;
            if(propagation<=0.0) break;
}
// do same for vertical line under the light
for(int y=ly+1; y< height; ++y) {
    unsigned char prev_v = light[(y-1)*width + lx];
    float fade = is_solid(lx, y-1) ? fadeSolidK : fadeK;
    float propagation = 1.0f*fade*prev_v;
    light[y*width + lx] = (unsigned char)propagation;
            if(propagation<=0.0) break;
}
// now fill right down part
for(int y=ly+1; y< height; ++y) {
    for(int x=lx+1; x< width; ++x) {
        unsigned char left_v = light[y*width + x-1];
        unsigned char up_v = light[(y-1)*width + x];

        // determine how strong each previous (left or right) pillar influences us
        float dx = x - lx;
        float dy = y - ly;
        float sum = dx + dy;
        dx = dx/sum;
        dy = dy/sum;

        float fadeh = is_solid(x-1, y) ? fadeSolidK : fadeK;
        float fadev = is_solid(x, y-1) ? fadeSolidK : fadeK;
        float proparation = dy*fadev*up_v + dx*fadeh*left_v;
        light[y*width + x] = (unsigned char)clamp(proparation, 0.0f, 255.0f);
    }
}
// make all solid cells look white (just to mark them, you do not need to do it)
for(int y=ly; y< height; ++y) {
    for(int x=lx; x< width; ++x) {
        if(is_solid(x-1, y))
        {
            light[y*width + x] = 255;
        }
    }
}

It may look like a lot of code, but this is all very simple operations and you are not dependent on light move direction (actually your light can be at any cell at any single moment). Also (as optimization) you do not need to scan all array - only in some radius around light (radius depends on how fast the light fades out).

You can check out my resulting image (only case for one quadrant, other are done similar)

Answer 4

(I removed this answer because it ended up not working)

I took this a completely different way, using recursion instead of for() loops.