Lisp Game Jam – “Wireworld” in WebAssembly Using Spritely's Hoot Project

This blogpost focuses on our second Spring Lisp Game Jam 2023 entry, wasm4-wireworld, an implementation of Wireworld on top of Hoot's lower-level assembly tools which are a part of our Guile → WASM project to bring Spritely Goblins-powered distributed applications to the common web browser.

For our entry, we targeted WASM-4, a "fantasy console" which uses low-level WebAssembly constructs.

In fact, if you see the animated "wireworld" splash screen at the top of this article, that's running wasm-wireworld itself... you can even run it live in your browser!

A brief intro to Wireworld

The real point of this blogpost isn't Wireworld itself, but how Hoot enabled making this Wireworld demo. So we're going to walk into how Hoot turned out to be an incredible toolkit to build this game jam entry, but first let's talk about Wireworld to give some more context!

Wireworld is a powerful cellular automata, categorically similar to Conway's Game of Life. Unlike Life, Wireworld's paths are fixed: "electrons" flow upon copper wires. The rules of Wireworld are very simple:

• Blank tiles remain blank
• Electron heads always become electron tails
• Electron tails always become copper
• Copper stays copper, unless there are one or two electron heads in any cardinal direction, in which case it becomes an electron head

That's it! Despite that simplicity, this leads to powerful emergent behavior. Electron head and tail pairs appear to "flow" fluidly upon copper wires and can branch easily. But we can also make "generators" and diodes that only permit electrons to flow in one direction and not another:

(Try it live!)

These rules result in behavior which permits visually stunning examples, many of which even look like computational circuitry.

Below is a "binary adder" circuit running our implementation of Wireworld.

Encoded in little endian, 3 (011) + 6 (110) = 9 (1001)! (And here's the live version... press the "x" button to start the simulation when you're ready!)

If you find this kind of thing delightful, see The Wireworld Computer for a tutorial that uses Wireworld to build from the simplest elements all the way up to a computer that can calculate prime numbers.

Try Wireworld yourself!

While building a cool version of Wireworld wasn't the real goal of our participation in the game jam, it was a lot of fun to build... and we hope it's fun to use and play with, too! And since you're reading this in a web browser and we're using Webassembly anyway, why not try playing with Wireworld right here in the browser?

You can click to place wires and electron heads/tails and press X to start/stop the emulation. Enjoy!

Insights from using Hoot to build WASM-4 Wireworld

Our intent in this game jam was to show off how the "lower level layers" of Hoot (i.e. the assembler, disassembler, etc) are themselves useful and powerful and could be used to compile something interactive and compelling. WASM-4's minimalist homage to 80s video game consoles helped us deliver on this focus by encouraging "coding towards the bare metal".

As usual, game jams force you to pair down features. For instance, 4-colored sprites were planned from the beginning, and we considered some unusual additions to wireworld, such as tiles which could make noise, which we thought maybe would allow Wireworld to be used as a custom music synthesizer.

We were happy to be able to deliver a completed and working Wireworld demo by the end of the game jam, but most of these features were removed, and notably we did not yet even have time to properly get in the sprites we had designed... instead we shipped with placeholder graphics using the "hello world" smiley from the WASM-4 tutorial!

We were surprised to wake up the next morning to find that Spritely community member Vivi had taken our program and not only made a cool world with it, but had modified the program itself:

Thus it was Vivi who first put a version of the binary adder (the general design taken from the wireworld computer) inside of wasm4-wireworld. With no assistance from Spritely's internal team, Vivi changed the grid size to render at 40x40 to have sufficient space to represent the binary adder (the sprite data was not changed for this grid redesign in Vivi's initial hack, leading to an entertaining effect resembling renderings from a corrupted Gameboy cartridge). The game jam submitted entry had a 20x20 grid size, but once we saw the binary adder, we knew we had to have it, so we resized the official implementation to 40x40 and redrew the sprites accordingly.

But the biggest takeaways from the jam were that Hoot, while still in early development, is already a very promising and powerful environment for doing low-level Webassembly programming. This merits some further explanation!

How we used Hoot to build wasm4-wireworld

The last time we talked about Hoot (our Scheme->WASM project) we talked about directly compiling Scheme to WebAssembly. This is of course the higher level goal of Hoot: since Spritely's tooling is written in Guile Scheme, we want Spritely to be in the browser, and compiling Scheme programs themselves to WebAssembly is a great way to accomplish that goal.

But what if we wanted to play with WebAssembly on a lower level? It turns out Hoot is a great choice for this: since Hoot uses Guile's compiler tower and has multiple steps of transformation, the lower level assembler, disassembler, etc tools of WebAssembly are also available to the inspired Guile hacker.

Though Hoot will be a complete Scheme→WebAssembly compiler... it already contains a nascent powerful and general WebAssembly toolkit!

---

Getting Technical: Making a minimal WASM-4 cart using Hoot

WASM-4 is intentionally minimal and sparse. No garbage collector extension, and no room for higher level constructs. You've got 64kb of memory, 4 colors, and individual instructions count.

WASM-4 runs fully compiled WebAssembly programs called "carts". A very minimal WASM-4 cart (in fact a cut down version of WASM-4's "hello world" cart) could be defined like so:

(define $smiley$ '(i32.const #x19a0))   (define smiley-data
  #vu8(#b11000011             #b10000001             #b00100100             #b00100100             #b00000000
       #b00100100
       #b10011001
       #b11000011))

(define (our-game)
  `(module
        (import "env" "blit" (func $blit (param i32 i32 i32 i32 i32 i32)))

        (data ,$smiley$ ,smiley-data)

    (func (export "update")
      (call $blit ,$smiley$
            (i32.const 76) (i32.const 76)              (i32.const 8) (i32.const 8)                (i32.const 0)))))              

Here we are using a special lisp/scheme feature called "quasiquote". Quasiquote is enabled with the "back-tick" character appearing before module, switching into read-only data. In this way, inside of our-game, in the places we have written ,$smiley$ we are actually substituting in the $smiley$ definition from the top of the program, and where we say ,smiley-data we are inserting the bytevector describing the smiley sprite. This turns out to be a powerful templating system for producing WebAssembly, and we will use it in greater detail later.

Now let's say we want to try this cart. Since we're in a lisp and lisp culture encourages "live development", let's make a helper utility to compile and run our game:

(use-modules (wasm assemble))

(define* (try-game #:optional (game (our-game)))
  (call-with-output-file "our-game.wasm"
    (lambda (op)
      (put-bytevector op (wat->wasm game))))
  (system* "wasm4" "our-game.wasm"))

Now giving the game a try is as simple as running try-game at the REPL:

scheme@(guile-user)> (try-game)

Here's a version of the cart we just built above running live:

Programmatically generating WebAssembly

Unfortunately, WebAssembly is very verbose. Consider how messy our "update" procedure was already looking:

  `(func (export "update")
     (call $blit ,$smiley$
           (i32.const 76) (i32.const 76)             (i32.const 8) (i32.const 8)               (i32.const 0)))                

This is very noisy! All of those i32.const operations are getting in the way of us placing our smiley and defining its width and height. Not to mention that the final argument defines various flags specified by individual bits which are very hard to remember. If we were writing many of these, this would get very hard to read indeed. Time for an abstraction!

(define (maybe-i32.const x)
  (if (number? x)
      `(i32.const ,x)
      x))

(define* (call-blit sprite-ptr x y width height
                    #:key 2bpp? rotate? flip-x? flip-y?)
  (define flags
    (logior #b0                                        (if 2bpp?   #b00000001 #b0)                (if flip-x? #b00000010 #b0)                (if flip-y? #b00000100 #b0)                (if rotate? #b00001000 #b0)))    `(call $blit ,sprite-ptr
         ,(maybe-i32.const x) ,(maybe-i32.const y)
         ,(maybe-i32.const width) ,(maybe-i32.const height)
         ,(maybe-i32.const flags)))

Now we can update our update procedure to rotate and place the smiley multiple times:

(func (export "update")
  ,(call-blit $smiley$ 76 76 8 8)
  ,(call-blit $smiley$ 42 42 8 8
              #:flip-y? #t #:rotate? #t))

Despite now blitting the smiley twice, and rotating and flipping it on the second version, this is now dramatically easier to read than the first version.

Scheme procedures to generate data and whole programs

While we're not translating Scheme to WebAssembly directly in this particular usage of Hoot, we are using Scheme to generate WebAssembly... and that means we have the full power of Scheme at our fingertips!

This turned out to be hugely useful during the game jam. For instance, while the "smiley" sprite we showed earlier was defined in 1 bit per pixel ("1BPP") and thus could be "seen while squinting" in its binary representation:

(define smiley-data
  #vu8(#b11000011             #b10000001             #b00100100             #b00100100             #b00000000
       #b00100100
       #b10011001
       #b11000011))

However, for Wireworld we wanted to take advantage of WASM-4's support for a 4-color palette to draw prettier sprites. These are not readable as text in pure binary data in the same way. However, for the sake of fast iteration and easy ability to "play with" sprite appearance, we wanted to get back the defined-in-ascii-art approach.

So we did just that. Here are the head and tail sprite definitions:

(define head-text
  "\
X##X
#~.#
#~~#
X##X")

(define tail-text
  "\
XXXX
X#~X
X##X
XXXX")

Here X represents a dark blue pixel, # is dark purple, ~ is light purple, and . is off-white. These sprites are compiled into their binary representation from within Scheme itself:

scheme@(guile-user)> (text->2bpp-sprite-bv head-text)
$7 = #vu8(235 146 150 235 0)

We can then directly insert the binary representation into the assembly of the program! (Understanding how text->2bpp-sprite-bv works is left as an exercise for the reader.)

When constructing this blogpost, we also wanted a way to generate multiple Wireworld WASM-4 carts which each started with an initial world state. Once again, we wanted to define these in plaintext for fast iteration and experimentation while preserving readability:

  *#                                #@
 @  ################################  *
  #                                  #
 #                                    #
  #                                  #
 #                                    #
  ######     ####### ####   ####     #
 #     #     #   #   #   # #          #
  #    #  #  #   #   ####   ###      #
 #     #  #  #   #   #  #  #          #
  #    #  #  #   #   #   # #         #
 #      ## ##  #######   ## ####      #
  #                             ######
 #                                    #
  #                                  #
 #                                    #
  #  #     #   ##   ####  #    ###   #
 #   #     #  #  #  #   # #    #  #   #
  #  #  #  # *    @ ####  #    #  #  #
 #   #  #  # @    * #  #  #    #  #   #
  #  #  #  #  #  #  #   # #    #  #  #
 #    ## ##    ##   #   # #### ###    #
  #                                  #
 #                                    #
  #                                  #
 #                                    #
  #                                  #
 *  ################################  @
  @#                                #*

Writing a text parser interpreted by a WASM program for reading textual wireworld descriptions would have been too much work (both for us and for the spirit of an old-school fantasy console). We took the same technique as with the textual representation of sprites: our Scheme program loaded and translated worlds from the textual representation to the very in-memory representation our WASM-4 game would use, then thanks to the power of quasiquote, we simply inserted the game into the generated program.

The really cool thing here is that the generation of carts is itself a procedure. Generating a custom cart is as simple as:

(wat->wasm (make-wireworld-game
            #:world (load-world-file world-filename)))

Thus our make file could simply spit out custom files with custom initial world states, "baking" the initial level descriptions into memory:

$ make
Built build/wireworld-adder.wasm
Built build/wireworld-splash.wasm
Built build/wireworld-intro.wasm
Built build/wireworld-blank.wasm

If you've ever heard lisp programmers talk about "programs that write programs", consider this a nice example!

Lessons learned and meta-observations

Our biggest successes were when we began embracing the abstraction powers provided by Hoot. Initially we simply hand-coded using WebAssembly's textual format and compiled such files. Once we moved to the scheme-as-code-generator abstractions shown in this article there was a marked uptick in productivity and correctness. Code became easier to write and understand and iteration became faster. Tools such as the textual representations of sprites and levels became easy to directly integrate. And significantly, by embracing the "programs that write programs" philosophy, generating the custom carts shown off in this article became as simple as passing in the relevant arguments to the procedure which "baked" the carts with the relevant levels. This latter part was particularly satisfying but was simply a natural outgrowth of the style of programming we took.

Hoot's primary goal is to get Spritely's tooling available in the browser by directly compiling Scheme to WebAssembly. However it turns out that Hoot's lower level layers of abstractions are powerful tooling in their own right! Game jams are a great opportunity great opportunity to put your tooling to the test, and we're delighted with the outcome.

from Hacker News https://ift.tt/2Zv9D0K