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.

This past weekend I attended PAX South in San Antonio Texas. It was the first time I’ve been to a gaming-related expo, and I was a bit blown away. My primary goal in going was to scope things out in preparation for exhibiting Kilstow. I saw a lot of great booths, and a lot of great games, and I’d like to talk about some of the better ones and the things I observed about the games and the booth setups. I took a bunch of pictures, but as they were with my cell phone they didn’t exactly come out great. Instead I’m going to use some of the promo imagery for these games.

The Adventures of Pip

Adventures of Pip

by Tic Toc Games

 

The Adventures of Pip is a puzzle platformer by Tic Toc Games. The core mechanic revolves around transferring the character between different eras of video game graphics. In each different form, the character has a unique set of abilities that have to be used to solve various puzzles. You can move back a step in the evolution at any time, but to move forward you have to kill a glowing enemy, which led to some interesting puzzles in the demo they had available. While it’s a not exactly the most innovative game out there, the graphics-switching mechanic was well thought out the whole thing was very highly polished.

The booth setup left a bit to be desired. There were two stations to play at, but the monitors were just on the table which made it hard to see if there were more than a couple of people there. A raised TV stand would have been a great way to let people passing by see what the game was all about. It also helps make the wait time a bit more bearable for those in line to try it out. Other than that it was a better setup than most I saw at the show, and with their location right behind the indie showcase it had a crowd every time I walked by.

Light Fall

by Bishop Games

by Bishop Games

Light Fall is a puzzle platformer by Bishop Games. The defining feature of this one was a cube that you could summon out of thin air to help you get around. It worked as a non-standard multi-jump, in that pressing the jump button would summon the cube and snap it to right below you up to four times in a row. You could also summon the cube and move it around to scout out the map, block hazards, and set up an extra jump for precise navigation or extra range. My favorite part was manipulating the fact that the cube spawned away from you and snapped to your position when you used it in the air, as it would allow for fancy wall jumping or allow you to gain incredible momentum, though that last part may have been bug based on my conversation with the developer.

These guys had pretty close to the perfect booth setup. Both play stations had raised monitors on stands, and the table in the back of the booth was free for conducting business or laying out business cards and other informational material. The only downside was the fact that since the table was in the back, you had to walk between the crowded stands to get to the business cards, but since they ran out on the morning of the second day it was less of an issue. Since they were on a corner booth they had a bit more space to work with, but the idea of the setup was sound and could be adapted to a middle booth. They also didn’t have their company name and logo displayed prominently (it was at the bottom of their standing posters), but since it was on their shirts it wasn’t a huge problem.

Hive Jump

by Graphite Lab

by Graphite Lab

Hive Jump is an action shmup with roguelike elements by Graphite Lab. This one I had actually played before when I backed them on Kickstarter, but they put on a great show over the whole weekend. You explore a procedurally generated alien hive with a group of four jumpers trying to get a special backpack to the bottom. When a player dies, they respawn at the backpack as long as it’s safe. If the player carrying it dies or drops it, then the aliens can destroy it and the respawns stop.

The game is amazing, and it’s perfect for the kind of atmosphere you find at shows like this. Four player co-op meant one huge TV could serve both the players and a crowd of fans watching. Fast-action shooting with high stakes and quick upsets meant the crowd could really get into the game just watching. They had four small padded cubes in front of their massive TV, and the whole thing was just set up perfectly. While I don’t really have the same type of game and thus can’t really do the same thing, it wasn’t particularly helpful, but it was striking how well they set things up.

There were more, but those were the most popular with the best booth setups. Since this PAX was focused on tabletop games, there were a ton of great booths for board games and card games that were simultaneously awesome and completely unhelpful. I only saw one other horror game there, and it was so early that it didn’t really have anything to show and you could tell from a distance. The guys were really passionate about the game, and it sounds like it will be awesome in a year, but it’s hard to glean any useful tips on how to show an atmospheric horror game at a trade show from something so early in development.

All told it was a fantastic trip. I ran into Jerry Holkins on the floor just walking around and chatted with him for a few minutes about running a booth at a show and a little bit about food in Texas. I also got to talk to a lot of developers that I had seen floating around twitter and reddit during the show, and it was nice to be able to put names to faces. Hopefully I can get my stuff together and join their ranks soon, because seeing all of those people and all of the amazing work they’ve done was incredibly inspirational. Now that I’m back home, my schedule has normalized, and I’ve finished the last of the engine modifications to make Unity let me do what I want, it’s time to start the fun work of actually making this game.

It turns out that PAX is a much more exhausting event than I anticipated. There is so much here going on that I wasn’t expecting, and I’m more tired than anticipated. As a result my brain hasn’t really processed everything that’s happened yet, so it’s hard to form a cohesive summary of the events. Since I fell asleep last night before writing anything and I don’t want to be late to the party today, I think the nightly recap is going to turn into an event recap. For now I need to get charged up and head back down, there’s so much more to do still.

I wanted to write a quick update here for all of you that don’t read the twitter feed. In the past two months I’ve been pretty busy with life, and my game development efforts have taken a hit as a result. Such is the life of a solo developer. My wife and I bought our first home in December and just finished getting all of our stuff moved over. We also had a friend staying with us during that time who was having some issues in his personal life and needed a place to stay for a while. He has since moved out, and while we still have a bit of unpacking to do at the new house, my office is all set up. Next week life should return to something close to normal and I can get this crazy game development train back up and running at full speed.

For now though, I am at PAX South. I’ve never been to a convention of this size before, and never to one that wasn’t aimed at professionals. I’m excited to see what all goes on at a place like this, and to check out the booths of my fellow (if a bit more successful) developers. I would like to eventually present at a convention like this one, and while I’m not quite ready yet, I wanted to come take a look at how they work from the other side first. This way I can soak it all in and see what it’s like without the stress of having to run a booth as well. A little vacation after what’s gone on in the past couple of months won’t hurt either.

I’m going to try and stay active during this event, on twitter during the day and maybe a recap each night. I’m already feeling excited and ready to jump back into my work when I get back. For now though, I have to get going; I’m sure the line is already a mile long.

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.