Jonas Rabbe's tumblr

It’s definitely possible to instantiate a module in a unit test. That said, your routes would be easier to test in an end-to-end setup, and you would get more value out of your unit tests if you focus on your individual units, i.e. your services/factories/providers, directives, filters, and controllers.

This weekend was the weekend of Ludum Dare. An online game jam where people from around the world create a game each in one weekend. The concept and background is explained quite well in the Ludum Dare Wikipedia entry so I won’t go into details here, except to say that the games have to try and follow a theme, and this time the theme was Minimalism. Since my wife and son are visiting family in Denmark, and I’m between jobs, I found that I suddenly had the time participate.

The thing I am the most proud of, coming out of this weekend, is that I finished my first game.

I chose to write it using HTML and JavaScript because of the accessibility it gave, and because those technologies will be part of my day job very soon. A game becomes much more accessible to people if they can play it in the web browser, rather than downloading, potentially installing, and running it on their machine.

Based on my technology choice I evaluated a few different game engines, and ended up choosing Crafty. While I did run into some problems with the engine, a few minor bugs that I hope I have a chance to tackle, and some documentation ambiguities, it still feels like it was a good choice. I did find a couple of articles comparing JavaScript game engines later, which I wish I had time to read before, but settling on tech and engine was a definite boon. It would have been nice if I had experience with the engine before, but since I didn’t have experience with any engine, that would have been hard.

I very quickly decided on a basic gameplay and art style, although I diverged a little bit from it when I started getting pressed for time. The basics still revolve around a blue ghost as the protagonist, red demons as the enemies, green ectoplasm for “ammunition, as well as black and blue elements representing walls and water. I wish I had time to design some proper wall and water tiles, but I didn’t even have time to use my thing or the Hell Hole itself. The thing was this orb you could pick up, and had to put into the hell hole to close it, and the hell hole would (obviously) spawn demons.

Before I start getting into the stuff I learned from this experience, you can open a new window and play the game in your browser, I’m not going anywhere.

Hell Hole -- Ludum Dare entry for the theme Minimalism

Now that you’ve tried it I’m sure there’s a number of things that have become apparent. First of all, this game is insanely hard (unless you found the same speed cheat1 a friend did within 10 minutes2). And sometimes, you can only move a short distance to the right before the viewport stops and you kinda step off the world. You can still die when outside the viewport, but you cannot see the little ghost or the demons

Secondly, if you made it that far, the goal is to kill all the demons and then you win. Easy right? What was that? You killed all the demons, and still didn’t win? That’s right, I forgot to put a screen in that told you when you won. Instead you are stuck in an empty world and the only thing you can do is to refresh your browser window.

Both of these boil down to the biggest problem I ran into: the time pressure. When you have to create a game in 48 hours, you really have to focus on the core and forget all the fluff. Which is definitely my biggest takeaway from this weekend.

Things that are done on purpose is that you can walk through walls, but you cannot cross water (basic ghostology). Similarly to the problems above, I wanted the demons to not pass through walls, but be able to cross water. This would give a different mechanic for hunting the demons.

I got caught off guard by a few things. First off, I thought the theme was announced (and the competition started) at midnight Friday. Turns out it started at 7 pm PDT. So I lost a few hours there. Not a biggy though. I spend the rest of the evening brainstorming ideas before going to bed, to be fully rested to start making my game Saturday.

When I got up Saturday I brainstormed look and feel, I sketched art, I researched story. I wanted something that people could play and go “wow, that’s a cool story.” Unfortunately, doing that meant that the mechanics never got the polish I felt they needed, and never got around to using my nice art or my elaborate story.

In the end Saturday was mostly spent doing sketches, some simple sprites (that didn’t get used either), story, and some very simple gameplay using this introduction to Crafty tutorial. The feeling when I woke up Sunday morning and realized I had basically nothing with 7 hours to go, is perfectly encapsulated in this tweet:

7 hours to go is when you start saying things like "who needs walk cycles." #LD48

— Jonas Rabbe (@somebear)

April 28, 2013

This was when I decided to fall back to 16 × 16 pixel sprites (rather than the 40 × 40 pixel beauties I had envisioned) blown up 4 times to give a retro look. Almost all animations went out the door, and only simple animations when you kill a demon or when you die stayed in.

One of the things that became abundantly clear, was that the time I spent on story was wasted. While I think story is definitely great in a game, the entries that do well in Ludum Dare and other game jams are those that choose one core mechanic and polish it to an incredible shine. Zen fighter is an example of such a game, its mechanic is in its controls and they work incredibly well. Since I became so pressed for time, I also didn’t have the opportunity to use the story at all, and the time spent on developing it could have been better spent polishing the mechanics.

For the competition Hell Hole uses a simple rectangular grid based game world with auto-generated content. The demons start following you if they come within 250 pixels of you, which means that sometimes you spawn, and a demon spawns right next to you (i.e. you’re dead). When you die the whole world is regenerated, so you start from scratch. Because everything is autogenerated semi-randomly, so you also run the risk of starting completely boxed in with nowhere to move.

Version 1.1

After the end of Ludum Dare I fixed a few things. I added a win condition (which is allowed within the rules), and added some instructions. I also fixed the viewport following bug by using Austin Hanson’s bmViewport which makes for a much more enjoyable gameplay. This version is also available online:

Hell Hole -- version 1.1

Things I wanted to get around to

Because of my time mismanagement, there were so many things I didn’t get around to. As I’ve already mentioned I wish I had time to use my story, but for the next LD48 I participate in, I’m definitely going to ditch story and make a game with a very simple mechanic that is polished to feel great.

The AI for the demons is a simple sight based model. If you get within a distance of 250 pixels (roughly half the viewport) of a demon, it starts following you. This means that you can see demons at the edge of the viewport before they start following you, so you can run away. I wanted for the demons to do some kind of random walk. I also wanted the demons to not pass through walls, but to be able to cross water, and I wanted them to not be able to see through walls.

Finally, I wanted to have the Hell Hole which spawned demons, and you would be absolved once you use the thing to close the hell hole and kill any remaining demons.

I’m sure I’ll get around to fixing some of these things, but enjoy what’s there, it’s my first game.

Getting the source

The source code can obviously be downloaded from the pages above, but the whole project is open source, and can be fetched from the Hell Hole Repository.

The game uses WASD and the arrow keys for controls, and if you press both W and the left arrow key, then you go at double speed (for now). ↩︎

The October Challenge from Ludum Dare is quite interesting. The point is to develop a game, take it to market, and start earning money on it (i.e. earn at least $1), all through the month of October.

Really interesting slide deck from NVIDIA about the lessons Valve learned from porting their games to Linux, and in turn from Direct 3D to OpenGL.

I recently talked to a guy about compilers and assemblers. I wanted to refer him to a blog post or some articles that explained compilers in a bit more details than Wikipedia without becoming scientific article level goodness. I'm not sure I've struck that balance yet, but here is my first attempt at explaining compilers. I'll dive into some of the subjects that make up compiler construction in later blog posts.

As the compiler Wikipedia page very succinctly remarks, "A compiler is a computer program […] that transforms source code written in a programming language (the source language) into another computer language (the target language…)." In order to do this tranformation the compiler goes through a number of steps. Note that different types of compilers may have different names. For instance a compiler that transforms a program in assembly language into machine code is commonly referred to as an assembler, and a compiler that translates a program in a language specific to one CPU architecture into a language specific to another is called a cross-compiler.

The parts of a compiler is most commonly referred to as the following the following:

Front End

Parsing

Syntax Checking

Type Checking

Error Reporting

Generating an intermediate representation

Middle End

Code Optimization (most commonly using program analysis techniques)

Back End

Preparation for code generation (for instance register allocations, machine architecture specific parallelizations, etc.)

The first thing a compiler does is to read the source program, and parse from the source language into a data structure that it can work on, usually some sort of parse tree. Like everything about compilers, the whole subject on parsers is incredibly deep and the subject of whole research careers. While I do enjoy technologies like Parser Combinators, most cases can use solutions like Lex & Yacc (or Flex & Bison) or even a simple tokenizer with simple logic to create a parse tree.

After the parser has generated the parse tree, it is traversed to check for correctness (usually the source of all those wonderful compiler errors we keep running into). Other information may also be extracted, like type information and data usage (depending on the language this may be content in the .data section of an assembly language program, or variables, and so on)

The output of the front end is the first intermediate representation which is a representation of the program that was given as input, in a way that can be worked on in the middle end and/or back end of the compiler. I'm planning to talk in more detail about program analysis in a later post, and there are some details about the intermediate representation that will be influenced by that, but for now let's just consider it as a tree containing the source program in a form that can be traversed to read information about the source program. This means that we skip the middle end until further notice.

The last part is back end that performs the code generation. This is where the program is written in the target language. It is "simply" a matter of writing the instructions from the sources languages as they translate into the target language. Most times that involves having a look-up table that contains this mapping. For something like compiling assembly language into object code, in order to create an executable, the look-up table would map instructions into their corresponding opcodes. In other cases the instructions in the source language may map to multiple instructions or operations in the target language. During this step the compiler also does other tasks needed to generate correct output code which may include register allocation, variable mapping, and generating debug data.

Even stormtroopers sometimes have to dress up, doesn't mean they have to like it.

Update: one of my friends linked to this presentation from NVIDIA (pdf) which specifically states: "Do not create a single FBO and then swap out attachments on it."

At the time I was implementing this I didn't know, and it was the most obvious approach within the architecture of the renderer we were using. Using separate FBOs to store the rendered output for each frame seems like a more reasonable approach with this warning in mind. Apart from that the synchronization guards below still make sense.

I know I know, you must all think I'm crazy, but bear with me while I try to explain.

Imagine a situation where you have a renderer. This renderer renders a scene (with animation and so on) in real-time. For the purposes of this exercise, real-time means 24 or 30 frames per second. The UI has to be responsive and "fluid", which means it should be able to update around 60 frames per second. I'm sure you can already see a problem here.

This could be a non-issue if you could decouple the UI completely from OpenGL. When you are trying to use a framework where drawing OpenGL content into a window means the whole window must be drawn with OpenGL, then you don't really have much choice.

So with the scene set let us dig into the problem. We obviously have to use threading, because our UI and renderer must be able to update more-or-less independently. Fortunately, that is possible with OpenGL, although the driver and GPU usually only has one command queue, so you have to ensure that you synchronize the OpenGL commands to prevent race conditions.

We are in the fortunate situation that the end result from the renderer is a texture attached to a frame buffer (let's call it the output frame buffer). This texture can simply be bound in the UI thread and drawn on a fullscreen quad symbolizing our viewport.

To allow the renderer to render somewhat independently of the UI thread, we must have multiple attachments to the output frame buffer, so the renderer can render to one while the UI is painting the texture from the other to screen, and so on.

This means the problem is more or less a producer-consumer problem. Some requirements on the application mean changes from the classic problem. We have pre-allocated elements in the queue that are filled in by the renderer. If there are multiple elements rendered and none left to render into, it may take the oldest and overwrite its contents, as long as the newest render is always available to the UI, and the renderer doesn't re-render the element it just rendered (e.g. because the UI wasn't done painting it when the renderer was done).

To solve this I created an AttachmentQueue. This queue holds elements representing the pre-allocated attachments on the output frame buffer. Each element has an internal unique ID, a name1, a time changed, a synchronization object, and a status.

The synchronization object is used because the number of commands the renderer pushes to the GPU is huge, and we need to make sure that the GPU has actually drawn to the attachment we want to paint in the UI before the UI command to bind the texture is put onto the command queue. This is the race condition I mentioned above. The status simply says whether the attachment has been rendered to yet.

In addition to a list of elements, the queue also has a mutex to ensure only one thread at the time makes modifications to it. It has a reference to the element representing the attachment current held by the UI and renderer. And also a wait condition and a reference to the last rendered attachment which are explained in further detail below. The references to attachment elements are all initialized to the empty element (EMPTY).

There is a pair of functions, reserveAttachment() and releaseAttachment(), for both the UI and renderer. The main difference is that the UI, in the case where it can't reserve an attachment will simply not get one, and will instead paint some alternative UI to show it could not get the texture. In contrast, the renderer needs an attachment to be able to render and will have to wait if there is no attachment available.

The queue should always have the newest rendered attachment at the front which the UI will grab, and the renderer will take from the back.

These requirements leave us with a reserve and release function for the UI (in my best C++ pseudo-code).

void reserveUIAttachment() { AttachmentWriteLock lock (_mutex); if (_queue.empty() || !_queue.first().isRendered) return; _uiAttachment = _queue.first(); _queue.pop_first(); if (_uiAttachment.sync) { glWaitSync (_uiAttachment.sync, 0, GL_TIMEOUT_IGNORED); _uiAttachment.sync = 0; } }

Pretty straight forward stuff. The only thing to note is the use of an OpenGL sync object, if it exist for this attachment we have to put a wait onto the command queue.

The release is not too complicated either, except we have to cover the case where the attachment at the front of the queue is older than the current attachment, in that case we have to add it back to the front. We also notify the wait condition. This means the renderer will be released if it's waiting, and does nothing if the renderer is not waiting.

void releaseUIAttachment() { AttachmentWriteLock lock (_mutex); if (_uiAttachment == EMPTY) return; if (_queue.empty() || _queue.first().timeChanged < _uiAttachment.timeChanged) _queue.push_front (_uiAttachment); else _queue.push_back (_uiAttachment); _uiAttachment = EMPTY; _waitCondition.notify_one(); }

The render side is very similar, but with a few crucial differences. We do not overwrite the last attachment we rendered to, and will wait if we can't get an attachment (rather than returning immediately like the UI reservation does).

void reserveRenderAttachment() { AttachmentWriteLock lock (_mutex); if (_queue.empty() || _queue.last() = _lastRenderedAttachment) _waitCondition.wait (_mutex); _renderAttachment = _queue.last(); _queue.pop_last(); _lastRenderedAttachment = EMPTY; }

For releasing the rendered attachment, we have to remember to push a sync object.

void releaseRenderAttachment() { AttachmentWriteLock lock (_mutex); _renderAttachment.sync = glFenceSync ( GL_SYNC_GPU_COMMANDS_COMPLETE, 0); glFlush(); _queue.push_front (_renderAttachment); _lastRenderedAttachment = _renderAttachment; _renderAttachment = EMPTY; }

Note that we have a call to glFlush() right after creating the fence, and before we release the mutex for the queue. This means the fence will be pushed to the GPU before the wait is put on the queue in reserveUIAttachment().

And that's basically all there is to it… Well, not really. You also have to use the attachments.

If you remember above, I said we store a name for the attachment. This is set up under initialization to ensure that we set up the right number of attachments. When we want to render to an attachment in the output frame buffer, then we ask what base name the render pass wants to write to. If it matches the base name of the attachments in the output frame buffer, then we map it to the name for the _renderAttachment from the AttachmentQueue. The call to glDrawBuffers (…) then has the correct buffer.

Similarly, when we want to get the texture ID from the UI for the attachment we have received, then the frame buffer finds the attachment with the name from _uiAttachment and returns the corresponding texture ID that can be bound with glBindTexture (…).

Now you know about as much as me on the topic of multi-threaded rendering. You can always ask. As an experiment I have also turned on replies to this post, so we'll see how that goes.

I have always enjoyed mac & cheese, so when I saw the Modernist version in Modernist Cuisine at Home, I knew I had to make it.

This weekend I jetted all around the Richmond area trying to find sodium citrate, which is used to prevent the cheese from separating when you melt into one of the most velvety cheesy sauces you have ever experienced. Unfortunately, it was all for naught. Of all the 6 places I visited, none had sodium citrate, or even citric acid which I wanted for another dish.

In the end, I improvised. I used an immersion blender to mix 0.3% xanthan gum into the milk (by weight) before heating it and blending in the cheese. It held together beautifully, and the flavor was excellent. The only downside was that the texture was a teeny bit gritty.