The Stranger in Kilstow

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.

It is a widely held axiom among programmers that premature optimization is poison. If you let it get in your head, you can end up spending months optimizing code that isn’t even a problem and waste countless hours better spent actually writing code. Being the level-headed individual I am, I decided to engage in such a behavior over the past couple of weeks. I didn’t arrive at this point by impulse or recklessness though, and the results are pretty incredible so far. Let me explain how I got here.

Tiles, United

I have made my fair share of tile-based engines in the past. I’ve used a variety of different languages and frameworks to do it, and I thought Unity would be no different. In a way I was right, just not in the way I expected. Up to this point I had been using Unity’s sprite renderer component to draw all of my images onto the screen. After learning that I was limited to one such component per object, I immediately took the brute force approach and just started adding more game objects to the scene, each with a renderer for a single tile. With the lights turned off, this worked fine, and Unity batched all of the renders together into a single pass, and everything was fast and efficient. Unfortunately, I’m making heavy use of lighting for this game, and when you turn the lights on with this approach, things start to fall apart.

Initially it wasn’t all bad. I only had one renderer per terrain feature, which was just stretched across the size of feature. This made everything look terrible, and was a hack to get the scene up and running. I started making more materials, one for each unique size of terrain, and telling the shader to tile the image out. This worked great, but I ended up with an unmanageable amount of materials, and it didn’t seem like a very scalable solution. I opted to switch to a single game object with a child object for each tile, each holding a single sprite renderer. A much more viable approach to the problem, but I noticed a peculiar spike in my draw call count and a dip in my frame rate. It wasn’t much, so I ignored it; premature optimization is the devil, after all.

I intend to use about five layers to render the scenes in this game, and up to this point I had simply been using a sprite layer and the terrain layer. A solid black background makes for boring screenshots, and since I am trying to spread the word about this game early and often, I wanted something a bit more interesting to share. As I started to put in background, middle, and parallax layers, the funny little draw call spike turned into a hulking monster. One room, with only a handful of lights and a single character, was spiking to unreasonable levels. The draw call count was well over 300, and the frame rate on my computer was dropping dangerously close to 60. I have a pretty powerful computer, I can play AAA 3d titles with the settings maxed out and never drop below my refresh rate. My 2d game should not be running at 60 fps on this computer, and if it does, it probably won’t run very well on a more standard desktop. Something had to be done.

The Cusp of Trouble

I think it had to be done, anyway. I did no profiling on this, I didn’t test it on other computers to see if it was really that slow. For all I know it could have been just a fluke. Regardless, I panicked. I had no idea how to approach this problem, I didn’t understand how Unity’s sprite renderers did their batching or what the potential ramifications of pumping 10k game objects per room into the scene were. I started looking into it, and while it seemed to be a common problem, nobody ever really had a solution that would work with my lighting system. The only thing I could think of was to stop using Unity’s built-in 2D tools and just write a tile renderer myself.

After digging through Unity’s sparse documentation on the matter, and then looking up several examples of people building mesh geometry through code, I figured out how to build the meshes and send them to Unity to be rendered. Essentially what I have now is a series of textured quads that are all built as part of the same mesh, with each quad representing a single tile on the screen. If this sounds like a simple and obvious solution to the problem, it is, but that’s part of why I’m confident in this decision.

Worth It

This comes with a few nice benefits on the side; answers to problems I hadn’t even thought about addressing yet. First and foremost, it lets me create an atlas for my tiles. I wasn’t sure how to do this in Unity without creating a separate material for each sprite in the atlas. This would mean that the extra textures for lighting would have to be split apart, which defeats the purpose of using an atlas in the first place. It also gives me a nice, single object to use as the view for each layer of map data. This cuts down on extra game objects in the scene, extra components in the code, and the extra complexity of grouping and managing tiles within a room to help decide when to stop processing that area because it’s too far away.

I really wanted to let Unity handle this for me, but it seems their sprite system and 3d lighting just don’t mix. At this point I’m not really using any of Unity’s 2d tools any more, which is a bit frustrating as this was supposed to save me time. If it makes for a better product though, I guess I’m alright with that. I’m hoping this is the last bit of infrastructure I have left, and I should be able to start focusing on making this into an actual game instead of a tech demo with a story.

Quick announcement today. I’ve been working on updating the back-end of the website to reduce spam comments so I could open them up for more general commenting. This was all so I could launch the new website for Project Dunwich. The project now has an official name. Check out the main website below for an updated description of the game. It’s not much yet, but at least I have something to call this game now.

The Stranger in Kilstow

You can also get to the site through or


I’ve been pretty quiet on the blog for the past month, and I’d like to apologize for that. I have a tendency to get caught up in my game’s development and forget about pretty much everything else. This whole player interaction piece has always been hard for me, and I guess I just let it slip for a while. No matter, you’re not here to listen to excuses, let’s get on to the good stuff.

No Seriously, We Do

It's tilted the wrong way because try as I might I could not get it to balance on the curve.

It’s tilted the wrong way because try as I might I could not get it to balance on the curve.

My wife has recently been getting into 3D printing, and this was one of the first things she printed. It hasn’t been sanded/finished yet in this picture, but it’s pretty damn cool as-is. While my wife did this all of her own accord, it has spurred in me a desire to make some merchandise available for both the company and the game as it moves closer to finish. I’m going to try really hard on the marketing angle of this game once I get the first vertical slice ready, and shirts and other physical objects seem like a good way to aid that. I do eventually want to go to conventions to present, and this has got me thinking about aspects of that I hadn’t even considered before. Plus, 3D printing is just cool.

The Slice

One of the things I want to do differently this time around is the way I approach the the promotion of the game. In Vivo was made in a very linear fashion, and I didn’t have a demo ready until just a few weeks before release. This, combined with the fact that I was so set on releasing it that I didn’t really give adequate time to content creation, meant there was very little time for marketing, and by the time I was able to I was so focused on finishing that I dropped the ball on it completely. The fact that it sold any copies at all given my efforts at marketing it still amazes to this day. That being said, this time I’m trying to get a polished demo out as soon as possible. We call this the vertical slice.

Essentially this is a cross section of the whole game, a short amount of gameplay with the most important systems in place and all of the polish of the finished game. I’m still quite a ways off from that goal, but I feel like I’ve overcome the final hurdle in regards to things I’ve never done before. I’ve made procedural level systems, I’ve done stealth and platforming and AI, and I’ve done sound effects and music. Now that I have the lighting and animation systems finished, all that’s left is making assets, and doing things that I’ve done before in code. That’s not to say it will be easy or fast, but at least I can better predict how long it will take and what obstacles I’m likely to encounter.

Lights and Spirits

Since the last update I’ve been focused on integrating the Sprite Lamp shader that I wrote with the existing Spine animation system I had been using. This presented some unexpected and maddening challenges. While I’m not 100% satisfied with how it is right now, it’s good enough to move forward for now. The crux of the Spine integration problems was due to the way Unity handles lights for objects on the same layer. It seems to be that Unity processes all objects on the same layer in one batch, first rendering the ambient and directional lights, and then adding each dynamic light one at a time to that initial render pass. Since the lights don’t know or care which object was drawn first and therefore occluded by other parts, it blends on the lights for everything to the top of the first render. Things that were covered up before (like the arm behind the body) have their light values blended onto the image anyway. It creates a really bizarre ghostly image.

While this may be a cool effect for some of the more bizarre Lovecraftian horrors, it seems like a bad fit for any protagonist who isn't Ghost Dad.

While this may be a cool effect for some of the more bizarre Lovecraftian horrors, it seems like a bad fit for any protagonist who isn’t Ghost Dad.

The good news is that after spending almost two weeks trying to fix this issue, I have something that works. It’s not ideal, and creates some odd graphical artifacts that I haven’t exactly figured out how to remove, but it works. The strategy here was to explode the Spine model on the z axis by a very small fragment so that each piece was on a different plane. This is irrelevant for rendering position, since the orthographic camera used for 2D ignores the z axis, but it lets me implement z-axis sorting for determining which pixels to write. Thankfully it looks like the guys over at Esoteric Software had planned on adding this as a feature at some point, and changing the runtime to make this work is literally a one-line change. Using this, I can test for the z values at each pixel to determine which object gets drawn and only draw that object. The problem is that I can only pick one object, and it’s all or nothing. This means I lose the translucent anti-aliasing effect on the edges of each object, since they can’t blend down to the next lower object because it isn’t even processed.

The hard edges are like knives in my eyes. On the plus side I get rim lighting for free. I have no idea where that effect came from, I sure didn't do it.

The hard edges are like knives in my eyes. On the plus side I get rim lighting for free. I have no idea where that effect came from, I sure didn’t do it.

It’s functional, and I definitely prefer it over the bizarre apparition it was producing before, but I would love to lose those hard edges and weird unlit pixels on the fringes. I think I can fix some of them, and with how dark the game will be, the hard edges shouldn’t be too noticeable, but settling for less than ideal always stings. This works for now, and it may be what the game ships with barring a few bug fixes and optimizations. Either way, it’s off the plate for the vertical slice and I can finally move on to other things that aren’t lighting.

Sneaking, Walking, Running

The next step in creating something that looks presentable is creating a character that moves naturally. While I was working on the lighting system, I was continually tweaking the walking animation. It’s in a place now that I’m pretty happy with, but there’s a lot more to this game than just walking. I have laid out a list of animations that I need to create to handle all of the gameplay systems that will be in the slice, and though there’s quite a few, creating and tweaking the animations is incredibly easy with Spine. Here are the walking and running animations that I have so far, and over the next week I hope to add jumping, sneaking and maybe some of the ledge animations.

I should be back next week with more updates, and hopefully a real name for this game. I’ve got something picked out, but I have some paperwork to do before I can announce it. For now, though, I have to fix the tear in those pants.

I mentioned in my post last week that I was on the fence about purchasing Sprite Lamp. I’m happy to announce that fence is long gone. After a cordial interaction with the developer, I went for it. This post is going to be mostly about that, so there will be lots of pretty pictures.

Getting Started

After getting my download link and cracking open the software, I was immediately struck by the fact that I had no images suitable for lighting. The body work I had done in the past was fragmented and didn’t apply to the new Spine animations. I wasn’t sure how this would work with the vector graphics style I had going for my images so far, and I had no idea how to actually shade anything in that style either. I sketched out the outline of a Corinthian column header, exported it into gimp, and set to work trying to make gradients wrap around complex shapes. Needless to say, this didn’t work. I found a plugin that did a good bevel effect and set to using that to shade my object. It sort of worked, but it felt very round and fuzzy.

Initial inputs and static output. Apparently I can't tell left from right at times.

Initial inputs and static output. Apparently I can’t tell left from right at times.

Not so much teddy bear fuzzy, as doesn't brush its teeth fuzzy.

Not so much teddy bear fuzzy, as doesn’t brush its teeth fuzzy.

It worked, sort of, and I had an object reacting to the light. I was ecstatic. I knew I could do better though, so the next day I set out to do just that. I had always wanted something closer to cel shading than normal lighting for this game, and getting smoothly-lit input images had been an incredible pain anyway. I decided to try and bake the cel shading into the lighting images used to generate the normal maps. This carried a couple of benefits. The first was that I no longer had to deal with creating perfectly smooth light maps. Creating cel-shaded input images in inkscape is pretty easy compared to making something perfectly smooth by hand or with linear gradients. It also means I don’t have to switch tools half-way through the process. The second benefit is that I can get something sort-of like cel shading without the somewhat erratic lines of light that normally come with those types of shaders. I wanted to test this quickly, so I made something very simple.

Clearly my mastery of lines and circles shows how great of an artist I truly am.

Clearly my mastery of lines and circles shows how great of an artist I truly am.

Painstaking Detail

This proved the concept, but it didn’t exactly look amazing. It looks closer to claymation than it does to cel shading, but I was pleased with it nonetheless. To make sure that the style held up in more complicated pieces, it was back to the column header. This took quite a while as I’m no master artist. Figuring out what the shapes should actually look like with orthogonal lighting was the biggest challenge; there aren’t a lot of references with that kind of lighting. After several hours tweaking nodes, I felt like I had something that might be passable. I have to say that I’m shocked with how nice this turned out, though I guess I wasn’t expecting much.

It kind of looks like a bucket. Catch the falling Cthulus mini-game, anyone?

It kind of looks like a bucket. Catch the falling Cthulus mini-game, anyone?

Apparently it just needed a new toothbrush.

Apparently it just needed a new toothbrush.

Lurking in the Shaders

With that, I decided I was content with my asset creation pipeline and decided to actually try and put this into the game. One of the key question I asked the developer before I bought this software was if it had an implementation for Unity. He said it had one, but it wasn’t fully done, and it wasn’t a top priority. Ok, not a big deal, I can work with partial support. It turned out though that partial support meant something different to me than it did to him. Hard edges on lights, no alpha transparency support, and a general approach that didn’t look like it was actually built for unity. I was a bit dismayed, but to his credit, he did warn me. I initially tried to get it working as-is, and when I saw that lights just stopped at their edge instead of falling off I knew I was going to be writing shaders for the rest of the weekend.

I kind of feel bad for that one off to the right. What did he do to deserve being ostracized?

I kind of feel bad for that one off to the right. What did he do to deserve being ostracized?

Prior to this weekend, I had never touched 3D lighting. I’ve dabbled in shaders for special effects, but dealing with lights was completely foreign to me. The included implementation had a whole lot of vector math that I wasn’t comfortable with, so I prepared myself for the long haul. Just getting it to where I had it had taken the better part of a day, how long would it take to make a new one from scratch? Not long at all, it turns out. Unity does, occasionally, make something really easy for me. The built-in shader lab made getting that shader up and running incredibly easy. It doesn’t support all of the features that Sprite Lamp offers, but for my purposes, it’s perfect. In a matter of a couple of hours, I had every feature besides shadows, depth, and pixel snapping up and running. A few minutes later and I had the whole thing integrated into my existing project.

This is actually an awful screenshot to show off the shader. Programming: A+. Media: F-.

This is actually an awful screenshot to show off the shader. Programming: A+. Media: F-.

It felt like a very productive week, and I’m looking forward to working on integrating spine, and getting my procedural decorator up and running in the coming week. These should be the last two graphical development pieces for a good long while. After this it’s all content and gem programming. This is when things get really exciting.