Cell Lighting Propagation Problem

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.

• – MichaelHouse Jan 21 '14 at 5:12
• @Byte56 That's one of my own questions... – bpmw Jan 21 '14 at 14:48
• It's why I linked it, you have a few questions on the same topic. – MichaelHouse Jan 22 '14 at 1:23

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.

• Could you mock some code up for me? I'm not sure what your talking about. – bpmw Jan 21 '14 at 14:50
• @Lemoncreme he's saying you're doing stuff like light[x,y] = light[x,y+1] - amount;. You shouldn't be reassigning, but instead, storing the values in a new array; once you've done all the calculations, then copy the values over. – ashes999 Jan 21 '14 at 22:48
• Please stop signing your posts; the system already does it for you. – user1430 Jan 22 '14 at 0:25

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.

• Unfortunately that would be way too performance heavy. I can't do it in one pass because of the issue mentioned in my previous lighting question. – bpmw Jan 21 '14 at 16:29
• @Lemoncreme, I can't find issue you are talking about. Can you cite please? – Shadows In Rain Jan 22 '14 at 11:25
• @ShadowsInRain gamedev.stackexchange.com/questions/63982/… – bpmw Jan 22 '14 at 17:15
• @Lemoncreme Alredy visited. – Shadows In Rain Jan 23 '14 at 8:00

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;

// 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];
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];
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;

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)

• Hmmm... Thanks for clarifying what Xnafan was saying, I'll try that first then I'll try your method. The problem is I need to be able to support a very large amount (500+) of lights on screen without lag. This is why I didn't go for dynamic lighting before, but this looks a lot more efficient for my purposes. I'll get back to you when I get a chance tomorrow. – bpmw Jan 22 '14 at 2:51
• If you have a lot of light, then (as I mentioned you) can calculate area of influence in order to not to go over all grid for each light. Maybe there are other ways as well but one needs more info. – alariq Jan 22 '14 at 15:34
• ugh sorry to bring you back here but its still not working correctly, maybe i misunderstood what xnafan was saying though. could you make an example building off of what i have written in my question, using xnafan's method? – bpmw Jan 28 '14 at 3:15

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

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