Spatial Networks in Space
I used to think that spatial networks were kind of boring. While the knowledge networks, the language, the internet, the social networks all promised a break from our everyday 3D surroundings into a vast untamed world of infinite dimensions and small distances, the networks in space, especially on a plane, seemed too similar to familiar lattices, too constrained to be interesting.
Having to be embedded in space is an incredibly strong constraint that weeds out most of the possible network topologies. The ones that remain are bound to have special properties. One common constraint is that in a 2D plane two edges cannot cross each other. In order for two streets to cross each other, you need to either create an intersection node, or run one of them across a bridge or tunnel, using the third dimension. Another constraint is the cost driven by the spatial metric. On the internet, you can follow a path across web pages through a few easy clicks, regardless of which server hosts each page around the world. But in the physical world, to get to a different place you need to walk or drive or take some other transport to cover the distance, and that would cost you time and money. Spatial distances thus factor into all of our daily decisions of where to live, where to work, and where to visit.
How do the spatial constraints drive the structure of spatial networks "in the wild"? One fascinating study highlights the universal topological structure to which subway networks converge, whether they originate in a city like London (1863) or like Shanghai (1993). Over time, the subway lines form a dense clump in downtown, surrounded by an inevitable ring line, with tendrils extending beyond it into the suburbs - a map very familiar to anyone who has lived in or visited a large city. This layout traces the population density, is nearly optimal to carry the traffic, but also develops gradually from the first line to the full network over the years by the generations of transportation engineers.
Sometimes, the efforts of urban planners are overtaken by self-organization. Such is the origin of slums, informal urban districts home to a billion people around the world. The densely packed and irregular buildings make any navigation through a slum challenging - both for the residents and for the communal services such as electricity and water. A recent study used a combination of multiple sources and techniques from archives to satellite images to local activist groups in order to map out the fascinating complex topology of the slums and found that the houses deep within the slum block generically lack access to the services. Yet very small interventions, such as demolishing just a few houses and laying out an extra 60 meters of roads, can provide enough shortcuts to decrease the navigational complexity and activate the economic life of the slum.
How does spatial organization come about? After all, usually we can't just sit and decide where all the elements go in an optimal fashion from the start. There needs to be a process of structural development, an ontogeny from simple origins to complex destinations. The brain of humans and other higher animals is a complex arrangement of neurons, with each specific region responsible for a different function but connected to other regions. Yet the brain needs to grow anew in every individual during its development from a zygote to adulthood. A recent paper offers clues to the mechanisms of brain ontogeny, leveraging the time-dependent spatial gradients of growth to explain a large fraction of observed brain wiring patterns. Getting the brain structure right would be too hard in a top-down fashion on an assembly line, it has to be grown organically in time and space - and that's the way biology does it for each of us.
You can try to spend a lifetime to design a functional subway (please someone in the US do this), to figure out the socio-architectural dynamics of slums, or track the development of a brain - but can you learn something about these spatial networks faster? Beyond the papers that are as dry as any science, is there a way to visceralize the experience of wrestling with the spatial constraints? Yes! I would like to introduce you to Slipways, a video game by designer Jakub Wasilewski, in which the player builds an interstellar empire. Slipways is a nod towards the genre of global strategy games known as 4X (Explore, Expand, Exploit, Exterminate), but really without the fourth component. Wasilewski's design goal was to prune a strategy game from all the tedious and time-consuming parts, which resulted in a very tight experience: each round takes just about an hour. So how does it work and what does it have to do with spatial networks?
In Slipways, you see a sector of a galaxy filled with planets, asteroids, and debris, all on a 2D plane. Each planet can be colonized, so that it produces some resource but demands another resource. Two planets that are close enough can be connected by a "slipway" (a faster-than-light highway), along which the resources travel. Workers from an Earth-like planet can travel to a relic planet and build robots out of scrap, the robots then go to an ocean planet to grow food, and food is shipped back to the Earth-like planet to support the workers. As planets exchange resources, they satisfy their needs and upgrade, growing the economy and well-being of the empire, and demand new resources that require more slipway connections. The main catch is that the slipways cannot intersect any other objects, including other slipways, so the whole experience is about building a planar network that moves resources while avoiding obstacles.
There is no universally correct solution to each situation - not only can you pursue different strategies for your empire, but in fact every next galaxy sector you encounter is procedurally generated and different. Out of the enormous ensemble of all possible network configurations that satisfy the non-intersection constraint, every player's decision carves out the path to victory. The seemingly global constraint of edge non-intersection is actually not daunting as it is visibly broken down into individual decisions. If every slipway you build doesn't intersect the existing ones, then the network is planar. The network formation is, of course, path-dependent, since you need to build a small stable loop of planets that satisfy each other's needs before you can expand, so your early choices constrain the later options.
To keep things interesting, the game also has a technology tree. If early on you invest resources into building science labs, then later you can reap the benefits that relax the game constraints. What if you could shift the planets in space before colonizing them? What if you could ignite a planet into a star that provides energy and satisfies any resource requirement like a wildcard? What if, very late and very expensive, you could build infraspace slipways that can cross regular ones but not each other? While rare, such tricks can help you get that one crucial shortcut and deliver a resource where the planar constraint would have prohibited it.
The solution ensemble in which I analyze situations and make decisions didn't come out of nowhere: it was carefully curated and designed. Slipways is an indie game, product of the singular mind of its developer. Before I made my solution choices, he made his design choices. How many planet types should there be and in what proportion? How far do the standard slipways reach and how much can you extend them with tech? How many different resources are there? What are the probability weights of the random tech tree? How much time should each action take so that a standard run fits in 25 years in-game and about 1 hour in real time?
Slipways is a strategic game that lives and dies on its systems: every draw of the random sector, every bonus from ancestor ruins, every tech tree realization, every set of tasks from the advisory council, and every decision you make construct the narrative of the run. However, the game also has a campaign mode with a somewhat more explicit plot. In fact, it is the recently released Act 2 of the plot that made writing this post inevitable when economic systems, player's agency, and plot-driven gameplay quirks came together just right.
Slipways teaches its rules intuitively, you just need to respond to the gamified design pressures. It reveals the space-constrained, path-dependent ontogeny of space networks, but in that reproduces the way real slums, subways, and brains grow. And if some instructors teach history with Civilization, then why not teach yourself some spatial networks with Slipways?
I can't wait for Act 3.