Instant Dungeon! - Tech Talk #2 - Shadows feature

I've gotten a lot of kind words about the look of Instant Dungeon! so it seemed like a good idea to share some knowledge about how it was all done. To that end, here is the second in a series of articles detailing the tech behind Instant Dungeon!

First a quick introductory note on platforms, SDK, languages, etc. Instant Dungeon! was written in C# using our custom with the love engine. The engine uses SDL Dot Net and OpenTK for the Windows build and PSM SDK for the Playstation Mobile build. Shaders were written in GLSL for the windows build and CG for the PSM build.

The previous article in this series tackled the basics of Instant Dungeon!'s deferred 2D lighting system. It's recommended you read that one first, as this article builds on the ideas introduced there. You can read it here:
Indiedb.com

Ok, onto the final component of the lighting system, the shadows. In the game, the player's light is special in that it casts shadows, or to put it another way, it is blocked by walls.

Shadows are one of those great graphics programming challenges that have many, many solutions, all of them very interesting. In Instant Dungeon! shadows are achieved with a variation on the classic shadow map recipe that gives a good demonstration of how 3D techniques can be adapted and simplified for 2D.

In traditional 3D shadow map techniques, the scene is rendered from the perspective of the light. The depth buffer from this render is then used to determine what is lit by the light and what is in shadow. Instant Dungeon!'s shadow maps take this idea and squash it into 2D.

Instead of rendering the scene, a shadow map depth texture is generated by ray casting around the light's position and checking for walls. Because the walls in the game are represented by a simple 2D tile map, these ray casts are simple enough to perform on the cpu (Wolfenstein 3D anyone?). Just as each pixel of the depth buffer on a 3D shadow map represents a distance from the light along a specific ray shooting out from the light, each pixel in the 2D shadow map represents the distance to the nearest wall along a ray from the light. In 2D, that ray can be represented as a simply an angle in the axis-aligned unit circle around the light's position. Thus the 2D shadow map can be distilled to a 1D texture where the value at each texture coordinate 0-1 represents the distance to the nearest wall at the angles 0-360 (0-6.28 in radians).

Checking if a pixel is in light or shadow then is a simply a matter of knowing the distance and angle from the pixel to the light's center. The angle can be used to look up the distance between the light and the nearest wall in the shadow map texture. If this is greater than the distance to the light's center, the pixel is lit, if it's less, the pixel is in shadow.

Here is a diagram showing a sample shadow map raycast:

Of course, just like 3D shadow maps, this technique is limited by the resolution of the shadow map. Too much resolution and the shadow map depth texture will take too long to create, too little and they'll be artifacts (jaggies, swimming, etc.) in the shadows. In Instant Dungeon! the shadow map for the player's light is a 1D 8-bit 64 pixel texture. Some quick, round math, and that tells you that each pixel in the shadow map represents about 6 degrees in the sweep around the player. That might not seem like much, but it's plenty of room for nastiness even when rendering at a low res like Instant Dungeon! uses (240x136). Applying hardware (linear) filtering when sampling the texture map helps some, but to get the nice smooth look seen in the game, I added a slight 'penumbra' effect to the shadow, wherein the edges of the shadows are softened by blending in their occlusion effect. Here's a comparison shot of the the shadow maps with no filtering, filtering and filtering plus penumbra effect:

To get more technical about the penumbra effect, the penumbra is calculated by taking the distance to center of the light and the distance from the light to the nearest wall, computing the difference between these two values, then dividing that distance by the desired penumbra size and clamping to the range 0-1. The result is a number that is 0 if the pixel is fully lit and blends to 0 as the pixel moves into shadow. We subtract this number from 1 and multiply our normal light attenuation by it. Here's the GLSL code for the light with shadow map fragment shader (the vert shader is unchanged from the light without shadow map):

in vec4 ex_Offset;
in vec4 ex_Color0;

out vec4 out_Color0;

uniform sampler2D uShadMap;

#define TWO_PI 6.283185
void main(void)
{
	vec3 lcolor;
	int l;
	float dist;
	float attenuation;
	float depth;
	float diffuse;



	// distance attenuation
	dist = length( ex_Offset.xy );
	dist = min( dist, 1.0 );
	attenuation = pow( 1.0 - dist, ex_Color0.w );

	vec2 dir = normalize( ex_Offset.xy );

	// shadow map attentuation
	float angle = dot(dir,vec2(1.0,0.0));
	angle = acos(angle);
	if ( ex_Offset.y < 0.0f )
		angle = TWO_PI - angle;
	angle /= TWO_PI;
	float sdist = texture( uShadMap, vec2( angle, 0.5f ) ).r;
	float rdist = max( 0.0, dist - sdist );
	rdist = min(1.0, (rdist/0.2));
	rdist = 1.0 - rdist;
	attenuation *= rdist;


	lcolor = ex_Color0.rgb * attenuation;


	out_Color0 = vec4(lcolor,1.0);
	return;

}

Ok, some more clever shader talk. Notice how the use of 'corner' coordinates simplifies the shadow map calculation as well? The shadow map texture itself is actually encoded as distance from light's position to nearest wall divided by the radius of the light. This allows it to be compared directly to the linear distance factor from our standard point light calculation.

Finally, note that the penumbra's size is provided as fixed constant. This should actually be passed as uniform or vertex data so that it can changed per light. Since it is expressed in 'radius' space (if you will), using the same value for a light with a larger radius will yield a larger penumbra, which may or may not be what you want. However, since only one light in Instant Dungeon! casts shadows, I decided to leave that style point for later. Anyway, using a constant should be faster (if ever so slightly), so I'm calling it an 'optimization'!

Of course, these fancy shadows would be for not if they didn't serve the game. Fortunately (for the graphics junkie in me anyway), justifying this tech is simple as the core of the Instant Dungeon! player experience, wandering around a monster filled dungeon with limited visibility, is pretty well built around this shadow effect. You can get a good idea of the tension it creates by viewing our recently released 'Dark Roast' teaser:

And if that's not enough, or you just want to oggle a hot animated gif, here's one for you:

That's all for this talk, you can read more about Instant Dungeon! at:
Indiedb.com

And you can buy a copy or check out the free demo on:
Green Man Gaming
Greenmangaming.com
or
Itch.io
Capbros.itch.io
or
Indie Game Stand
Indiegamestand.com

In our next talk we'll delve into the powers of C# reflection, stay tuned!

* Legal notice, the code snippets above are provided free, public domain, etc. Do with them as you please.