Rust, WASM, and LOK

Have you played LOK? It's a puzzle game in the form of a grid of squares with letters in them. You pick cells from the board in certain orders to activate "keywords" and then execute the effect of the keyword. The objective of each puzzle is to black out all the squares on the grid.

I purchased the physical book a while back and finished it recently. I had a lot of fun, especially with some of the later levels that have pretty cool reveals. There's also a video game version of LOK in development, which got me thinking about how someone would make that, given the types of puzzles in the book. I love developing in Rust and had been thinking about experimenting with WASM to see its capabilities and how Rust works with it, so decided to combine these two together into a side project I uncreatively called LOK-Wasm.

I'll give a little overview of the architecture, but I think the more interesting parts are the game design aspects and how to set up the interface for the player.

These are of course spoilers for the game's mechanics, but if you want to try it out, with the author's permission, I have it hosted at https://knutaf.com/lok_wasm. And if you want to see the source code, I have it hosted on my github.

Rust + WASM

First of all, a quick rundown of what WASM is. It stands for Web Assembly. In essence, similar to how Java compiles down to a bytecode that is interpreted by a Java Virtual Machine, Web Assembly is a different bytecode interpreted by the browser. Many different languages can compile into WASM, and Javascript can interface with it like a module. In my case, I wrote a lot of the source code in Rust and compiled it down to a WASM module, then called into it from Javascript.

Could I have written the whole thing in Javascript? Sure, but what would be the fun in that?

Like many Rust features, there is a Rust/WASM tutorial and book that was very good. I was able to follow the tutorial to get up and running with development pretty easily... though this entire ecosystem kind of has way too many moving parts. Webpack? NPM? Nodejs? Just for this? It's a bit heavyweight, but I guess like 90% of the development in the world uses stuff like this now, huh?

Using that tutorial, I was also able to run npm run build to produce the distribution package of static files I then uploaded to my web site for sharing. I wrote this paragraph in here as much for me as for you, dear readers, because I had to go looking on the Internet to figure out this magic incantation. Probably someone well-versed in NPM packages would have known this right away, but alas, I'm not that guy.

I was able to easily upload the few files it generated to my web hosting provider. I did have to set up the MIME type for the WASM file there, by adding the following to my .htaccess file:

AddType application/wasm .wasm

The Rust/WASM interface

Having gone through the tutorial, I needed to decide what the architecture of my game was going to be. My main guiding principle was that I wanted most of the code to be in Rust, especially the logic that implemented the rule checking. I decided I was OK having some static HTML and CSS for display, and Javascript to "render" objects exposed by the WASM module into the right HTML.

The LOK puzzles are all grid-based, so I grabbed an old Grid object I had previously written in Rust. Following the Rust tutorial, I exposed the contents of the grid as an array of u8 so that the Javascript side could map the region of memory for fast, direct access. I like this sort of thing in general, so I wanted to see if I could make it work.

Well, I was able to keep that for a while, but as I implemented more of the LOK rules, I ended up having too much state I needed to store on each BoardCell object, so I abandoned the mapped u8 array idea and just exposed a Board::get accessor to fetch a cell by row/col. I'm sure this incurs marshaling overhead, but my n is so small that there's no way it matters--LOK puzzles just aren't that big. Maybe 10x10 at most.

So I had just two classes exposed: Board and BoardCell. Board had getters like the height and width and of course fetching each cell. It also had actions, the verbs allowable by LOK puzzles. BoardCell only exposed getters necessary for rendering the puzzle in HTML: things like whether a cell should be interactable, what letter to draw on it, and how it should be styled.

The Javascript code iterates over all the cells in the Board, fetches each one, and generates a table with tr and td in it, applying different CSS classes to the cells depending on the current state of each one.

One important part of the UI is the ability for the player to enter a puzzle. I just used a textarea and let the player write in monospace font in it. If you want a 2x3 puzzle, just enter two rows of characters with 3 characters in each row. Underscore indicates a blank cell and a dash is a gap in the board. That's all you need to represent LOK puzzles. I thought about having a grid-based editor, but my I thought about wrangling all the event listeners and CSS styles and just felt tired, so I didn't.

The other verbs I implemented in the UI were the different actions you can take in the LOK puzzle, an undo button, and of course one to submit for checking if you have a proper solution entered.

Undo

The undo functionality was implemented in an inefficient but simple way. Every time the player makes a move in the puzzle, I copy the entire grid plus the move they made, modify the new copy of the board, and push them onto a stack. Undo simply pops the top of the stack, so the previous board state is now the thing to render. That also pops the latest move, keeping the board state consistent with the list of moves that got it there.

/// Marks the specified cell as blackened and tracks this move in the solution.
pub fn blacken(&mut self, row: usize, col: usize) {
    assert!(row < self.grid.height());
    assert!(col < self.grid.width());

    // Make a copy of the entire board and store that with the move, for easy undo.
    let target_rc = RC(row, col);
    let mut new_grid = self.get_latest().clone();
    new_grid[&target_rc].blacken();

    self.moves.push(BoardStep {
        mv: Move::Blacken(target_rc.clone()),
        grid: new_grid,
    });
}

/// Removes the latest move from the solution.
pub fn undo(&mut self) {
    let _ = self.moves.pop();
}

Checking the solution

I did most of the game logic for checking the solution with test-driven development. It was easy to do it this way because of the simple nature of the code with no external dependencies. My tests set up a puzzle and then enter in the moves to solve it. The checker returns a result that indicates if it was successful, or if not, specifically why it failed and at which move number in the attempted solution. This let me author tests for every specific failure type.

#[test]
fn lok1x4_correct() {
    let mut board = Board::new("LOK_").unwrap();
    board.blacken(0, 0);
    board.blacken(0, 1);
    board.blacken(0, 2);
    board.blacken(0, 3);
    assert_eq!(board.check_solution(), SR::Correct);
}

#[test]
fn lok1x5_unsolvable_out_of_order() {
    let mut board = Board::new("LKO_").unwrap();
    board.blacken(0, 0);
    board.blacken(0, 2);
    board.blacken(0, 1);
    board.blacken(0, 3);
    assert_eq!(
        board.check_solution(),
        SR::ErrorOnMove(1, ME::BlackenNotConnectedForKeyword)
    );
}

In whatever projects I work on, especially at work, I'm a big fan of having different error codes for different codepaths. If I had it my way, every error would uniquey identify which call-site it came from. I managed to do that with this project, so the test code very nicely describes the expectation in each case.

The checker iterates over the ordered list of moves that the player (or test) entered and modifies a copy of the puzzle grid for each step. It also keeps track of what state it's in--like gathering a keyword or executing a specific keyword, accompanied by any extra info about the current state. Rust's enum types are great for this.

enum BoardState {
    GatheringKeyword(String, Vec<Move>),
    ExecutingLOK,
    /// ...
}

Each move is checked against the current state to decide if it's permitted or not. Finally, after all the moves are done, it checks the overall grid remaining to make sure it's complete.

Code Coverage

As of the time I'm writing this blog, the main file is 2665 lines long, of which 63% of it is tests. I wrote a lot of tests! Towards the end, I also tried out Rust's code coverage support to see what tests I'd missed. It was cool because it found some tests that were not catching the conditions I expected and areas I'd forgotten to cover.

Rust's code coverage support is heavily based on what LLVM provides. There's a pretty decent suite of tools, and they're runnable from cargo (Rust's build tool). There's a good section of the book on code coverage, including how to instrument your code, generate data, and analyze data. I was able to follow it pretty easily.

One tweak is that the book suggests cargo-binutils is optional, but I couldn't really find a good way to run the tools without it.

Here's the script I ended up using for generating a coverage report:

del default_*.prof*
cargo test
cargo profdata -- merge -sparse default_*.profraw -o default.profdata
cargo cov -- show -Xdemangler=rustfilt target\debug\deps\lok_wasm-4d4ce0b412053771.exe --instr-profile=default.profdata --output-dir=coverage --format=html

After a few iterations of generating reports and adding tests, I managed to get 98% line coverage, and the only remaining parts were bits exclusive to the UI. Not bad at all. I don't think I've ever managed that with a project at work, heh.

Mobile version

I was pleasantly surprised to find that it Just Worked on my phone's browser. I guess that's the power of WASM?? I don't know. Actually I had to add one magical incantation:

<meta name="viewport" content="width=device-width, initial-scale=1" charset="utf-8" />

Apparently this fixes font scaling on mobile browsers? I don't know. Without it, the font sizes were all over the place, way too big in some places, way too small in others.

SPOILER WARNING for next section

The sections after this one are full of spoilers for the LOK mechanics. The original game does a great job of guiding you through learning how to play, gradually ramping you up on more complicated mechanics. It's masterfully done, so if you were thinking of playing, I recommend not reading the next section onwards.

Without spoilers, I can say that my number one guiding principle was to have my version reveal as little as possible about how the mechanics work. It is an oracle: you can submit a solution and get a result of yes/no, but if you want to know how the mechanics work, well, I've deliberately tried to make that difficult.

OK, now go away. Unless you've aready beaten the game, in which case, welcome!

Gathering Keywords

Reminder: spoilers from here on out. OK, let's go. So a big part of LOK is keywords. The main verb that players have for a good chunk of the book is "blackening" out a cell. If you black out all the squares in the right order that make up a keyword, you then get to (have to, actually) use the keyword's effect.

So of course I had to add a "blacken" verb to the UI. However, unless I took care with it, I could accidenetally leak information about how the mechanics work.

When you blacken a square, it does change color. However, you can click on it multiple times. Normally this would be a no-op, but I don't want to reveal that, so instead the letter in the cell gets a little superscript showing how many times it was clicked on. This lets the player know their click was registered and also lets them know their "undo" was registered, if they hit Undo.

I guess I could have made it a toggle, even though that's not valid in the game either, but that would be misleading, because a player might think the toggle acts like an Undo, but I didn't implement it that way.

When the player has successfully blackened out a keyword, there's no feedback in the UI that they've done something interesting. The solution checker is expecting the player to execute the keyword correctly next, but the only feedback the player gets is a "yes" or "no" when they click the "Check!" button, not when they interact with the board.

Conductors and Paths

Implementing the keywords LOK, TLAK, and TA were pretty straightforward. They all only use the "blacken" verb. The next choice came when implementing the conductor, 'X'. Conductors allow you to gather a keyword by selecting cells that aren''t in a straight line; you can "bend" the line at right angles.

In terms of interface, I could have chosen to just let the player pick the cells of the keyword without requiring them to enter any additional information about what path they're using. In fact that was my first thought. But then I started thinking about having to write the pathfinding code to verify that the player chose a valid path and realized: hey! why should I do this? The player should be telling me what path they want to use, and I can verify if it's valid. Let them do the hard work, right?

The other advantage of forcing the player to enter the path is that there's less chance of accidentally getting a puzzle correct without fully demonstrating an understanding of the solution. In other words, the player could enter an underspecified solution and get lucky.

The downside is that it reveals information about the mechanics, namely that the concept of a "path" exists. The way I presented it in the UI is there is a set of radio buttons corresponding to different modes, like "blacken" and "mark path". When the player uses "mark path" on a cell, it gets a border and increments the superscript on it--just enough to let them know that their click had some effect, but probably not too much about what it means.

Editing Cells

The final major UI change I had to make was to allow players to edit the contents of cells. Why? Because the BE keyword and the ? wildcard allow for it. I added a new mode, called "Edit". The player can freely edit whenever they want. I only allow changing characters to a single other character, but without much restriction on what they can change into. I hoped the freedom conferred by this mode didn't give them any information about why they'd want to do this or what the rules around it are.

I had a lot of fun with this project. It was simple and I learned some things. And of course I enjoy writing things in Rust. Go buy and play LOK! It's really good!!