Tower of Hanoi in P5.js + WASM

#p5 #webassembly #solidjs #rust

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 (like the Knapsack Problem, Tower of Hanoi, Tic-Tac-Toe, etc.) behave and grow with their inputs.

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

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, it is sort of the JS version of Processing 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:

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.

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. For WASM, C++ is still a good choice, but what about Rust? I did some research and found wasm-pack. A few lines in the cargo.toml file and we were ready to generate compiled + ready to import bytecode!

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).

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:

The compiled output is now accessible as follows:

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:

The function takes a Number -> i32 argument: The number of disks.
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.

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.

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

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

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).