Taking a Point for a Walk: Pattern Formation with Self-Interacting Curves

Year: 2014 Authors: David Chappell

Core claim

Self-interacting curve rules can produce visually coherent, repeating, and mutable 2D patterns from a single walk.

Topics

generative design, self-avoiding walks, pattern formation, mutation rate

Domains

random walks, geometry of curves, Brownian motion, self-avoiding walks, generative art, 2D design, pattern making, visual coherence

Methods

random-curvature walk, antennae collision detection, self-following rule, barrier constraints

Media

Processing, smooth curves, 2D rendered drawings

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Proceedings of Bridges 2014: Mathematics, Music, Art, Architecture, Culture

Taking a Point for a Walk: Pattern Formation with Self-Interacting Curves

David Chappell Department of Math, Physics and Computer Science University of La Verne, La Verne, CA, USA dchappell@laverne.edu

Abstract

I present a method of generating organic, 2D designs using self-avoiding, random walks. “Self-following” rules are introduced that produce repeating patterns that evolve and mutate as the walk progresses. The rate at which mutations occur influences the degree of organization and coherence in the final design.

Introduction

The Swiss-German painter, Paul Klee, famously remarked that “A line is a dot that went for a walk.” This paper asks the question: what happens when the perambulating dot chooses not to cross its own path? What types of patterns might emerge? Self-avoiding walks (SAWs) are those in which the dot cannot visit the same location more than once. In this case, a dot that encounters its path must either swerve to avoid it or come to a stop. Self-avoiding walks have recently received attention in the physics and chemistry literature because of their application to protein folding and other polymer-related problems [3]. While most SAW studies have been implemented on discrete lattices in order to utilize results from combinatorics [5], I focus on walks on ${\mathbb{R}}^2$ because I’m interested in generating 2D designs using smooth curves.

Simple self-avoiding walks may be constructed from two rules. The first rule describes the behavior of the walk when the dot or particle is not in imminent danger of crossing its path. This motion is generally taken to be a random walk with the provision that the particle cannot double back on itself. The second rule describes the behavior of the particle when it encounters its path. This paper explores how different self-interaction rules affect the variations and visual coherence of the resulting curve. Because I am interested in creating drawings with smooth curves, I first introduce an unconventional random walk in which the curvature (rather than the direction) of the path undergoes a sequence of random perturbations. Finally, self-avoiding and “self-following” rules are introduced to explore designs with repeating forms that exhibit variations and recurrent “defects.” It should be note that systems of “walking particles” have been previously investigated that exhibit emergent and self-organized behaviors [1, 4]. Here, I present the dynamics of a single walk to explore the tension between the absolute, universal qualities of rigid symmetry and repetition, and organic, “playful” forms that possess unique, quirky and individualistic qualities.

Random-Curvature Walks

Let the arc length along the curve be $s$ and the tangential angle of the curve relative to the $x$ axis be $\theta$ . I define a random-curvature walk (RCW) as one in which the curvature $\kappa (s)=d\theta /ds$ undergoes a random walk. In other words, the curvature experiences a sequence of random jumps according to $\kappa (s_{i+1})=\kappa (s_i)+{\kappa }_0{X}_i$ , where $X_i$ is a stochastic variable that returns $+1$ and $-1$ with equal probability and ${\kappa }_0$ is a free parameter that sets the magnitude of the curvature jumps. In practice I choose a large number of stochastic steps and a small value of ${\kappa }_0$ so that the evolution of the curvature approximates a continuous Wiener process (i.e. Brownian

Chappell

Figure 1: Random-curvature walk. The black dot marks the start of the walk.

Figure 2: Self-avoiding walk. The black dot marks the start of the walk.

motion). Once the curvature $\kappa (s)$ is specified, the Cartesian coordinates of the curve may be found through integration:

Figure 1 shows a random-curvature walk with 2000 steps. The random-curvature walk spends most of its time in compact, tightly wound structures that have large curvatures. It provides a useful foundation for developing the self-avoiding and self-following walks presented in the following sections.

The path in Figure 1 is shaded on its right side as the walk progresses, which renders clockwise loops dark and counter-clockwise loops light with a dark halo. The shading direction is chosen based on aesthetic considerations. The curves were constructed and rendered in Processing.

Self-Avoiding Walks

To generate a self-avoiding curve, I place “antennae” on the moving point that sense when the path is about to be crossed. Figure 3 shows the geometry. If the left antenna crosses the path, then the point executes a $180^{\circ }$ reversing turn to the right. If the right antenna crosses the path, then it reverses direction by turning to the left. Reversing turns are followed to completion and are not interrupted or modified if one of the antennae strikes the curve again, although a second set of antennae described below can override the turn. The radius and angle of the reversing turn are each held constant to provide a unifying visual motif throughout the

(a)

(b)

(c)

(d)

Figure 3: Schematic showing the “antennae” used in the self-avoidance procedure. (a) The point curves to the left. (b) The left antenna makes contact with its path. (c) After contact, a $180^{\circ }$ reversing turn to the right is executed. (d) Same as (c) except the shorter override antennae are shown.

338

Taking a Point for a Walk: Pattern Formation with Self-Interacting Curves

Figure 4: Self-following walk with a moderate mutation rate $(\eta =0.1)$ .

Figure 5: Self-following walk with infrequent mutations $(\eta =0.8)$ .

design. The walk is terminated when the self-avoiding rule fails and the point collides with its path. An example of a self-avoiding walk is shown in Figure 2. The small, closed loop toward the right of the figure shows an example of the path becoming trapped and colliding with itself after executing two $180^{\circ }$ turns. The walks in Figures 4 and 6 (which are discussed below) terminate when the walker becomes trapped, while Figures 5 and 7 show walks that are still progressing. In all figures, the small black dot represents the starting location of the walk.

In order to reduce the likelihood of the walk becoming trapped, the point is given a second set of smaller antennae (see Figure 3d) that can override the longer antennae when more immediate dangers are detected. For example, if the walker is executing a reversing turn to the left and the left overriding antenna touches the path, then a new reversing turn to the right is initiated, overriding the original turn. This new rule is found to greatly extend the life of the walking point. It should be noted that infinite SAWs that are never trapped have been developed [2], but the algorithms only apply to walks on lattices.

On each step of a SAW, the antennae must search the path for possible collisions. In an exhaustive search, the number of computations required to generate a SAW with $N$ steps scales as $N^2$ . A more computationally efficient approach stores the step positions in a linked list that is indexed on a spatial grid. Because the density of points remains approximately constant as the curve grows, each antenna only has to search through a fixed (non-growing) number of points $n_{search}$ on each step. Thus, the number of computations required to generate the SAW scales as $n_{search}N$ . Because the number of steps in a complex curve can exceed $10^5$ , and n_{search} < 100 , this method can increase the computational efficiency by > 10^3 compared to an exhaustive $N^2$ search.

Self-Following Walks

A common tactic for creating visual interest and unity in 2D designs is the use of repetition. I extend the self-avoiding walk to include a “self-following” rule as a means of generating repeating, correlated forms. The method may be summarized as follows. If the SAW particle wanders within a prescribed distance $d$ of its old path, it will attempt to align with and parallel the motion of the path, thereby mimicking the curves of its past motion. Let $s$ be the arc-length coordinate of the current point and let the starting position of the path be $s=0$ . We search for the point $s^{\prime }$ that is closest to $s$ on the interval $(0,s-s_d)$ , where the offset $s_d$ is

Chappell

Figure 6: Self-following walk with frequent mutations $(\eta =0.03)$ .

Figure 7: Self-following walk constrained to avoid a “U”-shaped barrier $(\eta =0.8)$ .

introduced to prevent the point from aligning with itself. The tangential angle of the particle on its next step will be $\theta (s+\Delta s)=(1-\eta ){\theta }_{RC}+\eta (\theta (s^{\prime })+\varphi )$ , where ${\theta }_{RC}$ is the tangential angle produced by random-curvature motion, $\varphi =0$ or $\pi$ depending on whether the point follows the path “upstream” or “downstream,” and the parameter $\eta \in [0,1]$ controls the contribution of random motions. When $\eta =0$ , the point follows a random-curvature walk and is not influenced by the presence of its path. When $\eta =1$ , the point is “pinned” to the curve it is following. Figures 4-7 show examples of self-following curves with different $\eta$ values.

Because this simple following technique is subject to instabilities (which have not been investigated in detail), irregularities in the path become amplified with each replication. Each pass of the walk is an imperfect copy of the previous pass (e.g. see Figure 4). The instabilities generate spatial complexity that produce more visually interesting designs. Two types of “mutations” or “defects” can arise: (1) the antennae can swing toward the previous pass of the walk, make contact with it, and initiate a reversing turn and (2) the walker can wander out of range of the self-following mechanism and return to a purely random walk. These irregularities and defects give the resulting patterns their quirky and unique character.

Finally, it should be noted that the patterns may be shaped by including barriers or obstacles that the antennae can “sense”. In Figure 7, a walking point is placed at the bottom of a “U”-shaped barrier. The point snakes its way out of the “corral” and returns to a more regular, “shell-like” pattern similar to that seen in Figure 5. By strategically constructing barriers the self-avoiding and self-following walks may be sculpted to produce diverse 2D designs.

References

[1] M. Annunziato, “The Nagual experiment”, (1998) Proceedings 1998 International Conference on Generative Art (ed. C. Soddu), pp. 241-251. [2] K. Kremer and J. W. Lyklema, “Infinitely Growing Self-Avoiding Walk”, Phys. Rev. Lett., 54 (1985), pp. 267–269. [3] N. Madras and G. Slade, The Self-Avoiding Walk, (1993), BirkHauser: Boston. [4] J. McCormack, “Creative ecosystems,” in Computers and Creativity, (eds. J. McCormack and M. d’Inverno), Springer, Heidelberg, pp. 39-60. [5] C. Vanderzande, Lattice Models of Polymers, (1998), Cambridge University Press: New York.