Networks and Space Colonization
*This post reproduces content from Chapter 8 of my doctoral thesis and serves as an introduction to several forthcoming ‘space colonization’ algorithms. The first of these the meander is now available, with some others coming soon!
In Harvard-trained architect Peter Steven’s 1974 book Patterns in Nature, the author proposed that in 2- and 3-dimensional physical spaces, there are only a very limited number of possible configurations of elements, and that consequently nature is forced to reuse the same basic formal strategies in diverse contexts. The variety and diversity we perceive in nature comes not through innovative formal structures, but through topological deformations and hybrid configurations of the limited palette of possible spatial arrangements. (Stevens, 3-4) For example, according to Stevens, in 2D space there are only four strategies to connect a random group of points to each other without any overlap between points and without any redundant connections, i.e. where there is only one possible path between any two random points. He also proposed that these graphs corresponded to four archetypes for pattern formation in nature, each with certain efficiencies and drawbacks. (Stevens 37-48) Some of the images from Stevens’ book can be found at Annette Millington’s blog here.
My own interpretation of Steven’s patterns are reflected in the introductory image to this post, but in summary Stevens four strategies are as follows:
Explosions: An explosion connects a single point directly to each other point in the set. (See Image Top, First Row)
Spirals: The spiral starts at a central point, and progressing in one of two directions, connects points in a rotating fashion. There is no branching in a spiral, with each point connected to only two other points. (See Image Top, Second Row) In the mathematical terms of graph theory, all points in a spiral have a degree structure of 2 (connected to only two other points), except for the start and end points, which have a degree structure of 1.
Meanders: A meander is similar to a spiral having an identical degree structure (1-2-2….2-2-1), but connects points in a much more flexible manner, with frequent changes of the direction of connections. Meanders and spirals share many similar properties.
Branching Structures: In a branching structure, nodes can have a degree higher than 2, and points are typically connected to their nearest neighbor regardless of whether other connections come into this point already. Branching structures usually start at a single point, and “grow” from this single point incrementally, adding connections to the nearest neighboring point in an iterative manner.
Stevens recognized that the limitations of space would cause similar organizational structures to appear even when different processes of formation where in play, but like György Kepes had recognised in his book The New Landscape in art and science, he observed general trends and commonalities in the behavior of these four networks, and proposed that processes of formation and function were closely related to the associated form. (Stevens, 37)
The simplest of the four patterns proposed by Stevens was the explosion, which also has the shortest average distance between any two points. This network prioritizes speed, but the cost of the network is extremely high in terms of overall length. The spiral, on the other hand, is generally very compact having a low overall length and can develop in a very ordered fashion, but as overall size increases, the distance between any two random points increases as a function of its length. The spiral can be seen as an orderly transfer of energy or material from one point to another. The meander is similar to the spiral in its properties, but in contrast to an ordered development, it can develop in a number of dynamic and chaotic ways. Depending on how it is formed, the meander can in some instances be even more compact than the spiral, but in others it has a far longer length. This network forms in spaces with energy transfer from one point to another, but where flows of matter or energy are highly variable. The last of the networks has perhaps the most surprising properties. The structure of a branching network, like the explosion, connects one point to every other point in the network in a fairly direct path. It is generally only slightly less efficient than the explosion in this way. It does this, however, in a very economical way, with a low overall length, even compared with spirals or meanders. Because of its economy and efficiency, it is no surprise that this type of network is the basis of the body plan of many organisms, including all vertebrates, some invertebrates (the others having a fundamentally spiral body plan), as well as most plants.
Most networks are not purely of one type or another, and hybrids exist between them. River basins, for example, generally follow a branching pattern connecting all points in the river basin to a single river mouth, but between nodes in the overall branching structure, meander patterns tend to form. Likewise, plants might have an overall branching structure, but this is deployed in a spiral fashion. (Stevens, 37-48, Bell, 20-27)
Algorithms for Non-redundant Networks
To test Steven’s propositions about these four basic non-redundant graph structures or patterns, I tried to create a series of algorithms for each of these strategies to test their properties for space colonisation and the overall efficiency of the networks created. The goal of this post is to summarise the findings of the four algorithms, each of which will be covered in a bit more detail later.
The simplest of the networks proposed by Stevens is the explosion. Here the algorithm 1) simply finds the point closest to the center of the point cloud, and then 2) connects this point to each other point.
The spiral also starts with a single point. Conceptually, the spiral can be said to start in the center of the cloud, but in order to avoid certain problems with the outer points, in this case the formation is reversed and the outer points are added to the spiral first. To do this the algorithm 1) Finds the point furthest from the center of the spiral and draws a circle through this point, with its center at the center of the spiral. 2) Next a line is drawn from the center of the spiral, through the last point added to the spiral, and continuing to the circle drawn in step one. 3) The intersection point is moved a small amount equal to the average distance between points in the point cloud, in a direction tangent to the circle in either a clockwise or counter-clockwise direction based on the vector of the last segment added (or randomly selected in the first round). 4) The closest point not yet in the network to the translated point from step 3 is added to the spiral.
Similar to the spiral, the meander represents a more chaotic flow of matter or energy and for me was the most difficult of the four basic patterns to model. I tried various algorithmic strategies but all had defects. The most effective strategy demonstrated here 1) starts the algorithm at the point with the smallest Y value. 2) A radius of a parametrically variable dimension is drawn at this point, and all points within this radius are considered to be added. In this example the circle has a radius 1.3 times larger than the average distance between points in the point cloud. The final decision on which point to add is 3) the point within this radius with the smallest Y value. The algorithm then 4) repeats this process with the radius always determined starting at the last value added. In general, the algorithm produces non-redundant meanders, but errors do appear, especially towards the algorithm’s final steps.
The final of the four non-redundant networks, the branching network, is in contrast to the meander very easy to model and error free. The algorithm starts by 1) ordering all the points in the point cloud based on their distance from the center of the point cloud. 2) It then selects the point closest to the center of the point cloud (the first item in the ordered list of points) and adds this to the network. 3)The algorithm then gradually goes through the list, taking the next ordered point, and drawing a line from this point to the closest node already added to the network. Once a node is added to the network, it is removed from the ordered list from step one, and moved to a second list—nodes already in the network.
Tests on Network Properties
Once all of these networks were created, I ran a series of tests using a shortest path algorithm on each network to determine the average distance between any two random nodes in the network, using only the associated edges for each network strategy. The results of these tests, comparing average network distance between nodes with the cumulative length of all the network’s edges, i.e. the total network length, are summarized in the image below. For the non-redundant networks, the explosion always maintains a lead in minimizing the average distance between any two random points, but its overall length increases much faster than the other networks as points are added. On the other hand, branching networks while having only slightly higher average distances than the explosion networks, are very economical in minimizing the total network length. The efficiency of this type of networks gives hints to as why it is found in so many natural systems.
In the coming days, I will be posting some scripts relating to colonizing space with these general strategies, starting with the meander. In the meantime, however, you could try writing an algorithm based on the logic explained from the images above, since your solutions may be better than mine!
Sources
Joseph Claghorn. Algorithmic Landscapes: Computational Methods for the Mediation of Form, Information, and Performance in Landscape Architecture. (doctoral thesis Leibniz University Hannover, 2018), 178, 184-189.
Peter Stevens. Patterns in Nature. (Boston: Little, Brown and Company, 1974), 3-4.
Simon Bell, Landscape: Pattern Perception and Process. 2nd ed. (London: Routledge, 2012), 20-27.