inconvergent

Future Alterations

When I started learning Common Lisp I also started writing a framework for generative art. The first version was named SNEK. The most recent version of this framework is named WEIR.

One of the ideas I wanted to explore was the ability to have a graph (essentially a drawing). Combined with the ability to line up future changes that will be applied to this graph. In WEIR this kind of future change is named an alteration.

symbols
Generative symbols

The main motivation was that this would let you collect a series of alterations, then apply them later. Knowing that you can safely access the current state of the graph because it is currently unaltered. This functionality is made possible with a macro, (weir:with ...), that collects and the applies the alterations.

Another motivation was that this would provide an expressive and simple interface, where the complexity of actually applying the alteration is hidden behind the scenes.

For simple cases this worked well enough, but I quickly realised that I wanted to create (nested) alterations that were dependent on other alterations. Essentially I wanted a dependency graph of futures. In other words, it proved to be far more limited than I had initially imagined.

Implementing this dependency graph seemed rather complicated, so I had mostly discarded it.

Since I made the first version of this functionality, I have only made a few technical improvements to the code that enables it. Beyond that I have largely left it unaltered.

A few days ago I went back and looked at the code, and I suddenly realised how I could quite easily implement the dependency graph.

The implementation isn't that interesting in itself, I assume there are other people who have implemented this kind of dependency resolving more elegantly. However, I thought I'd share an example of what this new functionality allows me to do. Or perhaps, more interestingly, how it to some extent lets me write an algorithm that almost looks like pseudo code.

symbols
Generative symbols

The example below is an iterative algorithm that starts with a single straight line (edge). And then proceeds to select edges at random. Effectively the selected edge is split at the middle, and two new edges are appended at the split, rotated around the middle of the edge.

We assume that we have an initial graph instance, wer, with an initial seed edge. Furthermore the alteration, (add-edge? ...), will only do anything with a certain probability, and if the new edge does not cross any existing edges.

; repeats n times:
; select a random edge, ee, from wer
(with-rnd-edge (wer ee)
  (let* ((vv (get-verts wer ee)) ; positions of edge
         (mid (get-mid vv)) ; midpoint of edge
         (angle (get-rnd-angle)) ; random angle
         (rotated (rotate vv mid angle))) ; rotate vv around mid

    (with (wer %)
      ; delete the selected edge
      (% (ldel-edge? ee))
      ; nev vertex in the middle, named :mid
      (% (add-vert? mid) :mid)
      ; two new verts, rotated relative to
      ;  initial edge, named :r1 and :r2
      (% (add-vert? (first rotated)) :r1)
      (% (add-vert? (second rotated)) :r2)

      ; four new edges from :mid to the
      ; new vertices :r1 and :r2; and the existing
      ; vertices of edge, ee
      ; (:mid :r1) means that this alteration
      ; depends on :mid and :r1
      (% (add-edge? :mid :r1) (:mid :r1))
      (% (add-edge? :mid :r2) (:mid :r2))
      (% (add-edge? :mid (first ee)) (:mid))
      (% (add-edge? :mid (second ee)) (:mid)))))

  1. An alteration is unaware of the current state of the graph; if it happens to be invalid in some way when it is about to be applied, it will be discarded.
  2. For some definition of easy.
  3. You can probably spot a possible flaw here. Depending on how (add-edge? ...) is implemented the intersection test will happen at the time of alteration creation, or at the time of alteration application. My code does the latter, because it works just as well for what I wanted to do. This kind of consideration applies to all possible alterations.