Best algorithm for shadow casting on a 2-D grid?
Chris Katko

I have a 2-D square grid, and I'd like to do a shadow casting / lighting algorithm. However, I haven't found one that takes advantage of the fact that I'm using a 2-D grid and not arbitrary polygons, while still retaining a non-grid lighting.

Like this:

{"name":"Monaco-whats-yours-is-mine-01.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/f\/afc95cb0114aecdf1d72b835e9dd49fb.jpg","w":1440,"h":900,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/f\/afc95cb0114aecdf1d72b835e9dd49fb"}

Not this:

{"name":"maxresdefault.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/9\/49b4bf903de99c158710e8fff1b85368.jpg","w":1920,"h":1080,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/9\/49b4bf903de99c158710e8fff1b85368"}

Bonus points if it shows how to do soft edges like in the first image.

Elias

My way is like this: first you want to get a polygon with the lit area. A very simple approach is to just create a fixed circle with, say, 1024 vertices. By using a fixed polygon instead of trying to figure out the exact shadow polygon (which is also possible) it gets rather trivial - just loop through the number of vertices and cast a ray for each, connecting the polygon to the first tilemap intersection (or the end of the ray if there is none).

As an example with just 6 vertices you get 6 collision rays for your light source:

```
\   /
\ /
----*----
/ \
/   \
```

And the resulting light polygon with no shadow tiles:

```   ___
/.   .\
/  . .  \
....*....
\  . .  /
\.___./
```

And with some shadow tiles:

```   ___
/    |
/__   \S
S| *  \S
|     /
|___ /
```

It won't be perfect, a shadow tile between two rays is ignored and the shadow never exactly follows the tiles but just the ray intersections. But you won't notice, I think when I implemented it I only had 256 vertices even.

As a next step, to get the soft border, add a border inside the polygon. For each vertex add another one which is, say, 10 pixels closer to the light. It should be trivial, there are no special cases - the first polygon always has exactly 1024 vertices no matter how many collisions - and you now add another 1024 vertices. Now create 1024 fully opaque triangles by connecting the inner vertices with a vertex in the center. And then fill the strip between the outer and inner polygon with 2048 triangles where the outer vertices are fully transparent.

Finally there's many ways to use this polygon to create the shadow effect - a very easy one is to use two bitmaps, one where you draw the shadow (e.g. white on black), one where you draw your fully lit tilemap. Then use a shader to combine them. The gradient in the shadow bitmap decides whether the tilemap bitmap is drawn unmodified (or with that extra color effect they seem to have in the screenshot) or gets dark and gray.

You could even completely skip shader and extra bitmaps for a somewhat reduced effect - just draw the shadow polygon first (white on dark gray). Then draw your tilemap but use multiplicative blending - fully white areas will have the unmodified lit tilemap, shadowed areas will get darkened, including the soft border. (But there shouldn't be any performance gain anymore and if you want the grayscale effect you need a shader anyway.)

[edit:]
Tried it out quick. My ray casting seems to have a small bug, probably due to the shortcut I took combining left/right and up/down. And my smoothing isn't enough because it obviously doesn't smooth at the sides. So instead of just moving the inner vertices towards the light source should probably take the normal of one of the adjacent edges into account and move in the opposite direction of that a bit.

1#include <allegro5/allegro.h> 2#include <allegro5/allegro_primitives.h> 3#include <allegro5/allegro_color.h> 4#include <math.h> 5#include <stdio.h> 6 7#define QUALITY 1024 8ALLEGRO_DISPLAY *d; 9ALLEGRO_EVENT_QUEUE *q; 10ALLEGRO_EVENT e; 11ALLEGRO_TIMER *t; 12ALLEGRO_COLOR c; 13bool r = true; 14int w = 32; 15int h = 18; 16int s = 32; 17int m[32 * 18]; 18double mx, my; 19 20void setup(void) { 21 for (int y = 0; y < h; y++) { 22 for (int x = 0; x < w; x++) { 23 m[x + y * w] = rand() % 10 ? 0 : 1; 24 } 25 } 26} 27 28bool cast_ray_tile(double ax, double ay, double bx, double by, 29 int *tx, int *ty, double *r) { 30 double cx = *tx * s; 31 double cy = *ty * s; 32 double dx = bx - ax; 33 double dy = by - ay; 34 double cx2 = cx; 35 double cy2 = cy; 36 double d = sqrt(dx * dx + dy * dy); 37 dx /= d; 38 dy /= d; 39 if (dy > 0) cy2 += s; 40 if (dx > 0) cx2 += s; 41 42 if (dy != 0) { 43 /* ax + u * dx = cx + v 44 * ay + u * dy = cy 45 */ 46 double u = (cy2 - ay) / dy; 47 double v = ax + u * dx - cx; 48 if (v >= 0 && v <= s) { 49 if (u < d) { 50 *ty += dy > 0 ? 1 : -1; 51 *r = u / d; 52 return 1; 53 } 54 return 0; 55 } 56 } 57 58 /* ax + u * dx = cx 59 * ay + u * dy = cy + v 60 */ 61 double u = (cx2 - ax) / dx; 62 double v = ay + u * dy - cy; 63 64 if (u < d) { 65 *tx += dx > 0 ? 1 : -1; 66 *r = u / d; 67 return 1; 68 } 69 return 0; 70} 71 72void cast_ray(double ax, double ay, double bx, double by, 73 double *ix, double *iy) { 74 int tx = ax / s; 75 int ty = ay / s; 76 *ix = bx; 77 *iy = by; 78 while (1) { 79 double u; 80 if (!cast_ray_tile(ax, ay, bx, by, &tx, &ty, &u)) 81 return; 82 if (tx < 0 || ty < 0 || tx >= w || ty >= h) 83 return; 84 85 if (m[tx + ty * w]) { 86 *ix = ax + (bx - ax) * u; 87 *iy = ay + (by - ay) * u; 88 return; 89 } 90 } 91} 92 93void draw_tilemap(void) { 94 ALLEGRO_COLOR wall = al_color_name("yellow"); 95 ALLEGRO_COLOR grass = al_color_name("green"); 96 for (int y = 0; y < h; y++) { 97 for (int x = 0; x < w; x++) { 98 int p = m[x + y * w]; 99 al_draw_filled_rectangle(x * s, y * s, x * s + s, y * s + s, 100 p ? wall : grass); 101 } 102 } 103} 104 105void draw_shadow(void) { 106 107 ALLEGRO_COLOR solid = al_map_rgba_f(1, 1, 1, 1); 108 ALLEGRO_COLOR transparent = al_map_rgba_f(0, 0, 0, 0); 109 110 double ix[QUALITY], iy[QUALITY]; 111 double ix2[QUALITY], iy2[QUALITY]; 112 113 ALLEGRO_VERTEX v[2 + QUALITY]; 114 ALLEGRO_VERTEX v2[2 + QUALITY * 2]; 115 memset(v, 0, sizeof v); 116 memset(v2, 0, sizeof v2); 117 v[0].x = mx; 118 v[0].y = my; 119 v[0].color = al_map_rgba_f(1, 1, 1, 1); 120 121 for (int i = 0; i < QUALITY; i++) { 122 double a = 2 * ALLEGRO_PI * i / QUALITY; 123 double rx = cos(a) * 8 * s; 124 double ry = sin(a) * 8 * s; 125 cast_ray(mx, my, mx + rx, my + ry, ix + i, iy + i); 126 double dx = mx - ix[i]; 127 double dy = my - iy[i]; 128 double d = sqrt(dx * dx + dy * dy); 129 ix2[i] = ix[i] + dx * 8 / d; 130 iy2[i] = iy[i] + dy * 8 / d; 131 132 v[1 + i].x = ix2[i]; 133 v[1 + i].y = iy2[i]; 134 v[1 + i].color = solid; 135 v2[i * 2 + 0].x = ix2[i]; 136 v2[i * 2 + 0].y = iy2[i]; 137 v2[i * 2 + 0].color = solid; 138 v2[i * 2 + 1].x = ix[i]; 139 v2[i * 2 + 1].y = iy[i]; 140 v2[i * 2 + 1].color = transparent; 141 } 142 v[1 + QUALITY] = v[1]; 143 v2[QUALITY * 2 + 0] = v2[0]; 144 v2[QUALITY * 2 + 1] = v2[1]; 145 146 al_draw_prim(v, NULL, NULL, 0, 2 + QUALITY, ALLEGRO_PRIM_TRIANGLE_FAN); 147 al_draw_prim(v2, NULL, NULL, 0, 2 + QUALITY * 2, 148 ALLEGRO_PRIM_TRIANGLE_STRIP); 149} 150 151void draw_scene(void) { 152 al_set_blender(ALLEGRO_ADD, ALLEGRO_ONE, ALLEGRO_INVERSE_ALPHA); 153 al_clear_to_color(al_map_rgba_f(0.5, 0.5, 0.5, 1)); 154 draw_shadow(); 155 156 al_set_blender(ALLEGRO_ADD, ALLEGRO_DEST_COLOR, ALLEGRO_ZERO); 157 draw_tilemap(); 158} 159 160int main() { 161 srand(time(NULL)); 162 al_init(); 163 al_install_keyboard(); 164 al_install_mouse(); 165 al_init_primitives_addon(); 166 al_set_new_display_option(ALLEGRO_SAMPLE_BUFFERS, 1, ALLEGRO_SUGGEST); 167 al_set_new_display_option(ALLEGRO_SAMPLES, 8, ALLEGRO_SUGGEST); 168 d = al_create_display(w * s, h * s); 169 q = al_create_event_queue(); 170 t = al_create_timer(1.0 / 60); 171 al_register_event_source(q, al_get_keyboard_event_source()); 172 al_register_event_source(q, al_get_mouse_event_source()); 173 al_register_event_source(q, al_get_timer_event_source(t)); 174 al_register_event_source(q, al_get_display_event_source(d)); 175 al_start_timer(t); 176 setup(); 177 while (true) { 178 al_wait_for_event(q, &e); 179 if (e.type == ALLEGRO_EVENT_DISPLAY_CLOSE) 180 break; 181 else if (e.type == ALLEGRO_EVENT_KEY_DOWN) { 182 if (e.keyboard.keycode == ALLEGRO_KEY_ESCAPE) 183 break; 184 } 185 else if (e.type == ALLEGRO_EVENT_MOUSE_AXES) { 186 mx = e.mouse.x; 187 my = e.mouse.y; 188 } 189 else if (e.type == ALLEGRO_EVENT_TIMER) { 190 r = 1; 191 } 192 if (r && al_is_event_queue_empty(q)) { 193 draw_scene(); 194 195 al_flip_display(); 196 r = 0; 197 } 198 } 199 return 0; 200}

Polybios

I took a similar approach to Elias's, but what bothered me with the "fixed polygon"-approach was the slight jittering that's visible at the shadow edges when moving.
I've also tried this algorithm. It isn't optimized for square grids though, but this could probably be done in some way.

Elias
Polybios said:

I've also tried this algorithm

So basically, instead of shooting a fixed amount of rays, he collects all edges within the light radius which could possibly throw a shadow. Then sorts their vertices by angle to the light source. And then does the same algorithm as with the fixed angles, except shooting rays along those sorted angles. I think that is indeed worth the extra complexity, and with some clever collecting of edges can probably even optimize the sorting a bit.

Just leaves the question for making the soft edges. One approach might be to only calculate the original shadow polygon but after drawing it blur the whole shadow buffer. If done clever this can be achieved in the shader without requiring an extra pass I guess - instead of taking a single sample from the shadow buffer take several samples and average, therefore smoothing out the edges.

Polybios

He doesn't cap the distance (and always encloses the area with obstacles), so you'll have to generate nice arcs between the rays / angles that went beyond the light source radius, but that's no big deal.
I didn't quite like the idea of doing it with angles and atan2, but didn't play around with it any longer.

Also, t-junctions could be a problem when the resulting triangle fan is drawn with transparency at some point (i. e. two triangles have part of a common edge, but the vertices are not the same).