Arbitrary Alterations

Recently I have been looking for a solution to a particular problem related to my snek data structure. The problem is this:

What if I want to perform a particular action only if a given alteration is applied? Moreover, what if that action depends on changes to the data structure that will not exist until after the alteration has been applied?

A suitable example is a variation of a two-dimensional random walk, with the additional limitation that vertices are not allowed to be too close to any existing vertex. Below is an animation to give you an idea.

Random Walk Animation
Limited random walk animation

One way to implement this is to continuously try to place a new vertex in the vicinity of the previously added vertex. You can keep doing this until you find a free spot, or until you get into a deadlock.

It turns out I had the necessary functionality to solve this all along: custom alterations.

The ability to add your own alterations has been a part of the design plan for snek all along. After a bit of testing I have come to the conclusion that custom alterations are probably the best and most flexible solution to this problem as well.

Below is an example using a snek instance called snk, and the current vertex index w. Also note that the (append-edge? ...) alteration will attempt to create a new edge between an existing vertex and a new point. The important thing to note here is that the point will turn into a snek vertex when the alteration has been applied.

; create custom alteration func
(defun do-append-edge-alt* (snk a)
  ; append edge if it is not too close
  ; to any existing vert
  (if (<= (length
            (verts-in-rad snk
              (append-edge-alt-xy a)
    ; (append-edge-alt ...) returns index of
    ; the added vert. if the alteration is
    ; not applied, it returns nil.
    (aif (do-append-edge-alt snk a)
       ; update if alteration was applied
       (setf w it)))

; override the func that applies
; append edge alterations
(let ((snk (make-snek
             :alts '((append-edge-alt
  ; initial vert at xy
  (setf w (add-vert! snk xy))

  (loop for i from 0 below n do
    (with-snek (snk :zwidth rad)
      ; pick a point near w
      ; w will only be updated if the edge
      ; is applied
        w (add (get-vert snk w)
               (rnd-in-circ rad))
        :rel nil))))

This example extends the existing alteration (append-edge? ...). There is obviously nothing stopping you from implementing completely new alterations. While this might not be a perfect solution, it seems to solve all the challenges I've encountered so far.

  1. In fact I have been thinking about this for a few days. Which is embarrassing for a number of reasons ...
  2. A complete working example can be seen in the repository.
  3. All alterations are now postfixed with ?, to indicate that it may or may not be applied.