How I Learned to Stop Worrying and Love Prefabs

The level generation in Golden Krone Hotel has kind of sucked for a while.

For the 7drl version, I wrote a quick and dirty level gen system. It could make connected rooms and hallways, true, but the results were really kludgy looking. Rooms would overlap each other willy nilly. Hallways would be ridiculously long. Sometimes the levels would be much too small. They also tended to be very boxy (due to a very naive sunlight implementation).

ewww

Later I swapped in ROT.js map generation algorithms and for a time things seemed rather decent.

There were still a few quirks with the ROT.js maps though. Way too many hallways for one. The hallways often looped in on themselves and players were well aware of it. Dead ends appeared too often. And of course, using a simple level generation algorithm produces a bunch of samey levels.

The last straw was when I took screenshots of each level. At first, I thought the result was pretty cool. But the more I looked at it (and compared to the amazing diversity of maps in DCSS), the more I hated my crappy level generation.

Kind of samey

Prefabs to the rescue.

OK, so it was clear I would need a new level generator. I had been hearing tons of chatter about “prefabs” (hand crafted map components). Josh Ge has a bunch of posts on them and I found this talk by Jim Shepard particularly great.

So maybe the time was right to finally start utilizing them. Hmmm… prefabs sounded cool but damn complicated. How would I design prefabs and how the hell would the algorithm fit them into the rest of a level? Was this huge detour into rewriting a working system even worth it?

Spoilers: it was.

Let’s go over all the benefits that were realized by incorporating prefabs. Then we’ll cover how it works in detail.

It helped massively with the tutorial

Tutorials are sort of a nightmare. You have to plan for every contingency, every single way the player could screw themselves. It’s not impossible to have a procedurally generated tutorial, but I certainly wouldn’t try it. Instead the tutorial is one giant prefab.

Levels are less boring

My main goal was simply to make levels less boring. That was pretty easily achieved by having rooms that extended beyond rectangles: triangles, diamonds, crosses, circles (no worries, rectangle fans, we still got you covered). Even better than generating new room shapes is creating interesting encounters like a monster closet or a room with pits surrounding an item.

Branches actually feel unique

Branches play a very important role in roguelikes: breaking up the monotony of regular floors. To give players a proper break, it’s vital to make branches feel distinct from the regular dungeon and from each other. There are many tools to distinguish branches: monsters, music, floor and wall tiles. I was using all those, but without distinct map styles, branches in Golden Krone Hotel were still feeling too much like palette swaps of regular floors.

Now the Pharmacopoeia has circular chambers. The Greenhouse has flowerbeds and fountains. The Graveyard has a sensible and cool looking entrance to the Mausoleum.

I have a powerful tool for controlling the theme, pacing, and drama

In my favorite roguelikes, branches are more than an extra scoop of content. They each have a central challenge that has to be solved. At the heart of that challenge is usually a special boss monster(s) and a special area to house them. Basically we’re talking about a set piece.

A good example is the Vaults in DCSS. As you climb down to the last level, you find yourself surrounded by dozens of vault guards standing in formation and a bunch of other high level baddies. Sometimes you’ll try to run away, but the staircases will be sealed off. It’s not just cool gameplay. This encounter in Vaults:5 actually makes it feel like you’re in a vault.

Creating such a scenario is much easier with prefabs. They let you precisely control the space (determining tactics), monsters, bosses, and environmental dangers. Even the torch light can be controlled. Here’s some examples of set pieces I’ve created using prefabs (mild spoiler warning by the way):

The boss room in the Mausoleum. It’s wide open, which is dangerous because the boss spawns more vampires. On each corner is a twisting hallway to a room filled with treasure.

The central room in the Gallery. It’s a big, rectangular room with “display cases” on both ends. It’s actually possible for the Gorgon Queen to blast open those cases on accident. Along the perimeter of the room are columns, very useful for breaking line of sight with the boss.

Floor 10. You approach Fane and find him enveloped in darkness. You can have the whole conversation this way, with your character in the light and his in the dark. METAPHOR MAYBE? On both sides of you are torches, which can be lit simultaneously if you desire. Interestingly enough, torches are never generated that close together normally because it creates an ambiguity in which to light. I’m so damn happy with the dramatic flair this scene adds.

Mazes

One last bonus: mazes are easily generated using a single tiny prefab. And yes, the game will eventually have a maze!

https://pbs.twimg.com/media/CzZssOZUkAE9MdE.jpg

 

“Text files are nature’s most perfect fruit.” – Jim Shepard (Dungeonmans)

The process

  1. Load prefabs. Each prefab is stored in a plain old text file. Make a connection object for each “*” found, saving its relative location and directional facing.
  2. Generate “auto-rooms”. Since the entire generation is now dependent on prefabs, I generate a bunch of rectangular floors and save them as if they were real prefabs. I’m sure there’s a better way to do it, but this works. Other shapes could be generated this way too, but are more difficult to get right.
  3. Grab the level configuration. With this last release, I finally found all the scattered configuration code and put it into level config files. Super useful!
  4. Pick a starting prefab. The starting prefab will often be the important “set piece” of a branch, though any ordinary prefab can also be picked if none is specified in the configuration.
  5. Place the prefab on the map.
    1. The classic ASCII symbols like #.~> (wall, floor, water, stairs)
    2. ? for “don’t care”. Usually ends up being a wall (the default tile type), but this allows flexibility in overlapping prefabs.
    3. 0-9 can map nicely to 10 values without needing 10 case statements. I reserved these for floor type. For example, in the greenhouse, the default floor is grass, but I also mix in stone walkways and flowerbeds.
  6. Randomly pick a new prefab from the list of prefabs defined in the current level config. And also pick one of the existing prefabs on the map to connect to.
  7. Starting from a random connector, extend a hallway out. First the hallway is made as long as desired and then scaled back incrementally until the prefab fits on the end of it. It’s possible for hallways to be 0 length, if the level config allows for that. If it doesn’t fit, just scrap this hallway/prefab and move on.
  8. Jump back to step 5. Keep going until enough prefabs have been placed on the map or we’re timed out.
  9. Now that all the prefabs are placed, we want to enable more connections to minimize backtracking. There are three types of connections made:
    • Any connector that is flanked on both sides by floor can be made into a floor or door.
    • If two connectors face each other, a hallway can be dug between the two.
    • Two perpendicular connectors can meet through a L-shaped hallway.

A few remnants from the old system still remain. Some of the levels are generated using the old algorithm, just to increase the overall variety. Finally, many levels are expanded by randomly placing down rooms over the existing ones in order to make the levels more open (and more dangerous).

All in all, the minimap is looking quite different these days.

7 Reasons Save Systems Are Garbage

I like making small games. I’ve never even thought about a save system and no one has ever asked for one.

But Golden Krone Hotel is getting bigger than other things I’ve made. I’ve been surprised by how long some runs take players. It only takes me an hour to beat the game (and usually 10 minutes to die a horrible death), but some players were reporting 5 hour runs. Lots of people were asking about saves.

Sure, let’s write a save system. How hard can it be?

1) It seems easy, but it ain’t

Find all the state in your program, save it, and then reload it again. Seems easy. But if you try to do this late into a project as an afterthought (as I did), you’ll almost certainly forget how much state is actually in your program.

That’s because the better you get at writing encapsulated code, the more you’ll shelter yourself from the complexity horrors lurking inside each abstraction. You’ll forget about how much stuff is going on behind the scenes and how tedious it would be to track all of it down.

But track it down you must. Writing a save system is like getting a take home exam that requires a perfect score to pass.  If you load one thing incorrectly, your game will malfunction in subtle ways or, if you’re luckier, crash spectacularly.

2) It’s coupled to every part of your game

By definition, the save system has to have its fingers in all your program’s many pies. The only exception is temporary state that can be easily reloaded. For certain types of games, that may be a pretty big exception: think of Super Mario Bros. where only a few numbers needed to be saved (current level, number of lives, etc.).

For a roguelike with permanent levels, however, there’s a lot of stuff. My game has roughly 15 levels with 40×40 tile maps. That’s 24,000 tiles, not to mention:

  • Monsters
  • Items
  • Learned spells
  • Learned abilities
  • Potions
  • Status effects
  • Player stats

Floors in Golden Krone Hotel

Every level currently in Golden Krone Hotel

It’s easy to get tight coupling between the save system and all those different modules, which can make the code very brittle.

Now if you’re smarter than I am, you would think about how to centralize all your state at the beginning of your project. Josh Ge describes such a method and it sounds pretty great (though I’m still thinking about it would be properly implemented in a language like JavaScript):

All objects are stored in allocated memory pools and accessed via handle/ID (in other words, I don’t use pointers), so when you save the game, regardless of how many references there are to objects, all you have to do is save the memory pools and reload them when starting up again–bingo any references are still intact, cyclical ones and all. (I’ve got plenty of cyclical references and don’t have to worry about them getting out of whack.) It’s a really powerful idiom; learned it from one of the old Gems books.

On the bright side, revisiting almost every line of my project helped me clean up a lot of dead code. 😑

3) Debugging it is a nightmare

Halfway through this save endeavor, I realized it would be much easier to save parts of my game by recursively visiting objects and their properties.

Save functionThe bulk of the work is done by this one function

Automating that work was a big win, but it makes debugging pretty awful. I would regularly crash the browser (having never received a useful error message, I’m guessing it was through many a stack overflow).

Some bugs were hard to reproduce too. One required multiple save/loads before showing up. Others only arose when interacting with rare in-game items.

4) Circular dependency hell

“Experience keeps a dear school, but fools will learn in no other.” -Benjamin Franklin

Yup, that’s me. I often have a hard time accepting a design pattern until I feel the same pain that instigated the design pattern in the first place. Well, save systems provide the pain.

I’m fond of circular references, despite many people considering it an anti-pattern. A tile needs to know what monster is standing on it and a monster needs to know what tile it is standing on. So what? Well here are two big problems.

First, if you recursively visit an object/array and all its descendant properties (and some of those properties are circular) you are guarandamnteed to get stuck in an infinite loop. You can bail out of such recursion by keeping track of which objects you’ve visited, but then you skip saving certain things. The essence of the problem is that pointers just can’t get serialized and deserialized.

Again, this would be solved by Ge’s solution described earlier. What I came up with is also a handle system, just one that’s constructed on the fly solely for the purpose of saving. Whenever I encounter an object, I store it in a map. If I encounter a direct reference to that object again, I replace that with an indirect reference to the object map instead.

The second issue is rebuilding the objects. Going through this process helped me understand a lot about dependency injection. The problem is summarized quite simply:

Foo(Bar b){
    //do stuff
}

Bar(Foo f){
    //fuck
}

I can’t construct either of these objects before the other. There’s no way to square this circle.

The answer is to create separate functions that do the work of the constructor and can take in circular dependencies (it’s fine as long as we’ve first constructed the objects). I name these methods finishWiring and during loading it’s easy to find out which objects still need to be wired up.

5) Fast, good, cheap. Pick any NaN

Several painful trade offs are involved in a save system. I started out with saves about 30MB each, which seemed pretty high.

I was able to get the saves down to 7MB through a few optimizations, but like any other optimization, it caused readability to go down. Save files got down to just 300KB after compression. That’s definitely a number I can live with, but compression (I used this LZW library) takes a few additional seconds and that sucks.

6) It can make your code worse

Several of my optimizations produced some rather ugly code as a byproduct:

  • I had to mark temp variables that I wanted to totally avoid saving. I did this by preprending variable names with an underscore.
  • I removed default values of variables when those defaults were 0, false, or null. Fewer variables on each object means fewer things to save, but much more confusion.
  • When creating my object maps during saving, I compressed the property names of all objects using base 62 (using a-z/A-Z/0-9 as digits). It saved a good bit of space, but made debugging much harder.

I’m also considering generating levels on the fly so that early saves are tiny, but that will introduce more complexities to the level generation.

7) You’ll wonder if it’s even worth it

In the depths of debugging this mess, I often questioned if this was really worthwhile. These thoughts popped up regularly: How hard is it to just leave the window open? Is it really such a burden to carve out an hour to play the game?

It’s hard to maintain motivation in such times. I could just scrap the whole thing and pretend like it’s not a big deal.

But then I thought about a discussion I once had with a developer at a conference. He was asked by his players to introduce saves and he refused. He almost seemed offended that they would ask and gave all sorts of weak justifications against it. Thinking about how I play games and about my response at the time (“is that really rational… or is it sour grapes?”) made me realize that saving is something players deserve, even if it’s a huge pain.

Feel free to tell me about how much you love writing save systems in the comments. And if you want to see how my system turned out, check out the latest update to Golden Krone Hotel.

Making a Title Screen

Golden Krone Hotel is nearing release on Early Access and it’s gonna need an honest-to-goodness title screen. I think I’ve come up with something pretty cool, so here’s a post showing how it was done.

huge

click to embiggen

I’m often overwhelmed when I see big pixel art pieces. I hope breaking it down step by step makes it seem a little less intimidating. The thing about pixel art is it’s very procedural. Much of the work behind making pixel art is just following a series of simple procedures (proper outlining, anti-aliasing, shading, etc.) I don’t consider myself an artist in the slightest, but I’m usually able to get some OK results by just following the right steps and having some patience.

A little context

During game jams, I typically just slap some stylized text on a plain background. Here’s Golden Krone Hotel’s old title screen:gkh-original

I’m happy with the creepiness factor (all accomplished with a little CSS magic), but it’s otherwise pretty  boring. I needed something that establishes the setting, theme, and style of the game all at once. Dumping text on the screen doesn’t do that.

I got slightly more elaborate during the Greenlight campaign:

greenlight

Obviously, I made that rather quickly. It is closer to the end goal. Let’s be honest, I’m basically trying to evoke thoughts of “Dracula’s castle.” This image establishes the theme and setting (a creepy tower), but it doesn’t look very professional.

I decided to follow the same idea going forward but with the the whole thing completed fleshed out. No silhouettes. No MS Paint moon. I wanted to leave room for animating it all, so I knew the following layers were needed:

  • Background
  • Clouds
  • Moon
  • Mountains (multiple layers)
  • Cliffs and path
  • Castle
  • Logo

A lot of work, but I slowly chipped away at it over several weeks.

Putting in constraints

First things first. At the beginning, it’s a good idea to decide on the resolution of the final piece. I looked up the display resolution of SNES and arrived at 256×224 (which I later expanded to 400×224 to match wide screens). It’s not that I consider my game to be “retro”, but people will often label any 2D pixel art game retro anyway. Why fight it? Besides, constraints are super helpful. That’s already about 90,000 pixels, each of which I have to make a conscious decision about. If I tried to draw a piece at the resolution of my monitor, 1920×1080, now we’re talking 2,000,000 pixels.

Also a note on colors. I’ve been using two techniques recently for picking colors and I’m loving the output.

The first is blending between two colors.

The second is manually shifting the hue (towards either yellow or purple) and saturation as you change the lightness of your color scale.

Humble beginnings

Besides a few scribbles of the basic shapes (mostly fitting into a big ass triangle), here’s the first thing I drew:

 

starter-castle

I outlined the major shapes of the hotel, which has also functioned as a cathedral and a castle in the game’s backstory. My goal was to demonstrate the height of the hotel and to simultaneously make it feel sprawling (so there is plenty of room for many floors and branches). There’s a bit of symmetry but I also wanted to break that up.

The sketch didn’t look amazing, but at least I had a nice method for coloring the stones of the castle: creating a bunch of 4px tall stones, trying to avoid them looking too perfectly rectangular, and adding a tiny bit of highlight here and there. Adding some occasional darker shadows in the cracks between stones gave it some more depth.

Here’s the castle after continuing the stones and adding an elaborate stained glass facade:

mid-castle

One of the hardest parts was settling on a method for detailing the roofs. Sometimes pixel art is just trial and error until something looks right. I tried all sorts of diagonal roof tiling, but it kept looking awful. I settled on a simple horizontal tiling with alternating dark/light lines.

roofs

 

And here’s the final version. I added a few details such as a sloped wall, a portcullis, statues, and stairs. I also added a second background tower on the right to give the whole place more depth and really tiny doorways to try to establish the scale. Otherwise, it was just a tedious process of filling in the remaining stones and roofs using the same procedure I had already figured out.finished-castle

At this point, I decided to sketch out the rest of the piece. I wanted a giant, clearly unrealistic moon.

background-start

Then it was onto finishing the mountains. The back 2 layers aren’t that complicated. The farthest has a single color and the middle one only has two. The foreground mountains are a little more detailed.

The home stretch

cliffs-start

I’ve never been really great at mountains. I found this image really helpful to use as a reference though. I chose the light source to come from the left (which maybe sort of makes sense with the off center moon?). Basically, that means a bunch of little pyramid shapes that are mostly lit only on their left sides. The shapes obscure each other and have their own little cracks and details. The right side of each peak is mostly left with the darkest color and almost no detail. That was a little hard to live with at first, but those big open areas of solid color work really well.

mountains

These cliffs were really challenging! The process boils down to drawing little vertical protrusions/ridges that stick out from the bottom of each cliff. As I finished off the cliffs (and started looking at reference photos), I also tried jamming a bunch of almost-square rocks together and that worked great. As you look further down the cliffs, they start to lose the highlights and the shadows dominate until it’s a solid color just like the mountains.

cliffs

Even with clouds, the sky was going to need a bit of detail. A few years ago I would have tried a big gradient but that that can look really bad. I looked at a few pixel art works that depicted night skies and noticed a recurring pattern: layered, bubbly clouds with very low contrast between each layer. If you’re not looking for it, it’s difficult to see these details in the final piece. Yet they’re truly necessary.

background

Moon time. It was obviously helpful to look at photographs of the moon. I noticed a few details:

  • Huge dark splotches
  • Lots of craters big and small
  • Lighter starburst patterns

900px-LRO_WAC_Nearside_Mosaic

Humans are pretty bad at generating random patterns. I didn’t think I could do those dark splotches justice. Thus, I turned to a nifty feature found in most graphic programs: difference clouds.

difference-clouds

Besides the features described earlier, I also shaded the moon and added dithering between some colors. Gray was only a starting point by the way. Colorizing an image in tools like GIMP is really easy. I tried out blue, purple, silver, and even blood red. A bright yellow, almost washed out, ended up looking the best.

moon

I was not looking forward to drawing clouds at all. Clouds are weird.

I had to study a lot of reference images to figure out what was going on. And it’s surprisingly hard to find good photos of clouds at night. Finally, I realized something important about shading clouds. When the sun/moon is directly behind the clouds, they don’t have highlights around the edges because that’s the direction of the light source. They look brightest there because the clouds are thinnest there. So that’s logic I tried to use. I initially had highlights on the bottom of each cloud too, but I removed them so that overlapping clouds would blend together better.

clouds

Final touches

I certainly needed to come up with a cool logo. Since Dracula is set in the late 19th century, I googled for “19th century signs” (I have absolutely no idea if any of these are actually signs made in the 19th century):

oldsigns

Anyway, one thing most of these signs have in common is curved text. I drew curved guides and lined up the text to fit them. Then, the “Hotel” fit nicely in the pocket below the rest of the text. There was still the work of manually adjusting the features of each letter to line up flush with the guides, but I was able to do that with the pen tool.

text-wavy

I thought about making detailed gold lettering (like the Shovel Knight title screen), but fuck it. I was getting a bit lazy at this point and, anyway, doesn’t the Street Fighter II logo look awesome? So I put a orange-yellow gradient on it, a black outline, and a prominent shadow for readability. Done.

streetfighterii

The last step was animating everything. I’m not sure if it’s clear or not, but the idea is that we initially see a timelapse (the moon rises and the clouds move fast) while the camera approaches the hotel. I wrote a little code to randomly place the clouds and move them across the screen at different speeds. I wrote a little more code to move everything into its final position. All of it was pretty simple.

The art is scaled in integer multiples (e.g. 2x, 3x, never 2.5x) to maintain the crisp edges. Depending on your aspect ratio, either the top/bottom or left/right edges of the screen can get cut off, especially if that ratio diverges far from 16:9. However, there’s never any black bars or other such nonsense.

So there you have it. I hope that’s helpful for somebody. Let me know what you think in the comments.

title3

Project Update and Conversation Display

I haven’t updated the blog in a while, but don’t worry! I have been quietly plugging away at the game.

Since my last post, I’ve rounded out the spells and potions (for a total of 20 spells and 40 potions). I’ve added a revolver, shops, chests, water, noise, damage indicators, and a boatload of other features I honestly can’t even remember.

I did experience some slowdown around 7drl. In case you missed, I made a pretty crazy game about time travel called The Only Shadow That the Desert Knows. I also wrote a blog post about it (on my other blog) and it hit the #3 top post of all time on /r/roguelikedev. 😀

Nearing the finish line

To add some more transparency to the development, I’ve created a list of public milestones.

As you can see, I only have a few more things before I want to release on Steam Early Access. Mainly they have to do with polishing up the remaining parts of the UI. And of course, doing a ton of balancing and testing. If you’re interested in playtesting, let me know!

This week I’m working on conversation display.

Conversations

Right now, you can talk to any vampire or human in the game (provided you’re the same form at the time). The implementation of the dialogue has not been great though. Lines of dialogue got dumped into the message log and most people ignored it.

So I decided to make conversations more prominent and to give them that cool typewriter effect you see in old RPGs.

There are a few steps to achieving the typewriter effect.

Streaming characters

Obviously, the characters come out one at a time. That’s easy. The hard part is preventing weird line break behavior (visible in the video below). Words at the end of the line often jump to the next line as they run out of space. If only we could give words the same width even before they’re fully revealed. Luckily, that is easily achieved by displaying the yet-to-be-displayed characters as non-breaking spaces. Yup, it’s our old friend:

&nbpsp;

Note that this method is only guaranteed to work with monospaced fonts.

Beeping

I create the shortest sounds I could on Bfxr. At first I thought multiple noises would be needed, but one seemed to work the best.

When to play the beeps? One option is to play on every character, or at least every non-space character. That seems to be the approach in this video. What I did instead was only issue a beep when the ascii code of a character is odd. The end result achieves several things:

  • Reduces the rate of beeps to avoid them all bleeding together
  • Avoids beeps on whitespace for free (ascii code: 32), which makes sense
  • Gives text a rhythm that is analogous to actual speech
  • Produces deterministic patterns of beeps, so repeatedly viewing a line gives the same rhythm

The effect is pretty damn cool if I may so myself.

 

Tightening up the Graphics on Dungeon Floor 3

This post is about how I improved the graphical features in a simple HTML5 game. I did so by, among other things, adding a 2.5D perspective. But more importantly it’s about how I optimized the performance of said graphics. If you’ve ever written a 2.5D game engine, you probably know exactly how to do this. If not, read on!

cache-old

Last year, I entered the Seven Day Roguelike challenge with Golden Krone Hotel, a game about killing vampires with sunlight. It was well received, despite being completely 2D and having lo-fi pixel art and no animation. What can I say? The roguelike community doesn’t expect much when it comes to visuals.

cache-new4

This year, I decided to turn Golden Krone Hotel into a polished, commercial game. To appeal to a wider audience (one not content with ASCII graphics), I felt that the following features were needed:

  • 2.5D perspective. Game objects that can obscure other objects behind them, producing an illusion of depth. Tall entities (e.g. big monsters)  to emphasize the depth.
  • Smooth movement between tiles
  • Animated torches and spells
  • Previously seen tiles, which appear desaturated (common in roguelikes but I didn’t have it originally)
  • Increased visibility radius and fullscreen display

To reiterate, Golden Krone Hotel is an HTML5 game. It runs in JavaScript and is rendered in the canvas, which is known for being…. well, not as fast as one would like. To make matters worse, I’m distributing the game with a library called NW.js. For reasons I don’t quite understand, executables that come out of NW.js take a noticeable performance penalty compared to the same app running in Chrome. Ouch.

HTML5 nw

In 2014, this was no problem. That version was very easy to render. I only had 121 tiles on screen and they only needed to be rendered when the player moved.

The 2015 version was much more complex and slooow. I now had to render over 3 times as many tiles. I also needed to do it 60 times per second. To make matters worse, I was relying on some costly composite modes. Even on my gaming desktop, the performance wasn’t great and I knew it’d be much worse on older computers.

First let’s talk about how the new features work.

2.5D

The primary thing required for 2.5D is to render your objects in order from back to front (top of screen to bottom of screen). Not a big deal, right? Then things get dicey. You can’t just draw all of your floor/wall tiles and then draw all of your monsters on top. That wouldn’t allow walls to be in front of monsters, defeating the purpose of 2.5D. Instead you must group objects (walls, monsters, spells) into rows and draw the rows in order.

row
A single row

Smooth Movement

It sounds easy on paper. When a monster moves to a tile, you assign them to the new tile, but you also draw them with a corresponding (x,y) offset. For example, moving 1 tile to the right produces a (-1,0) offset. Decaying the offsets to 0 automatically slides the monster around.

smoothmovementComplications:

  • The player’s offset needs to be added to the camera itself, so the camera isn’t jerky.
  • In the naive approach, monsters going around corners appear to take diagonal shortcuts. To fix that, you’ll need arrays of offsets that decay one at a time.
  • When you add in the 2.5D perspective, you can no longer draw a monster in the row where it ends up. When I tried it initially, monsters moving vertically would get hidden behind floor tiles. Woops! The solution is find the maximum Y coordinate a monster reaches in an animation and draw in that row instead.

The root of all evil

efficiency

I went as long as possible without obsessing over performance, but at some point I realized I simply can’t ship a game this slow. Tuning the performance of my game was a slow process filled with confusion, frustration, and self doubt. But I’m happy with the end result and I learned some things along the way:

  1. Always determine where you need optimizations. It’s too easy to focus on the wrong parts, the parts that will never help you. See: Amdahl’s Law
  2. Always verify that your optimization worked. It feels good to come up with some clever trick and move on, but sometimes you’ve actually made the program slower.
  3. Remember that optimizations are tradeoffs. You lose debuggability, readability, and valuable development time. You damn well better get something good in return.
  4. Small mistakes (like forgetting to swap out some test code), can totally murder you. This happened to be me several times. It’s hard to detect without profiling because the program still behaves correctly.

To summarize: Never make assumptions. Profile, profile, profile.

The quickest way to profile is to use in-browser tools like Chrome’s profile tab. However, it can be difficult to interpret the results. When that fails you, you can get a better picture by writing your own profiling code. Performance.now() is pretty great for this.

Onto the optimizations:

Separate rendering into two buckets: animation and turn

Objects that are animated need to be rendered every frame. Objects that only change when the player takes a turn, such as the minimap, only need to be updated once per turn. Maybe the distinction is completely obvious, but it took me a while to conceptualize it and then hunt down all the bits that were being rendered too frequently. This separation is the single most important performance enhancement that I made.

Buffers

Tiles don’t change during turns, but they do move every frame while the player’s position is being animated. The solution is to drawn them onto a buffer (i.e. an off-DOM canvas element) and just move the buffer around as needed. Besides the main buffer, there also needs to be buffers dedicated to previously seen tiles (one per level). And as mentioned earlier, both of these need to be split up into rows.

Tile caching

There are only two hard things in Computer Science: cache invalidation and naming things. — Phil Karlton

Over the years, I’ve noticed that caching is used absolutely everywhere to make things fast. Unfortunately, caching can be complex and can cause all sorts of weird behavior. Computer thrashing? Web app not functioning properly? App icons missing? Maybe blame caching. It’s an interesting thought experiment: if computers and networks were infinitely fast, computer programs wouldn’t just be faster; they’d also be much simpler to write and more reliable.

So it goes without saying this solution was a bit painful.

cachecode

The motivation here is that rendering a tile requires several expensive draw operations, yet most tiles look alike. I save each fully drawn tile (again: a canvas element) to a plain old JavaScript object and I give it a key based on its properties. This works, but is indeed very tricky.

Scale the canvas instead of images drawn onto the canvas

Well, I sure do feel stupid about this one. Golden Krone Hotel uses small tiles, 16×16 pixels, which are typically scaled up 300%. The smart way to accomplish the scaling is to draw everything at 1X and then scale the canvas through CSS. The dumb way (what I did at first) is to scale while drawing to the canvas. This is actually much more complex. It resulted in some nasty bugs whenever the player resized the window because now I had all these improperly sized canvas elements sitting around.

Why did I do it the hard way to start? Well, for decades there has been no good way to tell browsers to use nearest neighbor scaling on pixel art; this is absolutely hilarious considering both how widespread pixel art games are and how dead simple the nearest neighbor algorithm actually is.

blurrednoble
2015 and this is still a problem

picard

So I used canvas property imageSmoothingEnabled = false to get crisp pixels on canvas draws. Now, I’ve decided to switch over to the CSS property image-rendering: pixelated. Of course, It still doesn’t work in all browsers and it only showed up in Chrome this year, but that’s good enough for me.

Fog

In the new version, I added neat looking fog of war, but it was quite slow. I tried to optimize by making fog buffers. I was ripping my hair out trying to figure out a way to update a buffer without redrawing the whole thing. Fog tiles overlapped, so for each piece of fog removed, I had to redraw all its neighbors.

fuckedfog
Fuck my life

I finally got it working, but then realized the buffers actually made things worse, since each buffer was the size of an entire level and the fog was animated as well. The buffers were so huge that they would make my entire app crash on startup. So I cut fog out entirely and I don’t miss it. Now I get these creepy vampire eyes instead.

creepyeyes

No rendering in steady state

When the player idles for a while, the only objects still animating are torches (at 10 frames per second). Someone suggested that rendering only at 10fps during those times would save on laptop battery life. It’s a great idea, so I did it.

WebGL

I’d seen some indications that using WebGL might improve performance. I decided to use PIXI.js to utilize WebGL. The cool thing about PIXI is it auto detects WebGL support and falls back to canvas rendering when not available. The requirement to run a local web server was a bit of a pain though. I’m no stranger to running local servers, but I really appreciate the simplicity of popping open an index.html file and having things just work.

I also spent several days freaking out over how PIXI and NW would interact before realizing it would work fine out of the box.

Lighting

Golden Krone Hotel has a performance issue that most roguelikes don’t have: dynamic lighting. Torches, spells, monsters, and rays of sunlight each produce their own light. Each light source can visit up to 400 tiles while distributing its influence. This occurs every turn and when the player rests, I have to simulate 50 turns at once. So in order to appear snappy, the game has to perform a few 100,000 tile visits/calculations in a split second. Achieving that seemed hopeless.

hunter

Failed solution #1: precalculate the influences of each light on each tile and then add them together. Sounds nice, but when you do the math it’s roughly the same number of calculations.

Failed solution #2: don’t simulate light sources that the player can’t see. Doesn’t really help because the player can see light from torches as far as 20 tiles away. If you have to calculate everything in a 20 tile radius, well, that’s nearly the whole map.

Failed solution #3: memoizing distance calculations. I thought 3 exponential calls would be slower than performing an array or object property lookup. I was wrong.

After many weeks of handwringing, the solution popped into my head: only calculate the differences between turns! I keep track of all current light sources, all previous ones, and the differences. If a light is missing from the previous list, I add its influence to tiles. If it’s missing from the current list, I subtract. I have to reset lighting whenever a door is opened, but beyond that it’s pretty simple code. I couldn’t believe how effective this change was. It took the average rest time from 1s to 100ms.

Wurf?

I made significant improvements in the performance of Golden Krone Hotel, but if I’m being honest here, some of the approaches just didn’t pan out. WebGL rendering and tile caching in particular resulted in little or no improvement. Tile caching appeared to be a winner early on, but that was before other changes superceded it.

Haitch-Tee-Em-El

One of my inspirations for shooting for a commercial release was Lost Decade Games, makers of A Wizard’s Lizard. These two guys have built a reputation on creating a surprisingly successful HTML5 game. They even have a regular podcast, which I would listen to every week. I’d smile and then cringe when I heard the cheesy opening which included a reference to the “arcane arts of HTML5.” One day I turned on the podcast and the opening which they had been using for 100+ episodes had changed. No mention of HTML5. They were switching to Unity because of performance reasons. Sad face.

Would I recommend HTML5 and NW.js for shipping games? If you already know JavaScript, sure, it’s a good option. But if it the game is at all complex, be ready to optimize.


If you enjoyed this post, why not check out Golden Krone Hotel on Steam Greenlight?

Conceits and Deceits in Her Story

If you’re the kind of person that has ever used the phrase “but it’s not a game,” you should stop reading immediately and go play a real game instead.

herstory

Her Story stands proudly in that “Not Game” category. The obvious comparison is Gone Home, but Her Story jumps right past the exploration of physical spaces into the exploration of mental ones. The premise: you’re watching short clips of police interviews following a murder. That’s all there is to do (besides mess around with the sublime 1990s fictional operating system). You can watch the clips in any order if you know what to search for. This might not sound gripping, but trust me: it is. Like the game’s detectives posing questions (which are never audible), you are tasked with posing questions of your own. But which ones? How do you know what to ask? That’s the puzzle.  With the game being about deception (including one necessary deception within the game’s marketing itself), this isn’t a straightforward task.

And oh yes. It does feel like a meticulously crafted puzzle. One that is ultimately meant to be understood. Like Primer. Or any Christopher Nolan film (and one in particular). The perfect accompaniments to Her Story: a pen, a notebook, and Google on the ready.

On the other hand, sometimes I feel I’m listening to a perfectly crafted album. There’s a lot of layers to peel away here and a boat load of symbolism (wielded a bit too carelessly… one of the game’s only flaws IMHO).

But what I really want to talk about is one particularly clever design choice.

I’m no games scholar, but I’ve thought a lot about how one implements a nonlinear story line in games. Let’s say you want to make such a story. You want to split up a story into a jigsaw puzzle and have the player piece it back together, right? But how much freedom do you give the player?

Imagine giving someone a novel where all the pages are randomly ordered. What happens when the first page they read is the last page of the novel? Or a huge twist? Or the climax? You not only run into an almost guaranteed anticlimax, but the reader also has to waste time on tedious setup for the climatic parts they’ve already read. Obviously, a naive approach isn’t going to work.

So you take the BioShock approach. You take pages  1-5 and put them in the first section of the game. Then 5-10 in the next section. We’ve seen this before and it’s not particularly interesting. What if you want to give the player totally unfettered access to the story and STILL feed them the twists and turns of the plot at a reasonable pace? Is that possible?

Yup and the solution is rather brilliant.

The answer is poor technology. Not the game itself of course, but the fictional, in-game technology. It’s much like the way that movies prevent communication between characters with poor telephone reception. The fictional video database in Her Story only lets you see clips that you explicitly search for and then only 5 clips at a time for any given query. At first this appears like an arbitrary limitation, but it’s absolutely crucial to the pacing. First, it prevents you from finding all the clips by searching a handful of common English words. But more importantly it allows the game’s designer, Sam Barlow, to order the content perfectly. To make sure that you have to ask the right questions to get the right answers. You still could find any clip you wanted by searching the right term. But you won’t know to search for the term (some of these clips are only a few words). So you get to navigate large parts of the story however you want, but there’s still a loose ordering that tends to prevent you from totally screwing yourself by watching all the most interesting stuff first.

I’m really amazed that a few small limitations can enable such an interesting story to be told, but there it is. More games should use such devices or invent their own.

I really want to talk more about this game, but doing so would involve massive spoilers. Play Her Story and let’s talk about it.

International Roguelike Developer’s Conference: Stone Soup

It’s been a few weeks since IRDC 2015 in Atlanta, the first IRDC in the states. The dust has settled, several youtube videos of talks finally got uploaded (part of the reason this is 3 weeks late), and I’ve collected my thoughts. Here they are.

Kawa did a write-up on IRDC 2015 and called it “one of the most amazing experiences” of her life. I concur.

Serious talk: the people at this conference were cool as hell. I’ve been to a lot of developer’s conference and it was by far the nerdiest (I say that proudly), yet friendliest ones I’ve been too. In my online experience, the roguelike community has often seemed…. curmudgeonly. However, everyone in the audience was extremely supportive. Maybe real life just has this effect on people?

Throughout the conference, we stoked a rivalry (tongue in cheek of course) between our conference and the European one. Todd Page set the mood with a hilarious talk (seriously, just watch this 2 minutes) explaining that Darren Grey beats him at everything, but maybe we could beat Darren at hosting a conference? One meaningless data point to support this campaign: we had the devs behind three of the top five 7DRLs this year, while it looks like the Nottingham version will have only two. I’m glad I could personally help shift the balance in AMURICA’s favor (with help from Canada of course). 🙂

On that note, despite being quite introverted, I did manage to get up in front and talk briefly about DUMUZID and my own small contribution to debasing the Berlin Interpretation. You see, there’s a little stipulation in there saying that “Monsters (and the player) take up one tile, regardless of size.” I argued that this restriction is pointless and unnecessary. Despite my incoherent babbling, it was rather fun.

Outclassed

I met A LOT of talented people:

Squirrel Eiserloh & Ken Harward, developers and professors at SMU Guildhall. They shared great stories about their game Square Logic, whose puzzles are procedurally generated and verified by AI (like Desert Golfing!) and which has the highest ratio of positive (174) to negative (1) reviews I recall seeing on Steam. I was blown away when Squirrel mentioned that he worked at Ion Storm and even got a mention in Masters of Doom. And then Ken told us he had once beat NetHack without spoilers.

 giphy
We are not worthy!

Jeff Lait. What can I say? He puts the rest of us to shame with how many amazing roguelikes he’s written. Jeff gave a lightning speed talk in which he did not apologize for the Berlin Interpretation, but did explain why balance is unimportant.

Jared Corduan. While the rest of the conference made me feel like quite the knuckle dragger (compared to everyone else), Jared momentarily made me feel clever. In his talk, he described several math puzzles. And I figured out the 2nd puzzle while he was giving the talk. Thanks Jared!

Sheridan Rathbun. Sheridan gave a very sincere talk about his experience developing Barony. There were several ups and downs in the story, but the happy ending was getting Barony greenlit. Well, Barony was just released on Steam today. Pretty cool to see that hapen after the conference!

Ascension

The conference got me fired up to play roguelikes of course! I played a little while there and within a week, I got my first 15 rune ascension in DCSS (despite playing for years).

Takeaways

The importance of handcrafted content in addition to straight up random/procedural generation. Jim Shepard had a lot to say on this including “text files are nature’s perfect fruit” (when arguing against making your own level editor). Darius Kazemi’s article/tool on Spelunky’s level generation got brought up at least TWICE (in very interesting talks by Cameron Kunzelman and Brett Gildersleeve). That piece never fails to impress.

Composition over inheritance. Yes, yes we’ve heard this before, but I for one needed a kick in the butt to actually do it. Brian Bucklew described how a very simple architecture allowed for the insanely complex behaviors in Caves of Qud.

Beneath Apple Manor – You may know that the first roguelike was actually released two years before Rogue. I had assumed that Beneath Apple Manor was way too simple to deserve any attention, but one M̻͙̭̦Y͖̖̪͎̪̹̞͝S͖̰̖̳͠T̷͍̝̤ER͈̲̗̤͟I̤̰̫̫͜O̝US͘ ̵̘̜̬ͅS̰͓̬̭̩̹͉ŢR҉̘̱̪͙Á̘̯̺͔ṆG̰̻̤E̞̮̳R̸͙͉͕͈͎̤ showed us that BAM was, in fact, very ahead of its time. Just take a peek at its gorgeous rulebook.

Pareidolia and friends. This concept got tossed around repeatedly. Pareidolia is the tendency for us to see patterns that may or may not exist (e.g. faces on Mars). One implication is that you don’t have to provide 100% of the detail behind your lore or mechanics because any gaps will naturally be filled in by the player themselves. If you’ve ever seen a Let’s Play of your game, you know exactly what I mean. If your combat system is not fully explained, players will derive their own superstitions about how it works out of thin air. Probably not good for a combat system, but good for creating the feeling of an expansive and lived-in world.

Symmetry. OK, this was some low hanging fruit, but I had not thought of it. Both Bob Saunders and Thom Roberston showed how 2 or 4 way symmetry (i.e. is generating something and then mirroring it) produces shockingly good results when trying to create spaceships and I imagine it applies well to buildings of all sorts.

Awesome, right? Well, IRDC Nottingham is this weekend. My advice is to go if you can (I wish I could). If you’re not a developer, no worries; I was happy to meet several roguelike enthusiasts in Atlanta.

Finally, let me explain the title of this blog post. The earliest speaker to be confirmed was Mark Johnson. Mark eventually had to cancel, but before he did, his name drew in a lot of interest and more speakers (it is Ultima Ratio Regum we’re talking about after all). Folks, that’s a stone soup if I ever heard one. 🙂

 

Howdy

Hi. I’m Jeremiah and this is the blog for Golden Krone Hotel, a roguelike about sunlight, stealth, and vampires. I plan to talk about Golden Krone Hotel specifically, but also roguelikes and game design in general.

Check out the trailer and if you like it, please vote for the game on Steam Greenlight.

If you have feedback, please feel free to email me or say hi on Twitter.