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 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.
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:
If we have enough points stop.
Compute a random position (x, y) in [0, width; 0, height].
Read the pixel value at (x, y) in the input image, normalize it to [0, 1] and
Compute a random brightness value between [0, 1].
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.
For each Voronoi cell move its central point to the darkest area.
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:
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.
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.
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
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.