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.