Procedural art with Rust

I’ve been working on a little procedural art project called trails, inspired by the recent Advent of Code day 10 and a visualisation by ruuddotorg.

Making trails

Since I already had the Advent of Code input and code to find trails, it was relatively straightforward to modify it to produce an SVG image visualising the trails, similar to the Reddit post by ruuddotorg. If you think of a trail as moving through a tilemap, then the trails only move vertically and horizontally and always turn through 90 degrees, and always move in multiples of the tile size (eg if your tile is 32px, then the trail always moves in whole tiles so each move will be a multiple of 32).

This meant that for the first pass I just went through a list of points, and drew SVG lines between the pairs.

Recreating the input

The Advent of Code problem was to find paths starting at 0 and finishing at 9 from a grid of numbers, for example the input

116321
987377

has a path from the top-right 0 to the bottom-left 9, and inputs can have multiple branching trails.

..6321
987...

What I needed to do was to be able to create my own input grids, and make sure they roughly matched the original Advent of Code (AoC) style. Looking at the AoC input, the starting points (0) were roughly uniformly distributed over the grid, ie evenly spread out so there weren’t big empty areas, and there weren’t areas with very dense amounts of starting points.

So if you need to spread things out uniformly over an area, the obvious choice is quadtrees!

Quadtrees!

(I love saying quadtrees, no idea why!) The general idea of a quadtree is to take an area, then split it into quarters. If the quarters are still too big for your needs, then keep splitting into quarters until you have areas around the size you want. You might not always reach your target size due to the size of your original area and integer division etc, so you just check if the next split would be too small. Eg original width and height is 10, target size is 3. After splitting, you have four squares of 5x5. Splitting again would mean each 5x5 square splits into a 3x3 and 2x2 (due to integer division) - 2x2 is smaller than the target size of 3 so you’d stop at 5x5.

This means you have rectangles spread out over your original area, roughly uniformly distributed - seems perfect to use to spread out starting points. In summary, to place starting points the algorithm goes:

1. Split the area into quarters
2. Are the leaf nodes - the smallest area we just split into - around the target size?
3. If not, go to 1
4. If small enough, place starting points

Create trail

Once I had a list of starting points, I just needed to add sequential numbers up to nine from each starting point. For the first pass I used a random walk, but that ended up drawing quite bad trails: newer trails would overwrite older ones so you wouldn’t get many complete trails, and random walks often ended up staying in a very small area which made quite a bad final image.

Starting with an empty grid, with only starting points present, I ended up using a depth-first search:

1. Get neighbours of current point
2. Shuffle neighbours so trails don’t have a biased direction
3. Check neighbours
   • if empty, place the next point
   • if not empty, is it the same as the next point? ie trails can share a point
   • if not empty and not the next number in the sequence, then we’ve reached a dead end so stop

.0........
.1........
.2345.....
....6.....
....789...
..........
...6543...
.987..2...
......10..
..........

The last step is to fill in the remaining empty spaces with random numbers. The nice part of this is that it sometimes adds extra branches to trails to add a bit more variety.

Drawing trail

I used seeded random number generators to draw the trails, so using the same input should always generate the same output. Since seeding is supported by the rand crate, all I really needed to do was make sure I passed the instance of rng around to functions so the same seeded instance was being used.

// create seed and initialise rng with it
let seed = "abc123".to_string();
let mut rng: SmallRng = Seeder::from(&seed).into_rng();

// make sure to pass the seeded instance to functions for repeatable output
input.add_trails(&starting_points, &mut rng);
input.fill(&mut rng);

I used SVG for the image output - SVGs are vector so can be scaled to any size, and it’s really easy to create SVGs from code since they’re just text. Initially I used <line> to connect each point to draw trails:

fn line(start: &Position, end: &Position) -> String {
    format!("<line x1={} y1={} x2={} y2={} />", start.x, start.y, end.x, end.y)
}

This worked, but meant the SVG was very large - trails would have nine lines each, and for larger canvases there could easily be over a hundred trails. In testing, a 45x45 canvas created an SVG that was almost 1mb - very inefficient!

Instead of using <line> for every edge, instead I switched to <path> which can contain mulitple commands - a trail can be drawn in a single path. Paths can also take abbreviated commands where you just pass the total relative horizontal or vertical movement, which meant that multiple moves in the same direction could be combined to reduce the size of the SVG further.

/* original - line for each edge. Moves right 10, down 30 then left 10 */
<line x1="0" y1="0" x2="10" y2="0" />
<line x1="10" y1="0" x2="10" y2="10" />
<line x1="10" y1="10" x2="10" y2="20" />
<line x1="10" y1="20" x2="10" y2="30" />
<line x1="10" y1="30" x2="0" y2="30" />

/* use a path for whole trail - this does exactly the same as above but is more concise */
<path d="M0 0 h10 v10 v10 v10 h-10" />

/* 
    merge path commands - the vertical moves can be collapsed into one command of 30
    instead of three commands of 10
*/
<path d="M0 0 h10 v30 h-10" />

As you can see, this reduces the original from five <line> commands to one much shorter <path> command. Adding this optimisation took the same SVG from 980kb to 61kb - about a 90% reduction in file size by iterating on the first pass approach.

The nice part about using SVG for the output is that it’s text, so in Rust you can implement Display for commands and then just print the output:

struct SvgCommand {
    command: LineCommand,
    distance: i16,
}

impl Display for SvgCommand {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self.command {
            LineCommand::Horizontal => {
                write!(f, "h{}", self.distance).expect("Failed to write command");
            }
            LineCommand::Vertical => {
                write!(f, "v{}", self.distance).expect("Failed to write command");
            }
        }

        Ok(())
    }
}

Stack

The tech stack I used was Rust to generate grids and trails, and Axum for the web api. The web frontend is vanilla JS with Vite as the dev tool, then all deployed using Github Actions.

What I really like about Rust for this sort of project is that Cargo Workspaces make it really easy to take a local library, create a binary to run or test things as well as create a web project for deployment. The really nice thing is that everything in the workspace links to the same local version of the library so I can still update my code as well as the projects which call it.

Initial setup

- binary generating grids and trails

Workspace setup

- workspace root
    - library generating grids and trails
    - binary handling CLI args, calling library
    - web project calling library and providing frontend

This makes turning a quick project into something deployable so quick and easy - I don’t need to publish a library anywhere, and the only setup is to move folders and add to add a Cargo.toml file to the root. This is so much easier than with other languages, and it’s built-in to the Rust toolchain which makes things incredibly simple.

Gotchas

Here’s a few things I ran into which I’m writing down so I can find the answers when I inevitably make the same mistakes in future.

Hashsets don’t have a stable order. I wanted to seed the output so that the same input always generates the same output, but using a hashset to hold the starting points meant that the output was different each time. Instead I switched to using a Vector to hold starting points - really it doesn’t matter if there are duplicate starting points, and the order of vecs is stable.

Supervisor! My server is a small (cheap!) hosted server, and I’m using supervisord to run the Rust web binary. When you change the supervisor config file (eg to change environment variables) then you need to run

supervisor reread
supervisor update

otherwise supervisor will keep using the old config, even if you restart the service. I forget this every time.

Axum was generally quite nice - I’ve been using Actix a lot recently and there are a lot of similarities, especially for a small api server. There were a few things I found odd or a bit painful though - lots of functionality is behind the tower_http crate, so Axum docs tend to just say ‘refer to Tower Http’ without many details, and then you need to understand and configure Tower to get things like static file serving or logging working. This is quite annoying to do rather than having things available or clear out of the box. Nothing was bad, but papercuts like these are just annoying enough to make me want to just continue with Actix rather than pick Axum up more.

The end

In conclusion, Rust was a lot of fun for this kind of experimental project, and Cargo workspaces are an absolutely amazing feature for taking a local project to multiple different projects, like web api and CLI binary.

The project is here if you want to play around with it.