https://www.cole-k.com/2023/02/21/tiny-games-hs/

home

    

  * Posts
  * Tags
  * About

Squeezing a sokoban game into 10 lines of code

Call-by-push-block

Published Tue, Feb 21, 2023 by Cole K

If you're only interested in seeing or playing the game, you can find
it on my GitHub.

The occasion

The Haskell Tiny Game Jam is a game jam which challenges participants
to write a video game in Haskell using 10 lines of 80 characters. I
happen to love Haskell and code golf (abusing a programming language
to produce disgustingly short code for fun) so I decided to enter the
Feb '23 jam.

My journey

My game is called Call-by-push-block. It's a Sokoban, or
block-pushing game, where you take a lambda code golfing ("golfing"
here is meant a little more literally).

A gif of the first level of Call-by-push-block

I started with an initial game that had player movement, pushing a
single block, and a single test level. I already had employed a few
code golfing tricks, but the code stood at 40 lines and was
reasonably legible.

Many ugly hacks later, I ended up with a game that also included a
level and score counter, undoing, resetting, pushing arbitrarily many
blocks, 14 levels, and some other features to be discovered by the
player. It stands at exactly 10 lines of 80 characters. It is
disgusting and I'm fiercely proud of it.

n="Yan hiZha tiXu megaKai kttseeki[?]Jia nyaanyaaZi Yao An Xia [?]Quan Jian [?]lZSuo [?]"
e('l':c)|(a,b)<-span(>'n')c=u(u a#m 1 b)%e(y b);e(c:d)=c:e d;e l=l;k="l.";m=take
v(x:_)=c x`mod`7;v _=0;l=print;s=[]:s;c=fromEnum;i="\no .#_l+";y=drop 1;(%)=(++)
e&0=u.t;f&_=f;p=putStr;(1?f)x=z x;(5?f)x=y x%z x%z x;(i?f)x=(f&i$r e$f$head x):x
r=map;main=print=<<(mapM g.zip[1..].r(pure.words).lines$r(i!!).m 5.w=<<r c(n%x))
g(k,o)|any(elem '_')$head o=do{k!o;p b;i<-v<$>d;g(k,i?([t.u,t,id,t,t,t,r u]!!i)$
o)};g(k,x)=a x<$k!x<*p"-"<*d;t=foldr(zipWith(:))s;z=m 1.u;w n=n`mod`8:w(n`div`8)
n!x@(s:_)=p"\^[cLvl "*>l n*>l(a x)*>p(unlines s);d=getLine;(_:r)#""=r%k;_#""="."
n#"."=n%k;(_:r)#"+"='.':r%k;_#"+"="..";('o':r)#"_"='O':r%k;l#x=x%l%"l";u=reverse
a=length;b="l:wasd :x :u\n";x="Pen 3Si [?]Ling [?]Di [?][?] baaDang teeChan [?]Xi [?][?][d1678][?]Jiong [d123478]"

In this post, I'll give you several tips that you can use to reduce
your own Sokoban game to a mess of letters and operators like the one
above.

Forgo any and all style

Do you like descriptive function names?

resolveMove index modifyGrid = undoMove modifyGrid index . map move . head $ gameGrid

Too bad, it's too many characters.

r i f = u f i . o m . head $ x

Think Haskell has too many arcane operators? Sorry, it's shorter.

i?f = (f&i) . o m . head $ x

Does this disgust you yet? It should, because we have to put parens
around i&f to prevent GHC from getting confused by operator
precedence. And someone left in spaces!!

i?f=f&i$o m$head$x

Much better. Now slap a semicolon on it and jam it in somewhere.

(My challenge to you for this tip and the other ones that have code:
see if you can find the actual source code corresponding to its
example. Just like with the Tiny Game Jam, there is no prize other
than your self-satisfaction.)

Think like a C Programmer

My game has 6 controls: wasd for directional movement, x for
resetting, and u for undoing. The way I would properly approach
handling inputs would be something like

data Input = Up | Left -- ...

charToInput c = case c of
  'w' -> Up
  'a' -> Left
  -- ...
  'u' -> Undo

gameLoop gameGrid = do
  c <- getChar
  handleInput (charToInput c) gameGrid

We're already over 10 lines and I'm trying to be terse in my example.
Not only that, the case keyword and each -> takes up so much space.

Instead, we can think like C programmers and use the Enum instance
for Char, for which fromEnum produces a char code. Then we just need
to find a modulus where wasdxu are unique and we can use fromEnum c
in that modulus to index into a list of commands. Luckily for us, 7
gives unique values.

charToInput c = fromEnum c `mod` 7

gameLoop gameGrid = do
  c <- getChar
  let command = [moveRight, moveLeft, ...] !! charToInput c
  command gameGrid

"Hold on," you might stop me, "What about the other index mod 7 that
none of wasdxu map to?" Good question, just put the smallest variable
you can get to type check there. All keys will do something, but we
will only tell the players what 6 of them do.

Abuse loopholes

There are 610 characters used across all the levels in
Call-by-push-block. A careful reader will observe that there are not
610 characters worth of strings in my code. So where do they live? In
the horrifying Unicode strings on the first and last lines.

I need 8 unique characters for my levels: 6 for tiles and 2 for
separators. A limited tileset like this allows you to smush 5^1 tiles
into a single Unicode character. The relevant loophole here is that
the judges count characters, not bytes^2, so this cuts the levels'
footprint by a factor of 5.

Here's how you can encode your levels. Start with the characters
list. First, map each tile to a number between 0 and 7. Now you have
a list of digits in base 8. Next, take 5 digits at a time, interpret
them as a number in base 8, and convert to decimal. Now you have a
list of decimal numbers that is 1/5 the size of the original.
Interpret the decimal numbers as Unicode characters and you're done.

One small wrinkle: GHC doesn't allow raw strings and requires strings
to contain printable Unicode. To work around this, I simply iterated
over every possible permutation of digits to assign my tiles, encoded
my levels, and checked the characters in each encoding against
GHC.Unicode.isPrint. There were a bunch of printable encodings so I
picked one that had funny emoji in it.

With this trick, you can go from half of a single level

x="oloo.... ooll_____ olool____ looool... ........."

to a little over two much bigger levels

x="Pen 3Si [?]Ling [?]Di [?][?] baaDang teeChan [?]Xi [?][?][d1678][?]Jiong [d123478]"

Even though it doesn't look it, the latter is fewer characters, too.

If this tip would actually be helptful to your own tiny game, then
you can check out the code I wrote for it (warning: it is gross and
uncommented) and refer to the decoding function in my golfed code,
which of writing is named w (I shouldn't need to warn you about this
one).

Solve NP-Hard problems by hand

A Haskell file is basically just a bunch of variable declarations.
The same is true for a very golfed one, it's just harder to make them
out. I count about 30 variables in my game.

Often when golfing you can reduce the overall character count by
moving around some logic, resulting in one line being 2 characters
over and another 5 under, for a net gain of 3 characters.

What do you do after this? Rearrange the variables so that all of the
lines are within the character limit.

Sound hard? That's because it's NP-Hard.^3 It's an instance of the
Bin packing problem where the items are variables, sizes are their
lengths, and bins are each of the 10 lines. Have fun and don't forget
that you need semicolons to separate your variables!^4

Only move right

The grid of tiles in my game is just a list of of list of Chars. An
unfortunate downside of Haskell lists being linked lists is that it
is much harder to move vertically in the grid than it is to move
horizontally. Should you encode your grid the same way, there is good
news! All you need to do is write code that moves the player to the
right.

moveRight :: [[Char]] -> [[Char]]

Need to move to the left? Reverse all of the rows first, move right,
then unreverse them.

moveLeft = map reverse . moveRight . map reverse

Need to move down? Transpose the grid, move right, then untranspose
it.

moveDown = transpose . moveRight . transpose

Barring moving up (which I have conveniently omitted), we can
abstract a pattern out:

move dir = transformation . moveRight . transformation
  where
    -- 0 = right, 1 = left, 2 = down, 3 = up??? >:(
    transformation = [id, map reverse, transpose, undefined] !! dir

Maybe smart math people can figure out a way to do upward movement
that doesn't require annoying special casing. If you figure it out,
don't tell me since it means I'll have to make more levels. With the
special casing for moving up, you'll end up with something like

move dir = undo dir transformation . moveRight . transformation
  where
    -- 0 = right, 1 = left, 2 = down, 3 = up
    transformation = [id, map reverse, transpose, transpose . reverse] !! dir

undo 3 _ = reverse . transpose -- special case for undoing 'transpose . reverse'
undo _ f = f                   -- everything else undoes itself

Ask HLS

The Haskell Language Server is a helpful tool for doing proper
Haskell development. It can also help with improper development if
it's not busy freaking out about all of your missing type signatures.

Throughout the course of golfing, you might end up with code like

(l!!x)$y

Spot the mistake? You don't need to! HLS will helpfully report

Redundant $ found,
  Found: (l !! x) $ y
  Why not: (l !! x) y

Make sure to ignore the spaces in its suggestions though, those are
for proper developers.

HLS trying to insert type definitions on the side of my code

Look how hard at work HLS is. Does proper code even need type
signatures?

Forget what you know

It's often said that authors have difficulty finding flaws in their
own works because they know them so well. Empty your mind and let
inscrutable code be your superpower.

Ignore all but the single function you need to update. Once it's done
and your code now has a bug, you'll likely find spots you missed as
you mentally trace the haphazard path your code follows when it
executes. These spots might be things like

  * A short alias for a function that in fact makes your code longer
  * A completely unused function (I guess HLS was too busy trying to
    fill in type signatures to inform me)
  * Two of the same function written with different names

Proof that the method works: I shaved three characters off while
trying to understand code I refer to in this blog post.

Kill many birds with one stone

Originally, my game did not have an undo. Adding undo was the number
two request^5 from my playtesters. I also wanted to add a move
counter to give some replayability since my game didn't utilize
randomness.

I initially dismissed my playtesters' requests as unreasonable and my
own as unnecessary. Then I forgot how to solve a level I was pretty
sure was solvable and decided adding an undo was a good idea.
Unfortunately I was already at the character cap. What allowed me to
add both undoing and move tracking was refactoring how I reset the
game grid.

My game loop took a tuple containing the current grid and the initial
grid. Resetting replaced the grid with the initial grid.

handleInput (grid, initialGrid) Reset = (initialGrid, initialGrid)
handleInput (grid, initialGrid) input = (move grid input, initialGrid)

Let's forget about resetting for a second and change this to just
support undoing. Instead of keeping track of the initialGrid, we can
keep a list of every past grid. Then if we want to undo, we just
replace the current grid with the grid that came before it. When we
make any other move, we now we have to add the current grid to the
list of past grids.

handleInput (grid, (pastGrid:olderGrids)) Undo = (pastGrids, olderGrids)
handleInput (grid, pastGrids) input            = (move grid input, grid:pastGrids)

This works well, but there's way too many parens and other stuff
going on. It's fewer characters if we put the current grid onto the
front of the list.

handleInput (grid:pastGrids) Undo  = pastGrids
handleInput (grid:pastGrids) input = move grid input : grid : grids

Now for resetting. The cruel game dev would just say "reset = undo
many times." I like to think I'm not that cruel. Fortunately, we can
reset without too much trouble by removing everything except the last
element.

handleInput grids Reset = [last grids]

Remember how I said I wanted to add a move counter? Before, this
would require threading the counter through my game loop, which would
take a bunch more characters. Now with the new list-based format, the
number of moves is just the length of grids. Well, technically the
length of grids minus one since the initial grid doesn't count toward
a move.^6

The astute reader will observe that there are few issues with this
implementation. The first is that this function is partial and will
crash the game if you try to undo from the initial state. The second
is that the [DEL:move:DEL] score counter doesn't count undos because
undoing decreases the length of the list. We can fix both of these by
just throwing some copies^7 of the initial grid onto the end of the
grids list whenever we undo.

handleInput grids Undo     = tail grids ++ initialGrid grids ++ initialGrid grids
handleInput grids Reset    = initialGrid grids
handleInput (grid:pastGrids) input = move grid input : grid : grids

initialGrid grids = [last grids]

It's still technically partial but who cares other than HLS?

Motivate yourself

I spent a lot of time staring at the garbled mess that is 809
characters of the tersest possible Haskell you can write using
Prelude. It takes willpower to keep searching for more ways to cut
another characters off. Here are three possible motivations.

Create levels with reckless abandon

A thoughtful tiny game jam developer might design levels with a
character count in mind. I just sort of made levels until I felt I
couldn't come up with any more interesting ideas. At that point, I
ended up about 20 characters in the red. So I golfed 20 characters
off.

The tile calculus

I'm used to golfing 30-character programs where removing a single
character is a pretty big accomplishment. In an 809-character
program, the value of a single character can be harder to appreciate.
That is, until I implemented tile compression.

If you compress your tiles, suddenly the two 'e's in the word "Level"
represent a quarter of a level. The four characters you save by
replacing "Reset" with "" are another half.

With this mindset, even a cutting a single character could result in
a small level that teaches how a new mechanic works.

Rick Roll the judges

Did you happen to read the first column of my game's source?

As I was writing up this post, I noticed that almost every single
line began with a variable. At a first glance, "never gonna" wouldn't
work because variables need to be unique. I realized, however, that I
was very close to being able to rearrange some infix function
definitions so that the variable bound was at the beginning of the
line. This would allow me to shadow an existing variable and
therefore duplicate a letter.

To do this would require me rearranging lines and golfing at least
one character off of an infix function. So, well, I set out to do
that and in the process I actually discovered some more tricks to cut
off three characters total.

Never underestimate the creativity born out of desire to make a
stupid joke.

In conclusion

Although code golfing is an ultimately frivilous endeavor, I had a
lot of fun trying to fit as much as I could into my game and I'm
pleased with how it turned out. I especially enjoyed asking my
friends, "Hey, do you want to play this game I made?" and just
sending them 10 lines of nonsense that somehow spits out a video game
when fed into GHC. While I don't expect you to ever make (serious)
use of these tips, I hope you liked them.

Call-by-push-block can be found as a submission on the Feb '23
Haskell Tiny Game Jam. And if you enjoyed this content, be sure to
check out the other tiny games there too!

Detailed instructions on running Call-by-push-block (including in
your browser) can be found on my GitHub.

Addendum

Being able to undo past resets

In a comment on Lobste.rs, hwayne suggested making undos work across
resets. For example, reset then undo should bring you back to the
state you were in originally. I replied with a 2 character change to
my code to support it. In that reply, I challenge you to find where I
made the change, but here I'll explain what the change is.

I described in Kill many birds with one stone how resetting replaces
the grid list with the initial grid.

handleInput grids Reset = [last grids]

In order to support undos across resets, we can instead put the
initial grid at the front of the list.

handleInput grids Reset = last grids : grids

It's really that easy.

Unfortunately, it does have a cost: resets no longer reset the score.
Instead, they're counted the same as any other move. This goes
against my game developer philosophy, but I might end up changing my
mind and implementing this feature in my submission. Thanks, hwayne!

Comments

My website is janky and doesn't support commenting (sorry!). If you'd
like to leave a comment, feel free to do so on Reddit or Lobste.rs.

---------------------------------------------------------------------

 1. Technically, it should be possible to fit 6 tiles into a single
    Unicode character, but there ended up being too many characters
    that don't fit in printable Unicode and the escape characters
    required to encode them took up too much space. A more
    intelligent algorithm might check adding a constant shift after
    the base-8-to-decimal encoding, but if you find one don't tell me
    because I don't want to make more levels. -[?]

 2. Usually code golf competitions count bytes and many of the
    Unicode characters I'm using to store my levels are multiple
    bytes. If the Haskell Tiny Game Jam counted bytes, my compression
    factor would be closer to 1/2, which is what I'd get fitting 2
    tiles at a time into an ASCII character. -[?]

 3. Yes, it's probably fallacious to claim that because bin packing
    reduces to my problem, the instances I solved are computationally
    intractable. Let me have this one, though. -[?]

 4. I now want to make a tiny game that reads its own horribly-golfed
    source and challenges the user to play Bin Packing with its
    variable declarations. Then they could know how I feel.
    Humorously, the code would be its own solution, so you could
    cheat by copying it. -[?]

 5. Number one was to use wasd instead of hjkl for movement, which I
    begrudgingly obliged. It's a shame since hjkl would allow me to
    save about 3 characters because it needs a smaller modulus to
    produce unique remainders (see: Think like a C programmer). -[?]

 6. Because of this technicality I decided against adding a move
    counter and instead added a score counter which happens to be
    equal to the number of moves plus one. -[?]

 7. I chose to add two copies because if you only added one, the
    score wouldn't change when undoing and that felt wrong to me when
    I play tested it. Adding two is a stylistic decision - the code
    would work fine if you only added one. -[?]

Tagged: essay, programming, haskell

home

 

(c) 2023 / Powered by Hugo

Ghostwriter theme By JollyGoodThemes / Ported to Hugo By jbub