Eight years ago (ouch …) I published a little tool to interactively cherry-pick commits from a branch. It’s still useful to me but ever so often I forget about the urwid dependency when re-installing it. Yada yada, so of course team Rewrite-in-Rust strikes again which means I can simply drop the statically linked binary into $PATH and not have to worry about Python and ncurses dependencies anymore.

And for the price of one you now get even two tools. Since I have to create a lot of feature, bugfix and whatnot branches, deleting them becomes painful as well even with tab-completion and fzf integration. So, in a similar vein to git pick the git prune-branches (git prune is a plumbing command to remove unreachable objects from the Git database) allows you to select a bunch of branches interactively and delete them in one go.

A friend of mine asked me to join him in a small side project that combines both art, programming and hardware. The latter is still in the design phase, so let me tell you about the art and programming part first. The principal idea is to generate art (random, really generative or from existing data) and let it being drawn in real life by a machine. We wanted to start simple and just process existing bitmap images and turn them into nice looking paths that can be drawn by the “machine”.

My initial idea was to generate a path from a random walk with a probability density that matches the surrounding pixel density of the current position. While that works in a way, the result is hardly legible. After some researching we came to the conclusion to do what in general is known as TSP art.

TSP art

TSP as in the Travelling Salesman Problem is a two-step problem. In a first step, for given number of points, we find a set of points that approximates the pixel density of the input image. In a second step, we determine a path that connects all points exactly once.

Sampling points

Because (photographic) image formation is a stochastic process one can do the reverse and use the brightness of each input image pixel as the probability that light hit the sensor. Since we want to have more points for darker areas, we have to use the inverse though. That and simple rejection sampling leads us to a basic point sampling algorithm:

1. If we have enough points stop.
2. Compute a random position (x, y) in [0, width; 0, height].
3. Read the pixel value at (x, y) in the input image, normalize it to [0, 1] and invert it.
4. Compute a random brightness value between [0, 1].
5. If the random brightness value is larger than the pixel value accept it.

This works wonderfully but due to the stochastic nature requires many samples which is detrimental to the path finding step. In the following image you can see the result for 10000 and 100000 points:

Luckily there are various approaches to approximate the density with less points the same way a human would draw an image using a pencil.

Weighted Voronoi stippling

Weighted Voronoi Stippling is such an approach. The basic idea in layman’s terms is as follows:

1. Sample a set of points randomly or use the algorithm from above.
2. Compute the Voronoi diagram for the point set.
3. For each Voronoi cell move its central point to the darkest area.
4. Continue until you are satisfied.

The following image shows you the result for 10000 and 30000 points and 5 as well as 100 iterations:

Note though that there are no major improvements past the 50 iterations mark.

Solving the Travelling Salesman Problem

Now that we have a good set of points we want to connect them and ideally visit each point only once. Sounds familiar? Yes, it’s the infamous Travelling Salesman Problem which is NP-complete, meaning you won’t find the best solution in a reasonable amount of time for a larger number of points. So again a bit of research and the most straightforward algorithm is again two-fold, first we compute an initial path using the Nearest Neighbor algorithm and then iteratively improve that path using the 2-opt algorithm. Here are two results for 10000 and 30000 points respectively:

inkdrop

All of the images have generated by a small Rust tool called inkdrop. It is split into a core library that implements the algorithms as well as some data structures and two binaries to drive them via command line or a GTK 4 user interface. The primary output data format is SVG which is super simple and matches the problem very well. To generate Voronoi diagrams I used the wonderful Voronator library which wraps the Delaunator library I tried to use before but gave me too many headaches.

Long-time readers will know that GTK is nothing new for me but GTK 4 is. And I must admit, I love the on-going work of the Gtk-rs team that provides usable GTK 4 bindings at this early stage as well as the GTK team itself. GTK 4 finally improves quite a few pain points for me and surprised me positively with the addition of layout managers and declarative property bindings. This allows one to write even less code and declare more UI facts in the builder file itself. Neat.

So, here is part one of our generative art adventure.

Update: The Rust bindings to GTK4 are now stable. Yay!

Stoneshard is a turn-based RPG with nice 2D pixel art and an elaborate role-playing system. Unfortunately, the Linux support is a bit messy and if you happen to play it on Ubuntu 20.04, it will tell you it cannot find libcrypto.so.1.0.0. Common advice is to symlink libcrypto.so.1.1.0 however that is neither a good idea nor even necessary because the game does not even depend on it. Hence, the cleaner way is just to patch the game binary, for example using patchelf:

$ git clone https://github.com/NixOS/patchelf && cd patchelf
$ ./bootstrap.sh && ./configure && make && sudo make install
$ patchelf --remove-needed libcrypto.so.1.0.0 <path-to-stoneshard>/game/StoneShard
$ patchelf --remove-needed libssl.so.1.0.0 <path-to-stoneshard>/game/StoneShard

With that done, you can run the game just fine. I still wonder what the crappy build system of that game is doing though …

As we all know public services are often underfunded or public websites more often than not of questionable usability. The waste calendar for the municipality of Karlsruhe is somewhere in between. It is not bad but not of much help for your fellow scavengers who like to re-use thrown away goods. For the past three years, I scraped that site with a small Python script and dumped a CSV file that people could use to plan their hunts. This worked well enough but I always only updated it begrudgingly because I was asked to do it rather than because I wanted to do it.

But I am motivated to hone my programming skills, so I took this little project, rewrote it in Rust, extracted road and date data and dumped everything into a small static site based on Vue and Leaflet.js. So, if you want to schedule your next hunt or find out where to play Pokémon GO in Karlsruhe without being disturbed, here is your chance.

P.S.: thanks Karlsruhe for that splendid API /s

As easily witnessed, content frequency of the blog is at an all-time low. So what’s better than increasing it by writing about switching from Jekyll to Zola? Why, you ask? First, Jekyll is the only reason I have Ruby and gazillion of Jekyll dependencies installed even though I don’t understand a lick of the language. Second, every time there is a Jekyll update, I have to do something about some plugin breakage or live with some new warnings about this and that. Third, considering the application scope of a static site generator, it’s incredibly slow.

Actually, there was no urgency but I read about Zola and was hooked because it’s supposed to be fast (it is, taking a mere 100 ms to re-generate this blog) and it uses the same templating technology I used for splat. I won’t bore you with the conversion details but just want to point out this rewrite script which converts the Jekyll front matter which is written in YAML to TOML which is required by Zola.

All in all it was a straightforward conversion and I hope Zola will backing this blog for the next nine years as Jekyll did in the past.