API Design decisions behind Lindenmayer in Swift

Procedural generation of art is fascinating to me. The scope of efforts that fall into the bucket of procedural generation is huge. Quite a lot of what you find is either focused on art or video games. Within procedural generation, there is a topic that really caught my eye, I think primarily because it wasn’t just about art or games, but rather botany.

I learned of L-systems, also known as Lindenmayer systems, quite some time ago, and knew that you could use them to generate interesting fractal images. L-systems were devised by Aristid Lindenmayer as a formal means to describe and model plant growth. Much of the background was printed in 1990 in the book The Algorithmic Beauty of Plants. The book is currently available from the site Algorithmic Botany in PDF form (which I linked above). I find it fascinating, and after skimming through it a couple of times, I started to look for what code might be available that I could use to play with it. I pretty quickly found the Swift Playground ‘lindenmayer‘, created by Henri Normak. That was neat, but I wanted to go beyond what it could do to re-generate some of the more complex examples from the book.

Fast forward a number of months, and I’ve now published an early release of a swift library that you can use to generate, and render, Lindenmayer systems. The library is available as a swift package – meaning it is intended to be used on Apple platforms (iOS macOS, etc) and quite a lot of it (the core) could be used by swift on Linux without a lot of trouble. I’m hosting the project, and the source for it, on Github at https://github.com/heckj/lindenmayer. The current release (0.7.0) is not at all finalized, but has a lot of the features that I wanted to use: contextual rules, parametric symbols, as well as image and 3D model representations of the L-systems.

To tease a bit of what it can do, let me share some examples from the book, and then my examples of the same L-systems, ported to using the library I created:

Rendered trees from The Algorithmic Beauty of Plants, page 59
The ported L-systems using the original parameters as the book, rendered in 3D

The rendered result is really close – but not quite there. Part of it stems from a the representation of a specific symbol in the original (‘$’), and my interpretation of what that does when render the state of an evolved L-System in three dimensions. It could just as easily be a mistake in how I interpreted and ported the original L-systems that were published in the book. You can really see the differences in the second set of trees that I tried to create from the book:

I debated how I wanted to create this library, and in the end landed on doing something was would push me as a developer, forcing me to more deeply understand the swift programming language as well as how to design APIs with it. The result isn’t an interpreted thing, but something that closely uses the swift compiler and tries to match to leveraging the type safety. If you want to make an L-system with this library, you’re doing it in the swift programming language.

The core of an L-system is a set of modules – an abstract representation – and a set of rules that you apply to these modules. You start with an initial set of modules – maybe just one – and on each ‘iteration’ of an L-system, you go through the entire list of all the existing modules, and apply a set of rules. The rules are set up to match a module, or a specific sequence of modules, and if they do – then you replace the current module in its current location within the sequence, with whatever the set of modules the rule returns. Typically only one rule applies, but in any case I set it up so that tries all the rules in order and only uses the first rule that reports it matches. If no rules match, the symbol is ignored and left in place.

A capability that I wanted to enable was implementing a parametric L-system. This means that the symbols aren’t just one-character things that you interpret, but objects (called modules) that can have parameters. Those parameters can be read, and used to determine if a rule should be chosen, or what the rule produces. I chose to use Swift closures for constructing the rules, the idea being that you could define a module as a Swift struct (with or without properties), evaluate if a rule applied to a module (or set of modules) by either their type, or by their type and properties. If choose, then also making the types with any properties available to compute values and choose what modules should be the replacements. My thinking was anything you could compute using Swift was more immediately available by using a closure, and had the benefit of being type-checked by the compiler.

To make this idea more concrete, take a look through a variation of the system that created the tree images above:

    struct Trunk: Module {
        public var name = "A"

        let growthDistance: Double
        let diameter: Double
    }

    struct MainBranch: Module {
        public var name = "B"

        let growthDistance: Double
        let diameter: Double
    }

    struct SecondaryBranch: Module {
        public var name = "C"

        let growthDistance: Double
        let diameter: Double
    }

    struct StaticTrunk: Module {
        public var name = "A°"
        public var render3D: ThreeDRenderCmd {
            RenderCommand.Cylinder(
                length: growthDistance,
                radius: diameter / 2,
                color: ColorRepresentation(red: 0.7, green: 0.3, blue: 0.1, alpha: 0.95)
            )
        }

        let growthDistance: Double
        let diameter: Double
    }

    public struct Definitions: Codable, Equatable {
        var contractionRatioForTrunk: Double = 0.9 /* Contraction ratio for the trunk */
        var contractionRatioForBranch: Double = 0.6 /* Contraction ratio for branches */
        var branchAngle: Double = 45 /* Branching angle from the trunk */
        var lateralBranchAngle: Double = 45 /* Branching angle for lateral axes */
        var divergence: Double = 137.5 /* Divergence angle */
        var widthContraction: Double = 0.707 /* Width contraction ratio */
        var trunklength: Double = 10.0
        var trunkdiameter: Double = 1.0

        init(r1: Double = 0.9,
             r2: Double = 0.6,
             a0: Double = 45,
             a2: Double = 45)
        {
            contractionRatioForTrunk = r1
            contractionRatioForBranch = r2
            branchAngle = a0
            lateralBranchAngle = a2
        }
    }

    static let defines = Definitions()
    public static let figure2_6A = defines
    public static let figure2_6B = Definitions(r1: 0.9, r2: 0.9, a0: 45, a2: 45)
    public static let figure2_6C = Definitions(r1: 0.9, r2: 0.8, a0: 45, a2: 45)
    public static let figure2_6D = Definitions(r1: 0.9, r2: 0.7, a0: 30, a2: -30)

    public static var monopodialTree = Lindenmayer.withDefines(
        [Trunk(growthDistance: defines.trunklength, diameter: defines.trunkdiameter)],
        prng: PRNG(seed: 42),
        parameters: defines
    )
    .rewriteWithParams(directContext: Trunk.self) { trunk, params in

        // original: !(w) F(s) [ &(a0) B(s * r2, w * wr) ] /(d) A(s * r1, w * wr)
        // Conversion:
        // s -> trunk.growthDistance, w -> trunk.diameter
        // !(w) F(s) => reduce width of pen, then draw the line forward a distance of 's'
        //   this is covered by returning a StaticTrunk that doesn't continue to evolve
        // [ &(a0) B(s * r2, w * wr) ] /(d)
        //   => branch, pitch down by a0 degrees, then grow a B branch (s = s * r2, w = w * wr)
        //      then end the branch, and yaw around by d°
        [
            StaticTrunk(growthDistance: trunk.growthDistance, diameter: trunk.diameter),
            Modules.Branch(),
            Modules.PitchDown(angle: params.branchAngle),
            MainBranch(growthDistance: trunk.growthDistance * params.contractionRatioForBranch,
                       diameter: trunk.diameter * params.widthContraction),
            Modules.EndBranch(),
            Modules.TurnLeft(angle: params.divergence),
            Trunk(growthDistance: trunk.growthDistance * params.contractionRatioForTrunk,
                  diameter: trunk.diameter * params.widthContraction),
        ]
    }
    .rewriteWithParams(directContext: MainBranch.self) { branch, params in
        // Original P2: B(s, w) -> !(w) F(s) [ -(a2) @V C(s * r2, w * wr) ] C(s * r1, w * wr)
        // !(w) F(s) - Static Main Branch
        [
            StaticTrunk(growthDistance: branch.growthDistance, diameter: branch.diameter),
            Modules.Branch(),

            Modules.RollLeft(angle: params.lateralBranchAngle),
            Modules.LevelOut(),
            SecondaryBranch(growthDistance: branch.growthDistance * params.contractionRatioForBranch,
                            diameter: branch.diameter * params.widthContraction),

            Modules.EndBranch(),

            SecondaryBranch(growthDistance: branch.growthDistance * params.contractionRatioForTrunk,
                            diameter: branch.diameter * params.widthContraction),
        ]
    }
    .rewriteWithParams(directContext: SecondaryBranch.self) { branch, params in
        // Original: P3: C(s, w) -> !(w) F(s) [ +(a2) @V B(s * r2, w * wr) ] B(s * r1, w * wr)
        [
            StaticTrunk(growthDistance: branch.growthDistance, diameter: branch.diameter),
            Modules.Branch(),

            Modules.RollRight(angle: params.branchAngle),
            Modules.LevelOut(),

            MainBranch(growthDistance: branch.growthDistance * params.contractionRatioForBranch,
                       diameter: branch.diameter * params.widthContraction),

            Modules.EndBranch(),
            MainBranch(growthDistance: branch.growthDistance * params.contractionRatioForTrunk,
                       diameter: branch.diameter * params.widthContraction),
        ]
    }

As a side note, the library uses both protocols as types (also known as existential types) and generic types – both for generating the L-systems and the rules within an L-system. Enabling that made for some tedious development work, as there’s not a lot of “meta-programming” capabilities with the Swift language today. That said, I’m happy with the results as they stand right now. I’m still debating if I would get any benefit from leveraging the Swift DSL capabilities with result builders. I’ve watched and re-watched Becca Dax’s talk from WWDC 21: Write a DSL in Swift using result builders at least four times, but so far I haven’t convinced myself it’s a win over the factory methods I’ve currently enabled.

The 2D representation draws into SwiftUI’s canvas (which is pretty much a clone of the stuff that draws into a CoreGraphics context that Henri Normak shared in his playground), and the 3D representation work generates up a SceneKit scene, and there’s so much more to go!

I love the idea of being able to use this to generate images or 3D models, and explore the variety of things you can create with L-systems. A huge shout-out to Dr. Kate Compton, who’s writing over many years has enabled me to explore a variety of things within procedural generation. I’m still working up to being able to “generate a 1000 bowls of oatmeal“, at least easily. One of the recent additions I enabled was randomization within the library. I included a seedable pseudo-random number generator, so you can make things deterministic if you want.

This was the first real effort I’ve taken to generating 3D scenes, so I may need to step back and re-think through the whole renderer that generates SceneKit scenes, and I haven’t yet even begun to explore how I might enable the same with RealityKit. The 2D version was relatively straight-forward, but when you get into 3D there’s all sorts of bizarre complications of rotations to deal with – and while I have something basically working, it’s not intuitive to understand – or debug.

I have a number of ideas for how I might continue to grow this – but if you find it interesting, feel free to try it out. I’ve enabled discussions on the Github repo, or you can track me down on twitter pretty easily, if you have questions or suggestions. I’m rather fixated on the issue that what I’m generating doesn’t exactly match the results from the book, and what I interpreted incorrectly, but I think the gist of what this is and does is reasonably solid. If you come to play, don’t be surprised if the examples that I have built into the library change as I iterate on getting the results to match more closely to the originally published work.

I dearly wish that the Swift Playgrounds version 4 (the update that just came this winter) out allowed for Swift packages to be used within a playground. Alas, that doesn’t appear to be the case – but you can still experiment with this library using Swift Playgrounds by including it in an App. I’ll have to explore how to publish that as an example… another thing for the TO-DO list for the project!

Published by heckj

Joe has broad software engineering development and management experience, from startups to large companies. Joe works on projects ranging from mobile to multi-cloud distributed systems, has set up and led engineering teams and processes, as well as managing and running services. Joe also contributes and collaborates with a wide variety of open source projects, and writes online at https://rhonabwy.com/.

%d bloggers like this: