The Quixotic Engineer

SpaceChem is a remarkable puzzle game about fake chemistry. The game challenges you to build a factory in order to transmute the given input molecules into the given output molecules. While chemistry is the theme, on a mechanical level it has more in common with programming. The methods used to tackle challenges in SpaceChem are akin to real techniques used by computer programmers. I’d like to elaborate on these manifold similarities, as well as explore how games like SpaceChem could be used to promote procedural literacy.

The player commands two circular “waldoes” by laying out paths and instructions for them. The waldoes follow the path and sequentially execute any instruction they come across. They can grab, drop, rotate, sync, bond, fuse, request input or dispatch output. The waldo’s analogue in computing is the processor, a hardware component that sequentially executes basic operations defined by machine code. Like processors, waldoes are the engines that drive the control flow of a SpaceChem factory.

When a waldo grabs a molecule, it gains the ability to perform instructions directly on it. In other words, a grabbed element is more readily and rapidly available than one lying elsewhere on the grid. Conceptually this is analogous to storing data in registers, a form of computer memory that is accessed very quickly and that the CPU manipulates directly. Just as a waldo can only grab one molecule at a time, computers have very few registers and must therefore rely on caching.

If grabbed molecules are like data in registers, then molecules left on the grid are cached. The cache is a larger, cheaper form of memory, but it is slower to read and write. Data must be written from the cache to a register in order to be manipulated directly by the CPU. The amount of memory in SpaceChem’s “cache” is governed by the area of the grid (8 x 10). Each coordinate on the grid can therefore be considered a unique memory address. This analogy is enforced mechanically: a factory “crashes” if two atoms collide on the grid, since you can’t store two values in the same memory address.

Each factory has two waldoes, and they must be properly coordinated as they move through time and space. This coordination is facilitated by the sync node, which tells a waldo to wait until its twin has also hit a sync node. Parallel waldo management is akin to parallel programming, and they share the same perils: deadlock, starvation, race conditions, etc. The waldoes are like threads operating on shared memory space, and sync nodes are functionally similar to semaphores (operations that tell threads to signal and wait.) Operating two waldoes simultaneously in SpaceChem forces the player to confront the same shared resource problems as parallel computing.

SpaceChem and programming involve similar challenges: laying out simple instructions to achieve a complex result while managing limited time and resources. Like a good software specification, each puzzle is clearly presented as a black box defined only by its inputs and outputs. The player lays out instructions, starts up the factory, observes errors and corrects them, iterating until the puzzle is solved. Solutions can then be further optimized to take less time and use fewer instructions. SpaceChem and programming are engaging, flow-inducing activities because they have an identical inner loop: implementing, debugging and optimizing.

At this year’s GDC, Michael John asserted that programming is 21^st century literacy. If computer programming is currently considered esoteric knowledge, it’s because our general education is not preparing students to think about problems in an algorithmic or systematic manner. Ian Bogost calls this procedural literacy: “the ability to reconfigure basic concepts and rules to understand and solve problems.” SpaceChem may not be an ideal game for the classroom (it’s far too difficult, for one), but it strongly suggests that the best way to learn about and engage with complex systems it to play with them.

Back in January, Henk, Thomas and I presented two games we were working on (Norwegian Wood and an alpha build of Pax Britannica) to the DemoCamp at CUSEC 2010. DemoCamp is a really cool informal event where programmers can show off what they’ve been hacking on. The rules are simple: 15 minutes maximum, no powerpoint, show working code!

I think the talk went really well, we got by with some laughs and a little bit of casual swearing. Big thanks to the CUSEC organizers, host Joey DeVilla and A/V tech Guillaume Theoret for giving us a chance to show off our games!

The project that became Norwegian Wood began in late April of this year. With school winding down and the weather heating up, I felt the itch to tackle something new. By chance I had met a number of like-minded people over the winter; students with big ideas and aspirations of working in the game industry. Inspired by this collective potential, I decided to reach out to my local friends and colleagues about coming together to make a game over the summer.

The response was overwhelming; of the nine people I had e-mailed, seven of them were interested in participating. The project was suddenly much larger than I had anticipated, but I didn’t have the heart to turn anyone away. The eight of us (Henk Boom, Thomas Hibbert, Phil Jones, Renaud Bédard, Alex Charlton, William Mitchell, Kyle Sama and I¹) formed the facetiously titled collective No Fun Games.

You might be surprised to learn that our original game idea had nothing to do with music, shoot ‘em ups or The Beatles. While we explored a number of different game ideas, we settled on creating a murder mystery game set in an JRPG-style lumber town. We gave the development version the nickname Pulp².

Pulp‘s main character was “Penny”, a local girl with a knack for mysteries. She teamed up with retired Sherlock Holmes analogue “Detective Powell” to solve the murder of his former partner “Dr. Watson” (we never really settled on official names). You can see Phil’s concept art for some of the characters above.

We developed an elaborate back story which outlined the motivation behind the murder and its connection to the protagonists. However, our ideas for the game’s actual plot and structure were little more than a skeleton. Truthfully, we possessed neither the inclination nor the talent to write good fiction and this was ultimately the game’s downfall.

On the programming side, we put together a basic game engine in Python with the help of the Pygame and PyOpenGL libraries. It gave us the bare essentials, allowing us to add actors to the screen and assign them behaviours. As seen above, we created a simple world for Penny to run around and interact with (the Fez spritesheet was placeholder art lent to us by Renaud).

Sadly, this is as far as the Pulp project ever got. Despite our best intentions, we drifted apart over the summer. Everyone had personal commitments, internships, and travel plans. We simply didn’t have the time or motivation for leisure coding. By July, Pulp had reluctantly become vapourware. Fortunately, this wasn’t the end of No Fun Games.

By late August, things in my life were starting to slow down. I was back living in Montreal (after spending the summer at IBM in Ottawa), and had a couple of weeks off before the fall semester. Blessed with free time, I decided to reconnect with my teammates for a final sprint. Naturally, we wanted to release something after all our hard work.

Of course, not everyone had the luxury of time off. While we all wanted to participate, only Henk, Thomas and I had the hours to spare. Our artist Phil was also interested, but couldn’t commit to the heavy art demands of the murder mystery concept. With this in mind, we decided to drop that idea and reuse the engine we had created to pursue an entirely different genre.

The concept for Norwegian Wood came from our desire to explore the burgeoning intersection of music and gameplay. We wanted to create a game where listening and following the rhythm played a strong role in the player’s experience, but less directly than a game like Rock Band.

This idea manifested as a shoot ‘em up game where the bullet patterns are timed to the individual instruments. The decision to use The Beatles’ music was somewhat incidental; I happened to be listening to Rubber Soul when the game concept occurred to me. However, the song has certain qualities that make it rather ideal. For instance, the notes are quite discrete, making it easy to divide the instruments and record timestamps. More importantly, using a calm lilting ballad with subtle dark undertones contrasted nicely with the upbeat synth-metal used in most shoot ‘em up games.

Henk, Thomas and I got together at school to work on the game, working nearly full time for two weeks. We managed to create a playable prototype within a few days, then put the majority of our work into refining and iterating on the core gameplay. We also placed a strong emphasis on player feedback, bugging everyone around us to playtest it.

After chasing down the cross-platform bugs and ironing out the details of deployment, we finally released Norwegian Wood in late September. Thanks in large part to friends on Twitter spreading the word, we’ve had thousands of hits, hundreds of high scores and some very positive feedback. We’re thrilled that so many people have enjoyed our game, and promise to put all that excitement right back into making more of them.

To summarize Gamasutra-style, here are some lessons we learned during development:

What Went Right

1. Working Together Locally
While most of the work on Pulp had been completed remotely, it came at a cost to communication and motivation. For Norwegian Wood we decided that there is really no substitute for face-to-face time and met up in person every day. This was extremely effective, both for making consistent measurable progress and sharing a common creative vision.

2. Recording Global High Scores
The online high score table was a minor last-minute addition to the game. However, as Eric Swain pointed out in his insightful Indie Spotlight, it added a ton of value in terms of competition and replayability. “Even after all these years and innovations it is still a huge motivation to play. [...] It isn’t all about competition, but the close knit community that get formed in that competition.”

3. Sidestepping Copyright
It took a lot of thinking to come up with a way to release a music game without infringing on The Beatles’ copyright³. Despite our doubts, having the user provide their own mp3 turned out to be a very successful strategy. Of course, it’s a shame that we picked the one band whose music can’t be downloaded legally. In the future, we’d very much like to reexplore this concept with Creative Commons licensed music.

What Went Wrong

1. Big Team Woes
Starting out with such a large development team on Pulp was a major challenge. Responsibility was spread too thin, and no one felt like they had creative control of the game on an individual level. In retrospect, I would recommend a team of no more than 4 for your first indie collaboration. Furthermore, it helps to have a fairly autocratic team leader.

2. Summertime Blues
I had assumed that summer would be the perfect time for students to pursue a side project. Working nine to five at an internship means having evenings off and lots of free time, right? Sadly, I was way off. The temperament of summer is lazy and leisurely; it’s hardly a season for picking up additional work. Furthermore, working full-time turns casual hacking into an unpleasant chore. Counter-intuitively, students would much rather attempt side projects while they’re juggling exams and assignments in the fall.

3. Storytelling Failure
We were incredibly naive about the process of writing a story for Pulp. We had the big picture ideas and the game mechanics, and just assumed that the moment-to-moment narrative experience would flow from that. We quickly discovered that writing a good story is an extremely demanding task, one we were ill-equipped to handle. Lesson learned: if you insist on having a narrative element to your game, make sure you have a dedicated writer (or semionaut) on the team.

Thanks again to everyone who was involved in Norwegian Wood, including those of you who playtested it and helped spread the word on release day. Making this game was a terrific experience, and it taught me a great deal about game design, programming and project management. I look forward to applying these lessons to my next game!

¹ Ben Abraham was also briefly involved as music director, he wrote us a lovely dirge for Pulp.
² Funny how Pulp turned into Norwegian Wood. The arboreal theme is coincidental.
³ Actually, Nick suggested this approach. Thanks Nick!

I was originally introduced to Markov chains by Josh Millard’s Garkov, a project that applies this mathematical model to Garfield comics. I thought it was an amusingly random idea, but didn’t fully appreciate the concept until Jeff Atwood wrote a post detailing how Markov Chains work.

To quickly summarize, the algorithm chooses its next word using a probabilistic function based on two criteria: the current word, and a large sample of coherent text. The chance of a word being chosen is based entirely on how frequently it follows the current word in the sample text. For instance, if the sample was “To be, or not to be, that is the Question”, the word “be” would have a 50/50 chance of being followed by “or” or “that.” As the sample size increases, the text produced becomes increasingly sound. [Update: The size of the sample does not necessarily increase the coherency of the text, the number of words used in the seed is the biggest determining factor. Thanks for the correction, Josh.]

Reading about this got me very curious. What would a Markov chain generated using my own writing look like? Would it overuse “however” and frequently misapply the word “parse” like I do? I decided some experimentation using the Markov Text Synthesizer was in order.

The first test sample was my Rockin’ The Boat series on rock ‘n’ roll and race relations in 1950′s America. At a scant ~4000 words it was a poor sample, which made it quite possible to recognize parts of the original sample in the text:

Rock ‘n’ roll party. Freed considered completely alien. Mintz had his personal success, but rather the Speeds had been a little pressed for school facilities. They were subject to unsuccessful alternative names such as much for the trend was classified under the Brown v. Board of, in ten in, most popular opinion in the same records was no memory of the major label was a lesson. He was a token job. The major record store owner in postwar economy. During the following lyrics which were localized in America. A successful rhythm and I feel would sing to popular.

For my next attempt, I used every post listed under the Video Games category. This was over ten times larger than my original sample, and the text was much more randomized as a result (it even snuck in a “however”, hooray!):

There are games have two things spectacularly well. One where it will work at first. They mix means of Internet hype around the U.S. Addresses Only. Heartbroken, I was, however, describe what is one of the censor, the creative Wiimote according to the end. Plot holes and Escapist feature. Embedded below is minutes of military shooters had her to convince you feel that the game will work done with blood all available up the narrative. He created the Medic class impressions. The use of his weekly feature film was already breaking my favourite newspaper articles. Read the end. The very effective ways. My favorite aspect of a short stories, particularly dystopian centuries. At first game Rock Band, but the best like a timeless void movie revolved largely passed under them all.

Next, I decided to use the same sample but increase the “word grouping” to two. This means that the function will now determine how frequently a word follows the two previous words (in order.) This made the text much more coherent, but brought back the problem of being similar to the original sample:

There have been used by other games in the villa’s lobby. Recharging your beam sword’s energy with a Little Sister crying for “Mr. Bubbles”, but it costs a whopping. December is a classic for years to come. Valve could have easily rested on their laurels and sold Portal on its PS release Tools of Destruction, with some great part series detailing each other, it seems that the FPS genre has been getting a lot of the murder investigation. The evidence found and is by far the best thing the Bioshock movie revolved largely around and go buckwild with ADAM. I would rescue them all. It was also annoying at times. To move Zack around you have to mimic it in real life.

Finally, I decided to test the program with a very very large sample: Cory Doctorow’s free e-book Little Brother. I don’t think this is the sort of remixing Doctorow had in mind when he released his book under Creative Commons, but here goes:

I’m a stone Disney park freak see my fear. Marcus, it can fill you with our magic coffee bean supply. If you’ve got it for a lot longer than me. One only spoke Arabic he began, when one of the country, the world to know it’s there. The truck drew closer. I kept hitting it with both hands. She was dressed in a drawer with the texture of very ugly stuff on the back of a polished marble plinth. I decided I wanted to do stand down. Will you promise me that? They promised with all the walls and other little devices, my wallet intact. Forbidden Planet rarely do I go to jail, Marcus, and not that many cool puzzles that you wanted to be a part of that Hummer, my head for my book by net or phone and memory sticks are private. Thats because of cryptography message scrambling. The math behind crypto is good and solid, and you wonder, Was it always like that? I hadn’t thought about trying to intimidate me the picture she’d snapped of us, if you wanted to.

I’m amazed, a very large sample with a word grouping of two or greater can produce some terrific results. It makes me wonder why spammers always end up with such nonsense titles, use a larger sample you jerks!

In my various attempts, I also ended up with some rather spectacular phrases. Here are some of my favourites, I swear I did not make any of these up:

The whimsical charms of each of disappointed children

Holding the Wiimote in the holiday rush? Either way, you’re probably online looking for awesome news like this

Your character’s level is on a couch. They’re comfortable for both sides.

a combination of raw stem cells, dubbed thing, and the USA

I believe I was blindsided by exploiting my childhood memories

…and the best one by far:

This essay will be successfully ignored altogether.

Check out Ben Abraham’s post for some more great ones (he beat me to the punch by a few hours.) Finally, I’ll leave you with a challenge. Can you guess what sample I used to produce the text below?

Peyote solidities of halls, backyard green tree cemetery dawns, wine drunkenness over the rooftops, storefront boroughs of teahead joyride neon blinking traffic light, sun and moon and tree vibrations in the roaring winter dusks of Brook-lyn, ashcan rantings and kind king light of mind, who chained themselves to subways for the endless ride from Battery to holy Bronx on benzedrine until the noise of wheels and children brought them down shuddering mouth-wracked and battered bleak of brain all drained of brilliance in the drear light of Zoo,

***********ANSWER***********

Trick question, it’s actually a word-for-word excerpt from Allen Ginsberg’s Howl. Only the formatting has been edited. I think the beat poets would have dug Markov chains, don’t you?

For a long time, one of my secret shames as a programmer was that there were parts of this website held together by some rather shoddy code. Writing this blog has been a great learning experience, but as a consequence I’ve often accidentally done things the “not quite right” way. Armed now with a better understanding of XHTML and CSS, I thought it might be a good idea to fix some of that spaghetti code and bring my blog up to at least XHTML 1.0 Transitional.

As a long overdue followup to my previous experimentation with Python, I decided to kill two birds with one stone by writing a script to clean up some common errors in my posts. Blame it on my sloppy HTML education, but I make these mistakes all the time. For instance:

• Using <i> instead of <em>
• Using <b> instead of <strong>
• Not closing my IMG and BR tags
• Forgetting to give my images “alt” text

Furthermore, due mostly to my Musical Box series, I’ve embedded a rather large number of YouTube videos in my posts. For some crazy reason, the default code uses the deprecated <embed> tag and is therefore not XHTML 1.0 compliant! The mind-blowing part is that it’s relatively simple to embed videos in an XHTML friendly way. Why isn’t this code available by default?

Armed with my copy of Dive Into Python and basic experience with regular expressions from Perl, I went about writing a script to parse my blog posts and fix the sloppy HTML. Since trying to embed Python code in a blog post would be inelegant at best, I present the script in three different formats (including some neat JavaScript syntax highlighting):

• Python Script File (.py)
• Syntax-highlighted HTML (Light)
• Syntax-highlighted HTML (Dark)

I’m not sure that my code is especially pythonic; sadly I have too many bad habits from Perl and Java. While I’m told that Python is frequently used as a scripting language, I get the impression that its real strength lies in larger applications. Furthermore, using regular expressions to parse HTML is a suboptimal solution, in retrospect I should have used an XML parser module. Any constructive criticism of my code is more than welcome, I’m here to learn.

Code qualms aside, I can now proudly say that The Quixotic Engineer is written in valid XHTML 1.0 Transitional (the front page at least, I’m still working on some of the archive posts.) Coming up next: XHTML 1.0 Strict, and perhaps some CSS experimentation to spruce the place up a bit.