Tower of Hanoi in P5.js + WASM
Tags: p5, webassembly, solidjs, rust
Published: 2023-05-08 06:08:39

## Story Time

In 2018, a professor at the Uni asked me to build a series of computer science games; he was looking for a very visual way to show students how the solution algorithms of [NP problems](https://en.wikipedia.org/wiki/NP_(complexity)) (like the Knapsack Problem, Tower of Hanoi, Tic-Tac-Toe, etc.) behave and grow with their inputs.

![Tower of Hanoi Animation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/60ltbfz5s9nm9ejj07bf.gif)

[Tower of Hanoi](https://en.wikipedia.org/wiki/Tower_of_Hanoi) is a good exercise when students are getting started with recursion and vectors. The pegs are usually fixed at 3, so it is easy to define the base case, and the only variable is the number of disks. It is worth noting that there are other more efficient approaches, such as The Binary solution or the Gray-code solution, but this was a Complexity course and we wanted to show how exponential time can break your computer while keeping it as minimal as possible.

## Vanilla JS Implementation

![Vanilla JS Implementation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9jkliqf9hskgr3dcvuzd.png)

There was only one design requirement: to show the animated solutions of the problems in a web browser. At that time I was familiar with HTML5 but not with any modern UI frameworks. Frankly, I couldn't imagine myself rendering objects from scratch in a plain HTML canvas. There had to be something out there that had already invented that wheel, and there was.

I found [P5.js](https://p5js.org/), it is sort of the JS version of [Processing](https://processing.org/) and it has everything I was looking for, a complete API for rendering, painting images and text, calling DOM elements and much more.

The main core of the animation system was the `draw` function provided by P5. It works as an infinite loop, so if we want to show the disks moving from `x1, y1` to `x2, y2`, we have to update the current position `x += speed y += speed` where `0 < speed < 120`. There are two types of motion, vertical and horizontal. An example of the former is:

{% embed https://gist.github.com/sjdonado/7bc69d063192a725552d4fd28ac103be %}

Note that the `refreshCanvas` function refreshes the canvas and redraws the towers filled by the disks, but not the one being animated.

You may wonder how the disks know where to move, do they move at the same time as the Hanoi calculations? That would be cool, but unfortunately they don't. We are limited by the recursive algorithm, so we have to wait until all calculations are done (until the call stack is empty).

Therefore, the `draw` function constantly checks if the array of moves `[towerFrom:towerTo, ...]` generated by `recursiveHanoi` is not empty. If it is, the animation starts.

{% embed https://gist.github.com/sjdonado/f4760799c6eb2af9d9d0e12413aa0eab %}

`recursiveHanoi` did the job, but it was very inefficient: it couldn't handle more than 14 disks (16K steps). The root cause was not in the algorithm itself, but in its execution in the V8 interpreter. Anyway, the same recursive function in C++ could run perfectly for more than 20 disks (aprox 16M of steps). So, running compiled bytecode in the browser was clearly the next step.

## wasm-pack

After four years, I found some time to pay that deb-tech (yes, quite a long time, eh). To make it fun I rewrote everything from scratch in SolidJS, which went smooth thanks to this amazing library [p5js-wrapper](https://www.npmjs.com/package/p5js-wrapper). For WASM, C++ is still a good choice, but what about Rust? I did some research and found [wasm-pack](https://github.com/rustwasm/wasm-pack). A few lines in the `cargo.toml` file and we were ready to generate compiled + ready to import bytecode!

![wasm-pack output](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j5sg6n8rehm3s1pegu66.gif)

Let's dive into the configuration:
- The `crate-type` is set to indicate that the crate will be compiled as a dynamic library: `wasm-bindgen`.
- `gloo-utils` and `serde` are included separately to avoid circular dependencies ([history](https://rustwasm.github.io/wasm-bindgen/reference/arbitrary-data-with-serde.html?highlight=serde#history)).

{% embed https://gist.github.com/sjdonado/ba4800934c52c58264869c3aa78eab40 %}

Once the configuration is ready, we run `wasm-pack build -d wasm --no-typescript` to compile. There is no advantage in generating ts files because we won't use those definitions since the `get_moves` function is gonna be called using a Web Worker.

Then, to make the `wasm` folder accessible to the solid app, we need to update the `vite.config.js` file following the recommended setup from [vite-plugin-wasm](https://github.com/Menci/vite-plugin-wasm):

{% embed https://gist.github.com/sjdonado/2715229d6e68885507cf45b4f9044230 %}

The compiled output is now accessible as follows:
{% embed https://gist.github.com/sjdonado/d4e8d67b248b460e69f0d35db89d25f2 %}

But wait a second, we haven't talked about this function yet, and why do we need a Web Worker? Let's move on to the final implementation.

## Hanoi Algorithm in Rust

The tricky part of writing WASM code is how to interact with the outside world (I/O operations). Fortunately, our function is quite small, its conditions are mapped as follows:
1. The function takes a `Number -> i32` argument: The number of disks.
2. The function returns an array of strings serialised by the `serde_json` crate (which allows you to convert a Rust data structure that implements the `serde::Serialize` trait to a `serde_json::Value` type, in this case a `JsValue`).

And that's it, inside the public fn, we can use regular Rust types like `Vect`.

{% embed https://gist.github.com/sjdonado/b4f3ec5f1de30cb082ee48d0477d32b4 %}

## Web Worker

As mentioned above, the number of disks is exponentially related to the number of steps required in the solution. 20 disks are about 1M, but 24 are more than 16M (which is quite a lot 😰). In fact, the execution time of the recursive function exceeds the Doherty threshold (300ms). So, it becomes mandatory to execute it inside a non-blocking thread, for which we can use the Web Workers API.

A new `.js` file must be created for the worker anywhere in the `src` folder.

{% embed https://gist.github.com/sjdonado/46f2948ffe7c0139edc3d600e252cd3b %}

Then, since the worker instance has nothing to do with the `solid` component lifecycle, we can instance it outside.

{% embed https://gist.github.com/sjdonado/fa411f567c13aec65319b178d77c8270 %}

Finally, when the user clicks on the play button, the async function is called:

{% embed https://gist.github.com/sjdonado/359efaaacd32c6a674d131d4eb57ebae %}

## In Summary

NP problems are highly CPU-intensive, and `wasm-pack` makes it easier to reduce the execution time. In addition, wrapping these operations in a Web Worker improves the user experience.

A picture is worth a thousand words: for 20 disks the Vanilla JS implementation takes more than `312000ms`, while Rust does it in under `200ms` (tested on a Macbook Air M2).

| Vanilla JS | WASM (Rust) |
| ------ | --- |
| ![20 disks execution time - JS implementation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c70vx9b6ulzndq9w2aro.png) | ![20 disks execution time - WASM](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6gic9o198fj17aakii8q.png) |

Source code available on Github:
{% embed https://github.com/sjdonado/cs-games %}

---

That's all I have for you today. Check out my website https://sjdonado.de.

Feedback is more than welcome, drop me a line in the comments section 🙂.

![gif](https://media.giphy.com/media/12noFudALzfIynHuUp/giphy.gif)