I have an implemented algorithm to generate these shadows and lights and it does fine. My problem is with the speed.
Observe some screenshots:

Screenshots.



Several Multi-colored Lights with NO Shadows. Get a solid 60 fps....




Lights WITH shadows. Generates 20-30~ fps. Speed reduces even further after 5 or so more lights in the map...

The Concept.

1. Pre-Lighting. It the checks to see if any light_groups have been added to the map and iterates through each visible tile on screen and applies each light to it. If the tile is off-screen or pitch black, it simply isn't drawn.

2. Light Calculation. Each light casts line checks to see if the tile is blocked by a wall tile (to reduce the light value the final tile may receive.) If so, the light value is cut immensely and is returned. If not, full light value is returned.

3. Light Baking. The final color value from the lights are applied to the tile (keeping a threshold between 0-255).

This process is repeated for each tile on-screen until all tiles are affected by the light sources.

The Problem.

Each tile through each light is costly. The screen is 600x400, so there are about 950 tiles to iterate through. Currently 5 light sources.

That's a lot of calculation that I'm sure could be reduced.

The Code.

Light Group and calculation.

#include "MapLightGroup.h"
MapLightGroup::MapLightGroup(GenericTiledMap *generic_tiled_map)
{
map = generic_tiled_map;
}
MapLightGroup::~MapLightGroup()
{

}
const Light::Color MapLightGroup::calculateLight(const Vector2D point)
{
Light::Color final_color, current_color;

final_color.r = 0;
final_color.g = 0;
final_color.b = 0;
final_color.a = 1;

// Map cell dimensions
int cell_w = map->getCellWidth();
int cell_h = map->getCellHeight();

for(int i = 0; i < getSize(); i++)
{
bool blocked = false;

if(get(i)->getPosition().distance(point) < get(i)->getCutoffDistance())
{
if(map->lineIntersection(get(i)->getPosition().x/cell_w, get(i)->getPosition().y/cell_h,
point.x/cell_w, point.y/cell_h,
0, 0, 0))
{
blocked = true;
}
}
/*else
{

}*/

// If the light source is beyond a block, darken it.
if(blocked)
{
current_color = get(i)->calculateLight(point);

final_color.r += current_color.r/10.0;
final_color.g += current_color.r/10.0;
final_color.b += current_color.r/10.0;
final_color.a += current_color.r/10.0;
}
else
{
//final_color.r = 0;
//final_color.g = 0;
//final_color.b = 0;

current_color = get(i)->calculateLight(point);

final_color.r += current_color.r;
final_color.g += current_color.g;
final_color.b += current_color.b;
final_color.a += current_color.a;
}
}

// limit threshold to 0-255
final_color.normalize();

return final_color;
}


The individual light calculation code:

const Light::Color Light::calculateLight(Vector2D point)
{
Light::Color final_color;
double dist = light_position.distance(point);

if(dist <= 1) dist = 1.0;

if(dist >= light_cutoff)
{
final_color.r = 0;
final_color.g = 0;
final_color.b = 0;
final_color.a = 1;

return final_color;
}

double dist_light_factor = dist*light_tightness;

double light_scalar = 1.0/(dist_light_factor/(light_radius*light_spread_weight));

final_color.r = light_color.r * light_scalar;
final_color.g = light_color.g * light_scalar;
final_color.b = light_color.b * light_scalar;
final_color.a = light_color.a * light_scalar;
final_color.normalize();

return final_color;
}


The map drawing code.


void ZombieGameTiledMap::draw(Camera *cam, LightGroup *lights)
{
if(cam == 0)
return;
int cell_width = getCellWidth();
int cell_height = getCellHeight();
for(int k = 0; k < getNumLayers(); k++)
{
if(!map_parser->getLayer(k).visible)
continue;

for(int i = 0; i < getMapWidth(); i++)
{
for(int j = 0; j < getMapHeight(); j++)
{
GenericTiledMap::Tile tile = getTile(i, j, k);

if(tile.getCellID() - 1 < 0)
continue;

if(!cam->isPositionInView(Vector2D(i*cell_width, j*cell_height)))
continue;

Gosu::Color c = Gosu::Colors::white;
c.setAlpha( map_parser->getLayer(k).opacity * 255 );

Vector2D coord = cam->worldToScreen( Vector2D( (i*cell_width), (j*cell_height) ) );

// CALCULATE LIGHT COLORS TO TILES
if(lights != 0)
{
Light::Color color;
Vector2D point = Vector2D(i*cell_width, j*cell_height);
color = lights->calculateLight(point);

// PITCH BLACK. DON'T DRAW!
if(color.r == 0 && color.g == 0 && color.b == 0)
continue;

// RED
double red = color.r;

if(red > 255) red = 255;

c.setRed( red );

// GREEN
double green = color.g;

if(green > 255) green = 255;

c.setGreen( green );

// BLUE
double blue = color.b;

if(blue > 255) blue = 255;

c.setBlue( blue );
}

double scale = cam->getZoom();

// NOW DRAW
v_img[tile.getCellID()-1].draw(coord.x, coord.y, k, scale, scale, c);
}
}
}
}


The Help.

If there is any more information needed (i.e. more code), please let me know. I want to be able to have decent results with better speed.

Also, another achievement I'd like is less blocky shadows if possible. If some kind of smoother interpolation between shadow'd tiles is possible, inform me.

Thank you.

I did something similar in a Ludum Dare entry a few years ago (Light and Darkness). Instead of calculating the lights during the drawing I did that before.

Also, every tile had a color value at each edge. Set all values to 0. For every visible light ray casting to modify the affected tiles. Let the GPU handle the smoothing via vertex coloring.

-wrong reply-

I did something similar in a Ludum Dare entry a few years ago (Light and Darkness). Instead of calculating the lights during the drawing I did that before.

Also, every tile had a color value at each edge. Set all values to 0. For every visible light ray casting to modify the affected tiles. Let the GPU handle the smoothing via vertex coloring.

But even if I changed the location of the logic (i.e. update() and storing the data in some buffer for the draw() phase), wouldn't it still be slow?

Color value at each edge isn't a bad idea instead of center-point light values. I believe that will solve my smoothing problem at least.

Doing the update separate allows you to batch drawing. Unless you already do that this might help performance a lot.

Although I confess, I didn't do batching back there as well. With smoothing it looked like this:

I haven't looked very much over your code, so i might be wrong in my assumption, but if your shadow algorithm is to take each light, and fire a ray to each visible tile, then their is defiantly room for improvment.

first idea to come to mind is instead of going through each tile for each light, you start at the lights center, and expand in a circle around the tiles of the light, until you've hit all walls in all directions for the light, or at least until the light value for each particular direction is withing whatever threashold you need(essentially a Dijksta algo).

another idea, which i'm uncertain how your map->lineIntersection function operates, but is to march along the line per tile, so this way you are only evaluating the tiles the line is actually interacting with.

anywho, hope i'm not completely off base with what your doing.

first idea to come to mind is instead of going through each tile for each light, you start at the lights center, and expand in a circle around the tiles of the light, until you've hit all walls in all directions for the light, or at least until the light value for each particular direction is withing whatever threashold you need(essentially a Dijksta algo).

Dijksta in this case sounds like an interesting approach. However, it did lead me to think about using a simple flood-fill algorithm alongside the ray-casting. All the tiles beginning from the light will be filled and dissolve with greater distance. Along with the ray-casting, it would lead to an instant check if there is an initial blockage.

Thanks for the brain storming! I'll reply with any results.