Technical

This past week I’ve been working on the first parts of the decorator algorithm for The Stranger in Kilstow. One of the most common complaints I see about games with procedurally-generated levels is that the map looks repetitive. If the map uses room templates, then the templates become immediately recognizable after a few plays through, and if the terrain is generated then every area tends to look very similar. To combat those issues, I’m working on an algorithm that can render any given set of geometry with sufficient variance based on a style template. The goal is to make each room look more interesting than just simple geometry, with backgrounds and decorative doodads sprinkled around in a coherent and sensible manner. This should hopefully add a good amount of variety to make the levels feel more unique within themselves and between runs, while also allowing me to do some more advanced things with level generation and using visual cues to tie remote locations together in the player’s mind.

To start things off, I needed a way for the algorithm to understand which parts of the geometry belong together. By getting the algorithm to understand how the pieces of the geometry fit together, it can make a smart decision about how to draw the backgrounds and supporting structures to make the room not feel so bland. I tried a variety of methods to turn a series of small rectangles into larger coherent zones, but what ended up working the best was a weird hybrid of a breadth-first search and a modified binary space partition.

I started by creating a list of bounding boxes for all of the terrain objects. For each item in the list, it looks for any other regions with any amount of overlap. If the two regions fully overlap, then the larger region is kept and the smaller one is discarded. This isn’t really relevant on the first pass, but once the regions start combining together it becomes very possible that a small piece is already covered by a larger area. After that it finds the nearest region and does a grouping check to see if they should be merged into a single region.

The grouping check is pretty simple. It calculates the smallest axis-aligned bounding box that contains both regions and then divides it in half twice. It calculates the number of objects contained within each region and checks the difference across each axis. If the resulting number of objects on either side of both axes is the same then it’s considered a good combination and the two regions are merged into one. If the number of objects are different across both axes, then it’s considered a batch combination and the algorithm stops processing that group and goes to the next nearest region. If there is a discrepancy only across one axis, then it randomly decides whether to keep the group, based on the room’s seed.

The end result is that the room’s geometry is transformed into a series of large regions on the map that all fit together. The next step is to use these regions of terrain to split up the empty space in the room into relevant corresponding regions for each terrain region. Hopefully once I have the empty space partitioning in relation to the terrain, I will be able to have it actually construct a visual representation of any room at least in regards to setting up the platforms and backgrounds to support them to create something that doesn’t look quite so bland.

I mentioned in my last weekly post that I had gotten a working shader for Sprite Lamp up and running. I’m going to explain what that shader does, and attach it here for you all to download and use if you feel so inclined. I will caveat this by saying that I am, by no means, an expert on shaders, Unity, or lighting. I figured all of this out with google searches on various topics and by looking at both the Unity documentation on writing shaders and the built-in shaders that Unity comes with. There may be mistakes and some features may not work as you would expect, but it fits my needs and so may fit some of yours as well. On with the show (or scroll to the bottom for the download link).

The Shader, Explained

Shader “Sprite Lamp/Default”
{

Properties
{

_MainTex (“Diffuse Texture”, 2D) = “white” {}
_BumpMap (“Normal Map (no depth)”, 2D) = “bump” {}
_AOMap (“Ambient Occlusion”, 2D) = “white” {}
_AOIntensity (“Occlusion Intensity”, Range(0, 1.0)) = 0.5
_SpecMap (“Specular Map”, 2D) = “white” {}
_SpecIntensity (“Specular Intensity”, Range(0, 1.0)) = 0.5
_Color (“Tint”, Color) = (1,1,1,1)

}

SubShader
{

Tags
{
“Queue”=”Transparent”
“IgnoreProjector”=”True”
“RenderType”=”Transparent”
}

LOD 300
Blend SrcAlpha OneMinusSrcAlpha

CGPROGRAM
#pragma surface surf BlinnPhong vertex:vert

sampler2D _MainTex;
sampler2D _BumpMap;
sampler2D _AOMap;
sampler2D _SpecMap;
fixed4 _Color;
uniform float _AOIntensity = 0;
uniform float _SpecIntensity = 0;

struct Input
{

float2 uv_MainTex;
float2 uv_BumpMap;
float2 uv_AOMap;
float2 uv_SpecMap;
fixed4 color;

};

void vert (inout appdata_full v, out Input o)
{

v.normal = float3(0,0,-1);

UNITY_INITIALIZE_OUTPUT(Input, o);
o.color = v.color * _Color;

}

void surf (Input IN, inout SurfaceOutput o)
{

fixed4 c = tex2D(_MainTex, IN.uv_MainTex) * IN.color;
fixed4 a = tex2D(_AOMap, IN.uv_AOMap);
fixed4 s = tex2D(_SpecMap, IN.uv_SpecMap);
o.Normal = UnpackNormal(tex2D(_BumpMap, IN.uv_BumpMap));
o.Albedo = c.rgb * c.a;
o.Albedo *= (1.0 – _AOIntensity) + (a.r * _AOIntensity);
o.Albedo *= (1.0 – _SpecIntensity) + (s.r * _SpecIntensity);
o.Alpha = c.a;

}

ENDCG

}

Fallback “Specular”

}

This shader handles normal mapping, ambient occlusion through calculated maps, and specular mapping. I’m going to start at the top and explain what each piece does.

Shader “Sprite Lamp/Default”
{

Properties
{

_MainTex (“Diffuse Texture”, 2D) = “white” {}
_BumpMap (“Normal Map (no depth)”, 2D) = “bump” {}
_AOMap (“Ambient Occlusion”, 2D) = “white” {}
_AOIntensity (“Occlusion Intensity”, Range(0, 1.0)) = 0.5
_SpecMap (“Specular Map”, 2D) = “white” {}
_SpecIntensity (“Specular Intensity”, Range(0, 1.0)) = 0.5
_Color (“Tint”, Color) = (1,1,1,1)

}

This stuff is all pretty basic. The first line lets you declare the name and folder where the shader will show up in Unity’s shader selection list. The next chunk is the properties block. This is where you define what properties are exposed in the editor interface. I don’t know how these map in code, I built all of my materials through the editor and just access them that way, but in the editor they are listed by name. Each property goes on its own line, and it’s pretty simple to set them up. The first part is the variable name, then in parenthesis you define how it works in the editor, with name as a string, followed by the type. 2D gives you any texture, range gives you a slider with specified minimum and maximum values, and color is a the color picker.

After the equals sign you specify the default value for the objects. This is important for the textures, since if you omit one, you want to make sure that it all still works right. Since both the ambient occlusion and specular mapping are done with multipliers, white means no change, which effectively turns that feature off if you don’t specify a value for that variable. The same thing goes for color.

SubShader
{

Tags
{

“Queue”=”Transparent”
“IgnoreProjector”=”True”
“RenderType”=”Transparent”

}

LOD 300
Blend SrcAlpha OneMinusSrcAlpha

The next block starts the actual shader logic. The tags let you specify some settings for the shader. I pulled these from the built-in sprite shader, so I’m a little fuzzy on what they do. Based on what I read from the official documentation, the queue tag sets which layer things are rendered on, and the render type tag sets how the rendering is performed. All three of these tags are in the default shaders, so I felt safe using them. There were two more that I took out that may go back in if this runs into performance problems later on, but these work fine for now.

The LOD tag sets the level of detail this shader runs at. Unity recommends 300 for bumped specular, so that’s what I went with. The blend mode sets standard alpha blending, which supports translucent pixels so you can have nice anti-aliased edges.

CGPROGRAM
#pragma surface surf BlinnPhong vertex:vert

sampler2D _MainTex;
sampler2D _BumpMap;
sampler2D _AOMap;
sampler2D _SpecMap;
fixed4 _Color;
uniform float _AOIntensity = 0;
uniform float _SpecIntensity = 0;

From here on out, most of this code was pulled from the official shader documentation. CGProgram is what starts the actual shader code; this is a standard Unity thing. The pragma line is where we declare what the names of our surface and vertex shaders are, as well as the lighting model we want to use. BlinnPhong is the lighting model for specular lights, so that’s what I went with. The rest of this is where we declare the variables that actually go into the shader code. These map by name, so they have to be exactly the same as they are defined in the properties block. I got the data types from looking at the included shaders, they seem to map 1:1 to the types in the properties section.

struct Input
{

float2 uv_MainTex;
float2 uv_BumpMap;
float2 uv_AOMap;
float2 uv_SpecMap;
fixed4 color;

};

This section just defines what information is fed to our surface shader from the vertex shader. Since all of these values are affected by their position within the face of the quad that is holding our sprite, we need them all. The ones that aren’t affected by position, the intensity values for both ambient occlusion and specular mapping, we don’t need to send those through. They have been declared so we can access them at the top level, and since they are constant (within a given pass) we don’t need any more detail.

void vert (inout appdata_full v, out Input o)
{

v.normal = float3(0,0,-1);

UNITY_INITIALIZE_OUTPUT(Input, o);
o.color = v.color * _Color;

}

This is the vertex shader. I ripped this almost entirely from the built-in diffuse sprite shader. All this really does is clear the normal based on the geometry and then apply the color from the vertex. This makes it so that we can use the tint of the sprite itself or the tint applied to the shader, they will both work fine. The only thing I took out was the pixel snapping code. My game doesn’t use pixel art, it’s all rasterized vectors. I didn’t need or want it in there, but if you want to enable pixel snapping, you can modify this based on Unity’s diffuse sprite shader.

void surf (Input IN, inout SurfaceOutput o)
{

fixed4 c = tex2D(_MainTex, IN.uv_MainTex) * IN.color;
fixed4 a = tex2D(_AOMap, IN.uv_AOMap);
fixed4 s = tex2D(_SpecMap, IN.uv_SpecMap);
o.Normal = UnpackNormal(tex2D(_BumpMap, IN.uv_BumpMap));
o.Albedo = c.rgb * c.a;
o.Albedo *= (1.0 – _AOIntensity) + (a.r * _AOIntensity);
o.Albedo *= (1.0 – _SpecIntensity) + (s.r * _SpecIntensity);
o.Alpha = c.a;

}

This is the real meat of the shader. This is what actually applies the different lighting concepts to the sprite. The first thing we do is grab the color of the pixel at the point of the current fragment being lit from all of our source textures. Remember that we defaulted these to white if they weren’t supplied, so if they aren’t available, we just get a fully opaque white pixel. We also multiply the texture color by the light that was supplied by our vertex shader. This is standard practice from the built-in shader to make the tinting and colored lights work.

The bottom part is where we set the actual values used for this fragment on the screen. First we grab the normal from our nomal map. This uses the built-in unity function for unpacking normals from a normal map. I have no idea how it works, it’s magical, and it basically handles all of the normal mapping for you. All that’s left is setting the albedo. I have no idea what albedo even means, but it seems to want a color based on the shaders I looked at, so I started with that. The rgb value from the input texture, multiplied by its alpha. I don’t know why, exactly, you have to multiply the color by the alpha, but if you don’t translucency just breaks completely.

From there it’s a simple matter of just multiplying in the ambient occlusion and specular maps and setting the alpha. These are always in grayscale, so I just grab the first color in the bunch since they are all the same. I will be honest, I have no idea if this is how baked ambient occlusion or specular mapping work. I did some googling on how to bake those things in, and the general consensus was that you just multiply them against your input texture. This makes sense, and the results look like I would have expected, so I left it at that. The math in there is just for tuning the intensity of the effects while ensuring that the top end is always 1.0.

So that’s it, in a nutshell. There may be some issues, and if you find any I’m all ears. I wrote this up quick and dirty just to get it working, and the results actually came out pretty nice.

Usage Instructions

To use this shader, there are a couple of things you need to make sure of. First, your diffuse texture should be set as a sprite in unity. None of the settings on the sprite really matter, though they will affect the image in the expected ways. Second, your normal map should be set as a normal map. If you’re using the output from Sprite Lamp, it needs to be normal only, not normal + depth or anything like that. When you set it to a normal map in unity, it has a tendency to default the Create from Grayscale setting on, but that will mess up the normals so make sure that’s unchecked. Third, the other textures, ambient occlusion and specular map, should be set as textures. That’s it, plug your values in and go.

There are a number of features that this shader does not support right now. The first is shadow casting. I don’t have Unity Pro, so I can’t use shadows. I could implement something for self-contained shadows, but since that would look awful in my game without external shadows as well, I didn’t. As a result, there is really no use for the depth map, so I didn’t include that either. The second is the lack of emissive light. Since this shader supports global directional lighting, I didn’t see a need to include it or wraparound lighting. The last thing it doesn’t have is cel shading. I may end up implementing this later, but for right now I’m going forward without it to see how it turns out. I will update this article and the attached download if I make that change.

Download the shader

Click to view, right-click save as to download.