Dynamic Step Distance Transforms

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration explores various ways of measuring the distance of a cell from a set of initial cells. Each cell stores a distance and a color (black or white), and these values propagate out from the initial set. The color of each cell is updated based on the colors of the neighboring cells at smaller distances. For example, the color might be set to white if the number of white, smaller neighbors is 0 or 2; this is totalistic color rule 1010000002=320. Distances between cells are measured by a variation of the taxicab metric: as the sum of distance steps along a connected path, with the individual steps chosen by taking the corresponding horizontal, vertical, or diagonal entry from one of the two sets of 3x3 values shown. The color of the cell is used to choose one of the two sets. Toggle the distance steps, then use the slider to change their values.

Contributed by: Richard Scott (March 2011)
Open content licensed under CC BY-NC-SA



Several of the snapshots and bookmarks show approximately circular patterns. Other snapshots show snowflake-like shapes, rectangular or hexagonal, and patterns that operate on two scales, such as the "bow tie" example.

The statistics displayed under the images include two ways of measuring the circularity: the percentage variation in the radius and the number of sides of the polygon with the same radial variation.

The "symmetric" checkbox (checked) means that the initial cells are set to 1 (white) and surrounded by zeros (black). When unchecked, the right and diagonal lower-left values are also set to 1. Try making the bow tie or "least circular" bookmarks symmetric.

Internally the color is saved as the least significant bit of the distance, which is why the distance steps are even numbers.

The smaller neighbor counts image has a value at each cell in the range 0-8, equal to the number of neighbors with smaller distances. Closely spaced parallel white lines radiating outwards in this image are caused by distance contours with a fine sawtooth pattern, and always seem to indicate circularity generation or smoothing.

For example, the approximately circular rule 416 (Snapshot 2) with size set to the maximum (wait a few seconds) shows this, as does Snapshot 1. The most circular-appearing rule (20-sided polygon bookmark) shows a more uniform pattern; at large scale it can be seen to be a polygon without much smoothing. At a size of approximately 1000, the slight instability on the diagonals blows up and the circle grows four ears.

The rotationally symmetric rules are set up by taking the pattern of smaller neighbors as digits, cyclically rotating to a minimum position, then applying a rule to the first three or four color bits, taken in clockwise order from that position.

The hexagonal rules (rule type 6) use the two least significant bits for the color (black/white) and to simulate the hexagonal neighborhood by switching the six neighbors on alternate rows. Rule type 9, where the rule counts smaller neighbors (instead of smaller white neighbors), can achieve a similar effect. For example, try rule 348 with white distance steps (clockwise from top left) = {2, 2, 2, 100, 2, 2, 2, 100} and black distance steps={0, 198, 0, 0, 0, 198, 0, 0}.

Other growth rules (A New Kind of Science, p. 928) can be simulated by setting the black steps to a large value (or to 0, meaning ignore this neighbor), so that growth occurs first for smaller (white) steps.

The worm rules (rule type 7) turn left or right at each step depending on the color, producing tightly twisting or spiralling patterns with long path lengths. The path length is the longest series of decreasing distances back to the start.

With random selection of the color (rule type 8) it is interesting to vary the proportion of white/black and to compare the result with patterns generated by a color rule with the same percentage of white cells.

These dynamic step distance transforms can be defined more generally as cellular automata on directed acyclic networks on a grid. As with other kinds of distance transforms (fixed step or Euclidean), cells can be updated in parallel or sequentially in any order, with the same end result, although by updating in order of increasing distance, each cell need only be updated once.

They can be useful for image analysis and for modeling patterns where growth occurs along a front that sweeps across an area, leaving a fixed pattern behind. Examples include the time evolution of 1D cellular automata, and more general cases where the network connections and shape of the front are generated dynamically.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.