Recursive Walks

A friendly nerdsnipe

A generated image of a plant-like structure, similar to a fern, drawn with white pixels on a black background

A friend approached me with a math paper about curves that can be expanded recursively to show self-similar structures at higher levels of recursion. They were continuous lines, like those defined by logo. While the paper focused on drawing and understanding the edges of those, we decided to draw only the visited vertices on a grid (a vertex on a cell, an edge connecting two adjacent cells).

Imagine a creature starting at a random spot on the 2D grid. It can go one step forward (F), turn right (R), or turn left (L). We can give a sequence of moves, for example FFFFFRFFFRFL and it will draw the following path.

A J shaped white trail on a black background

Now, we can take the initial path, and replace every occurrence of R with the same starting string FFFFFRFFFRFL. We'll get this.

The resulting path is FFFFFFFFFRFFFFRFFLFFFFFFFRFFFFRFFLFL.

Again, we can take the result, and apply the same replacement R -> FFFFFRFFFRFL, producing FFFFFFFFFFFFFRFFFFRFFLFFFFFFFFRFFFFRFFLFFLFFFFFFFFFFFRFFFFRFFLFFFFFFFFRFFFFRFFLFFLFL.

A white squiggle on a black background

After 5 replacements it looks like this:

A white squiggle on a black background

This visualization shows more visited cells of the grid with a brighter shade. It's starting to look more interesting and reveals this pattern's macroscopic structure. Repeating this process 10 times looks even more cohesive and organic.

A white squiggle on a black background, looks like two arms of a plant turning inwards

At this point the path is 24,564 steps long.

Each recursive expansion increases the length of the path exponentially (in this case, depends on the exact starting rules), so at 16 it's 1,572,852 steps.

A white squiggle on a black background, looks like two arms of a plant turning inwards

Generating the path is pretty quick, the bottleneck in my implementation is in saving the image because I want to stick to having each cell represented by a pixel.

The farthest I took these rules is 24 recursive replacements, which took a second to generate a path 25,165,812 steps long and about a minute to save a 41 megabyte, 10,244 x 13,327 image. I compressed this one for the web, but you can download the original image here.

A white squiggle on a black background, looks like two arms of a plant turning inwards

All of this comes from these rules: - starting with the path FFFFFRFFFRFL - replace every F with F - replace every R with FFFFRFFFFRFFL (same as starting path) - replace every L with L

Making small changes

Taking the rules we started with and changing the rule for F to LLF, which essentially means "for every F turn back and walk ahead" creates the same shape but more cohesive and geometric.

Plots at 8 and 16 replacements for: - F -> LLF - R -> FFFFRFFFFRFFL - L -> L

A white squiggle on a black background, looks like two arms of a plant turning inwards

Or instead, taking the original rules and swapping F and L (plots for 8 and 11 replacements): - F -> L - R -> FFFFRFFFFRFFL - L -> F

A sig-zag line that looks like two steps going down, flat floor, two steps going up, and the same pattern again mirrored vertically The same shape as above but repeated 4 times instead of 2

And making a small change to that creates a completely different result (plots for 8 and 12 replacements): - F -> L - R -> FFFFRFFFFRFFL - L -> FLFFL

Geometric shape with straight angles that's brighter in the middle

Prints

If you'd like a high quality print of any of these, or a pattern of your own, let me know and I can bring it to the next convention we'll both attend.

Summary

It's easy to nerdsnipe me with stuff like this. I have to get off a train now, so end post.

The code is available here: codeberg repo.

Have fun.

Home