Building Blockhouse

BlockhouseLevelsBy the time I decided that I was going to implement Blockhouse as a commercial iPhone app, the game design was already done. Tilt or swipe in one of the four cardinal directions to cause all blocks to slide as far as they can, and try to put them on their respective targets. What could be easier? Many aspects of the aesthetic design and the user-interface were still up in the air, but I had an inkling of where I was headed: chicklet-style blocks and walls, bright candy colors, minimalist interface. Implementing this stuff wasn’t going to be particularly difficult.

I knew that the hard part was going to be actually designing 100 unique puzzles. The only way I could think of to do this was to create some kind of puzzle-building tool that would allow me evolve, tinker, and tweak these puzzles into shape. As it turns out, I spent about six weeks on this task before I even wrote a line of iPhone code. The result was a rather clunky but serviceable OS X app called BlockhouseBuilder.

This was the first time I’d ever implemented a Mac app. Indeed, I’d only been using a Mac since about May of 2008, which is when I’d jumped into iPhone development with both feet. I knew there was going to be a bit of a learning curve. My goal was to make a fully-functioning document-based app, which would allow me to edit puzzles in groups of 100, save them, cut and paste them, undo and redo all editing actions, etc.

None of that was easy, but nevertheless I managed to cobble together an editor that allowed me to create and edit the layout of walls and blocks within a puzzle. It also allowed me to choose the grid-size of each puzzle, and I wrangled for a while about what range of sizes I should allow. Eventually I decided on an aspect ratio of 3:4 for all puzzles. This fit the screen of the iPhone well, leaving some room at the top for UI buttons. It also allowed for a nice range of puzzle sizes: 3×4, 6×8, 9×12, 12×16, and so on.

The really hard part was coming up with some way of displaying the abstract structure of the puzzles I was creating. I wanted to actually see the “puzzle-graph”—a visual representation of every possible position that the blocks could get into, along with the connections between them.

This turned out to be a tough nut for me to crack. There are algorithms for displaying arbitrary graphs, but they aren’t simple, and they often result in winding connections and crossed lines. I wanted all of the orthogonal relationships between states to be retained—in other words, if you can get to one puzzle state by swiping to the right, I wanted that state to appear directly to the right in the puzzle graph. I suspected that someone had already solved this graphing problem—if not for tilt-mazes, then for something isomorphic to them—but I didn’t know enough about graph theory to know where to look, or even to know for sure that what I wanted to do was possible in all cases.

I tried a number of different methods—even some evolutionary ones—but none of them quite did the trick. After working on the problem full-time for almost a week, I started to panic. What if the solution was simply beyond me? I couldn’t afford to keep pouring 8-hour days into it, and yet I couldn’t see how to do what I needed to do without it.

Fortunately, an new idea occurred to me involving a mix of two different techniques I’d tried earlier. I tried arranging all the puzzle positions along horizontal and vertical “struts” or “dowels”, like the beads of an abacus. Each strut contained all the puzzle positions that were connected to each other horizontally or vertically. Each puzzle position was connected to exactly one horizontal strut and one vertical strut. This created a large connected mesh of all the puzzle positions. This mesh was often too compact, overlapping itself at many points, but I could fix that by iteratively pushing the struts away from each other until no two horizontal or vertical struts lay on the same line. The result was a fast algorithm that displayed a flattened, 2D representation of the entire layout of a puzzle, with all orthogonal connections intact. Success!

Here’s a screenshot of BlockhouseBuilder in action, displaying puzzle #16 from the release version of Blockhouse.

BlockhouseBuilder

The lower left portion of the window displays tiny images of all 100 puzzles and allows me to move between them, change their order, or cut-and-paste entire puzzles from one slot to another. The upper left portion of the window displays a close up of the selected puzzle, which allows me to add and remove blocks and walls, and change their colors. The main window displays the graph of all possible positions that this puzzle can get into, including the starting position (outlined in blue), the ending position (outlined in yellow), and the shortest path between them (represented by the weird black arrows). I can select any starting and ending positions in the graph, and it will instantly show me the shortest path between those two positions. I also created some buttons that automatically find the ending position that’s furthest away from the current starting position (in number of moves), the starting position that’s furthest away from the current ending position, or the longest path between any two positions in the entire puzzle. This was helpful, because in general I wanted the starting and ending positions of a puzzle to be as many moves apart as possible. Finally, I created a button that allowed me to export the collection of 100 puzzles to a property-list file, which I could then include in the iPhone application bundle.

Once I solved the graphing problem and implemented the above functionality, I started adding other features that I knew I was going to need in order to design 100 interesting puzzles. First, I added a bunch of criteria that all puzzles had to meet in order to be exported. Most importantly, all puzzles had to be “connected”. In other words, for any given puzzle, it had to be possible to reach every puzzle state from every other puzzle state. I wanted every puzzle to remain solvable, no matter how you moved the blocks. I did include a reset button in the final game, but it’s always optional. Mostly, it’s there so that people can easily input the online solutions when they give up on a puzzle, but sometimes it’s just nice to get a fresh start on a puzzle when you’re stuck in a rut.

I also implemented some other criteria. For instance, I didn’t want the starting blocks to obscure any portion of their destination footprints. I planned on representing the block destinations using painted marks on the floor of each puzzle, and I wanted these marks to be visible at the beginning of each puzzle. There are plenty of perfectly good puzzles in which two blocks (for instance) swap positions, but I decided to disallow these. Beyond this, there are other criteria that are too obscure to even bother describing.

I didn’t know what percentage of puzzles would still be valid after pruning out all of the ones that didn’t meet my criteria. There was some risk that it would be very low, which would make it a lot harder to come up with interesting puzzles. Fortunately for me, this turned out not to be the case.

After about six weeks of working on BlockhouseBuilder, I was finally ready to actually start working on the iPhone app that would read the property-list file and let me play the puzzles I was creating. The bulk of that work took about a month, and then I spent another couple of weeks integrating the two, adding more features to BlockhouseBuilder as the iPhone app required them.

When it finally came time to start designing all 100 puzzles in earnest, I still felt pretty overwhelmed by the task, even with my fancy new tool at hand. Therefore, I added an “Evolve” button to BlockhouseBuilder. This button caused the program  to create thousands of variations of the layout of the current puzzle, looking for various criteria, like a particular ratio between the longest path and the total number of positions. With the click of a button I could have the program spit out a random variation of the current puzzle that was “better” in some way. Determining what counted as “better” was a black art, and I didn’t bother building a UI to tweak these values, because I had no idea what variables I should even be tweaking. Instead, I just kept changing the actual code for the “Evolve” button, recompiling BlockhouseBuilder, and playing around with the results. So I’d set up the basic situation—the size of the grid, the shapes of the blocks—and then I’d start hitting this button over and over again, cranking out a ton of evolved variations. Of course, on top of this I did a lot “artificial selection” (i.e. tossing out results that were unacceptable for various reasons), and manual high-level tweaking.

It was kludgey, but it worked. Exploring the puzzle-space in this way was fascinating, and because of the evolutionary nature of the process, I didn’t automatically know the solution to each new puzzle that I came up with. Not only did this allow me to play (and enjoy) hundreds of these puzzles myself, but it allowed me to directly test how difficult various puzzles were. It also allowed me to answer a few questions I’d been curious about for years. For instance, what’s a good ratio of path length to total number of puzzle positions? I found that it was somewhere between 1:2 and 1:3. In other words, if it takes 15 moves to solve a puzzle, I wanted there to be about 30 or 40 total positions in the puzzle. How hard do puzzles get as you increase the total number of positions? I found that 100 total positions is usually too hard. Most of the puzzles that I included in the final product have between 30 and 80 total positions. On the other hand, there isn’t a one-to-one correspondence between total number of positions and difficulty. I found some 40-position double-block puzzles that I was incapable of solving after multiple hours of trying.

As I explored the space, the puzzles I came up with fell into four distinct categories, each of which had its own flavor. The most basic type of puzzle contained only a single square block. These puzzles were only interesting on grid-sizes of 9×12 or larger, and I decided that they should all be explicitly maze-like. As it turns out, my evolutionary process wasn’t very good at coming up with maze-like puzzles, so I had to do a lot of manual editing on these. Another type of puzzle contained only a single polyomino. These puzzles were also only interesting on grid-sizes of 9×12 or larger, but unlike the puzzles in the previous category, these puzzles didn’t work well as mazes. Instead, they worked well in more open spaces peppered with single-square walls. Another type of puzzle consisted of two or more single-square blocks, each in its own walled-off compartment. These had a unique flavor, and were too difficult if larger than 6×8. The fourth type of puzzle consisted of two polyominoes together in the same compartment. Most of these puzzles were way too difficult if larger than 6×8, but they became easier if the blocks were large, because large blocks fill the space and cut down on the total number of positions possible. This was my favorite type of puzzle, and they make up about half of all the puzzles in the final product.

All in all, it was a fascinating project, and I hope some people get a kick out of the result. You can count on seeing Blockhouse 2 at some point. The puzzle-space is huge, and I’ve got BlockhouseBuilder burning a hole in my pocket…

20 thoughts on “Building Blockhouse

  1. @Dave:

    I’ve certainly thought about it. Of course, there are a number of issues. First of all, the tool as it stands is pretty much unusable by anyone but me. I could polish up a bunch of things, but polish isn’t the biggest problem. There’s the “Evolve” button, for instance, which is currently only useful if you can get in and change the code of BlockhouseBuilder itself. I could take all of the principles I’ve learned about puzzle design so far and create a UI for this, providing sliders and switches to tweak how the evolver behaves. But that will never cover all the different things I might want to try.

    There’s another problem that I didn’t even mention in my post, which is that my code is unoptimized, and as you start building more complex puzzles, things start to drag quite a bit. It takes time to build the puzzle graph and find the longest path between all positions, etc. I can optimize, of course, but that’s not a trivial task. And ultimately, no amount of optimization can handle the combinatorial explosion that results if you add too many blocks to your puzzle or make it too big. Since I didn’t want to sink weeks of development time into these issues, and I didn’t have to worry about other users, I just tiptoed around the issue. I just try not to do things that cause the tool to grind to a halt. Even so, sometimes I accidentally add an extra block to a puzzle, or erase a wall in a segmented puzzle which allows two blocks to come into contact with each other, and the puzzle suddenly jumps from having 40 positions to having thousands. In such cases, I have to go grab a snack while the program churns, or just kill it and reload.

    Assuming that I could come up with some version of the tool that would be fit for public consumption, there’s still the issue of how to integrate the custom puzzle files with Blockhouse itself. The simplest solution would be to create a “Blockhouse Player” app that can be pointed to any url containing a Blockhouse puzzle file (or just integrate this feature into the current app). But that’s a pretty bare-bones solution. Really, you’d want the ability to browse around through a repository of puzzle sets and choose between them, etc. This would all require design and implementation. And, of course, it would complexify the Blockhouse UI, which is currently extremely minimalist.

    My general take is that I’ll just use the tool to make another set of 100 puzzles, and publish it as Blockhouse 2. If there’s demand, I’ll even make Blockhouse 3. After that, if enough people are interested, I could consider making a Blockhouse Player app – maybe even a free one – and throwing a souped-up Blockhouse Builder out there for people to have fun with. (Of course, people could then reproduce all the puzzles from Blockhouse 1-3 for free, but I can think of some ways around that…)

    Anyway, these are just my current thoughts, and I’m interested to hear other opinions.

    • Wow, that PuzzleBeast stuff is pretty cool. I hadn’t seen it before.

      He seems particularly interested in finding simple-looking puzzles that are very hard (some puzzles require 100+ moves to solve). I spent a lot of time looking for medium-difficulty puzzles, and rejecting a lot of really hard ones.

  2. Hello Mr. Heath, love your game and always recommend it to freinds when talking tech. If you could, please keep the color scheme for Blockhouse 2, I’d pay $200.00 for the game. I mean, as an airbrush artist, i know that color drives most entertainment be a Cirque Du Soliel show, Pixar Movie, or carnival. But if you do change your color schemes, maybe like Mobigames “Edge” or texture’s like “15 Blocks” by Mad Finger Games a dual complementary color scheme would be awesome. Anyways, your a genius and love the puzzle!

  3. Please, please, please give me a hint for puzzle 62. Have gone through 74 of them and
    am completely stuck on this one. Love this app! Thanks.

  4. Um, after 3 days of banging my head,
    I got it two minutesafter begging for your
    help. Keep it up. Most fun app I have purchased.

  5. Are there plans to release a Blockhouse 2? I can’t take it much longer, just kidding. Last time I commented it was on the graphics, they were great. Was wondering have you ever thought of making them “metallic-like.” Not the ugly flat metal colors, but the “Kandy Coats” you see on custom hot rods at diners and car shows. Some with flake, and some with a “60’s” feel or even a graffiti-like touch! In all the colors that one could fathom. Heck, that’s the sole reason I bought and buy games in some cases, the art and graphics. Anyway, hope your well and may your days be blessed!

  6. Hi Roger, thanks again for the compliments, both here and in the other thread. Unfortunately, I’ve been too busy at my day job to have time to work on Blockhouse 2. But I haven’t given up on the project. Hopefully, all of this waiting will stir up a MEDIA FRENZY when it’s finally released.

  7. Hi Kory-

    Love the app…however, like Sandra above…I need a hint on level 62. A friend and I brought this to Australia with us and it passed a lot of bus riding time…however, we’re back in the USA and have been stuck on level 62 since Sydney! Can you give us a hint?

  8. Still hanging by my thumbs, waiting for BlockHouse 2. By me, BlockHouse is still one of the top 5 games for iPhone of all time. Please, please consider building another 100 puzzles!

    • Thanks Guy, and sorry for the super-late reply. Unfortunately, I’ve let the project lie fallow for so long that to release anything new I would probably need to rewrite a large portion of the app, which was written in 2009. I’ve been (very slowly) learning Unity, and I think it would make more sense to recreate the original, along with a sequel, in that, so that I could also release it for Android and the web, etc.

      I’m hesitant to make any new promises here, since I’ve already failed to make good on my initial promise of a sequel. I feel bad about that, so hopefully that will drive me to do something about it – eventually! :(

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>