Matt McCutchen's Web SiteEmbedding Klotski in Escape  (Top, Background, The levels, How to play, The embedding implementation, Bottom).  Email me about this page.

Embedding Klotski in Escape

Background

I enjoy the puzzle game Escape, and while idiomatic Escape levels are plenty of fun, I was intrigued by levels that embed other well-known puzzles, meaning that the Escape player can input a solution to the other puzzle via some reasonably natural means and will be allowed to win the Escape level if and only if the solution to the other puzzle is valid.  (A computer scientist would call this a reduction of the other puzzle to Escape.)  Escape supports various puzzle elements that can be used in embeddings; the easiest route I know to arbitrary computation is to have bots push buttons that trigger circuits containing remotes that switch other circuits on and off, but some embeddings use other techniques such as forcing the player to follow a particular path and push blocks that affect other parts of the level via panels.  One of the best embeddings so far is this implementation of a game most often known as "peg solitaire".

The Escape community encourages users to develop and share their own levels.  While I don't feel that I have any idea for an idiomatic Escape level that would add to the thousands of levels already available, I was excited to try to embed another puzzle game I've played recently: Klotski.  As an initial goal, I wanted to embed the well-known "Red Donkey" puzzle.  This turned out to be much more difficult than I expected.  I developed a complete design featuring an attractive "direct manipulation" UI in which the player could walk on the Klotski board and "push" Klotski pieces directly by pushing buttons on their sides.  Since my design would require about 10000 tiles for Red Donkey (the number depends on the board size and certain other properties of the Klotski puzzle), I decided to write my own program to generate the Escape level rather than build it manually in the level editor and risk needing massive manual rework if I found problems.  However, as I read the Escape source code to learn about the level format I would need to produce, I noticed the limit of 2048 tiles in a level.  At first I thought the project was a total loss, but then I identified compromises I could make in the UI and changes to the implementation that would reduce the number of tiles.  After a series of dirty tricks, I got the tile count low enough that I thought it was worth a try to add back a UI feature I had removed, and with further dirty tricks, I barely succeeded in doing that within the limit.

In addition to Red Donkey, I have generated an Escape level for Trail, another Klotski puzzle that is identical to Red Donkey in all the parameters that affect the size of my embedding but is somewhat more difficult to solve.  I'm confident that if the tile limit were removed, my current design (or, indeed, my original design) would generalize to arbitrary Klotski puzzles.  (Exception: I haven't implemented the special cells that are passable only by the goal piece.  In many puzzles, the use of these cells is gratuitous because it is equivalent to specify a goal zone just inside these cells, but in a few puzzles, they are important.  I believe the feature would not be difficult to add.)  Most of the major components of the embedding are trivial to resize to handle arbitrary puzzles.  However, the wiring that connects the components is not.  I built it manually for the common embedding size of Red Donkey and Trail and didn't believe it was worthwhile to work out the generalization at this time, but I'm sure it could be done.

The levels

You can download the Escape levels for Red Donkey and Trail here or use the Escape application to download them from the main Escape server (escape.spacebar.org).  Comments are welcome on the level pages on the Escape web site or may be emailed to me and I will add them to this page if I judge them to be of general interest.

For reference, solutions to the Klotski puzzles are available on this web site.

How to play

I tried to make the UI of the levels as self-explanatory as possible given the Escape tile limit, but if you need a little help, look right here.  This description assumes you already know the rules of Klotski.

In the Escape level, you begin in an area with a 4 by 5 grid of blue panels corresponding to the cells of the Klotski board.  The current state of the board is displayed to the right, with margins added between neighboring rows and columns so it is possible to see whether neighboring occupied cells belong to the same piece.  Pieces are in blue; the goal piece has bumps.  The goal zone (to which the goal piece must be moved to win) is in green.  When a piece overlaps the goal zone, the area of overlap is in red.

Klotski pieces can only be moved one unit at a time.  To move a piece, first move the blue steel block onto a panel corresponding to one of the cells of the piece (it does not matter which), then press the button labeled with the direction in which you want to move the piece.  A common mistake is to try to move a piece several units by pressing directional buttons without moving the steel block to follow the piece.  Attempting an illegal move has no effect, although if you have animation enabled, you will see the piece disappear and reappear in its original location; this is an artifact of the implementation that would be difficult to remove without exceeding the tile limit.  (Animation is slow, so if you are just trying to solve the puzzle and not watch the mechanism work, you'll probably want to disable animation by pressing Ctrl-A if you have a new enough version of Escape or otherwise in the preferences.)

When you have aligned the goal piece with the goal zone, the exit at the upper left will wake up.

The embedding implementation

For a real challenge, try to reverse engineer the levels.  (You'll probably want to make a screen recording of the animation and play it back bit by bit.  Since Escape supports animation only at full zoom, if you don't have a large enough monitor to see the whole level at full zoom (~1600x1600), you'll need to make the recording within a virtual display server such as Xephyr.)

Or if you prefer, download the program that generates the levels and look at the comments there.


Matt McCutchen's Web SiteEmbedding Klotski in Escape  (Top, Background, The levels, How to play, The embedding implementation, Bottom).  Email me about this page.
Modification time of this page's main source file: 2019-07-04 15:57:32 +0000
Except where otherwise noted, Matt McCutchen waives his copyright to the content of this site.  This site comes with absolutely no warranty.  Why?