Slime Mold Maze Solver

In 2000, Toshiyuki Nakagaki, Hiroyasu Yamada and Ágota Tóth published a one-page paper in Nature titled "Maze-solving by an amoeboid organism" (Nature 407, 470). They laid a small maze on an agar plate and filled its corridors with fragments of the plasmodium of Physarum polycephalum — a slime mould. The fragments fused into one continuous sheet of organism occupying the entire maze.

Then they placed blocks of nutrient agar at the start and the end. Over the following hours the plasmodium withdrew from every dead end, and then from the longer of the alternative routes, until what remained was a single thick tube connecting the two food sources along the shortest path through the maze. Where several routes linked the two food blocks, the organism settled on the shortest.

What makes this notable is what Physarum does not have. It is a single cell — very large, containing many nuclei, but one cell. It has no neurons, no brain, and no central controller of any kind. The paper's claim, and the reason it is still cited, is that this counts as a primitive form of computation carried out by cell physiology alone.

The plasmodium is a network of tubes through which protoplasm is pumped back and forth by rhythmic contractions — shuttle streaming, reversing roughly every 90 to 120 seconds. The mechanism behind the maze result is a positive feedback loop on that flow:

• Flow thickens tubes. A tube carrying a high rate of protoplasmic flow grows in diameter.
• Thicker tubes carry more flow. Hydraulic resistance falls sharply with radius, so widening a tube increases the flow through it further.
• Starved tubes disappear. A tube carrying little or no flow shrinks and is eventually resorbed by the organism.

Once food is placed at two points, the sustained traffic between them runs along connecting routes. A dead-end branch carries no through-traffic at all, so it starves first. Between two routes that both connect the food sources, the shorter one has less resistance, draws more flow, thickens faster, and progressively steals flow from the longer one until the longer route collapses. Nobody computes the shortest path; it is the only configuration the feedback loop is stable at.

In 2010 Atsushi Tero, Nakagaki and colleagues published "Rules for Biologically Inspired Adaptive Network Design" in Science (327, 439–442). They arranged oat flakes on a wet surface in the pattern of 36 locations around Tokyo — the city itself plus the surrounding stations of the real rail network — and used bright light, which Physarum avoids, to stand in for geographical obstacles such as water and mountainous terrain.

Within about a day the organism had settled into a network of tubes whose topology closely resembled the actual Tokyo rail system. The authors scored the result on three measures against the engineered network:

• Cost: total length of all links in the network.
• Transport efficiency: average distance along the network between pairs of locations.
• Fault tolerance: probability that severing a single random link disconnects part of the network.

The slime mould's network was comparable to the real rail network on all three, which is striking given that the rail system is the product of decades of deliberate engineering. The paper's more useful contribution was a mathematical model, abstracted from the organism, for growing robust low-cost networks — the point was not that slime mould should design railways, but that a decentralised biological rule produces solutions in the same quality class as centralised design.

The simulation above is not a fluid-mechanical model of protoplasm. It is the agent-based model introduced by Jeff Jones in 2010 ("Characteristics of pattern formation and evolution in approximations of Physarum transport networks", Artificial Life 16(2), 127–153), confined to the maze corridors. Thousands of particles move over a chemoattractant grid. Each one, every step, does exactly three things: sense, turn, deposit.

An animation that merely looks organic proves nothing, so the page verifies the result. The dashed line is the true shortest route, computed by breadth-first search on the maze graph — the correct algorithm here because every corridor has equal cost, which makes BFS optimal and O(V + E). The agents never see it.

To read the slime's own answer, the surviving trail is averaged per maze cell and then a widest-path search finds the A-to-B route whose thinnest cell is as thick as possible. That is a deliberate choice over following the strongest neighbour greedily: a greedy walk will happily chase near-zero noise through a broken network and report a path that is not really there, whereas requiring every cell on the route to clear the same visibility threshold means a reported path is a genuinely continuous tube.

The honest limitation: this works while the two food sources are close enough that agents complete round trips between them within a run. Push them much further apart and the trail connecting A to B never becomes continuous in the first place, the flux rule has nothing to reinforce, and the retraction produces a dead network rather than a shortest path. That is why the three layouts here are hand-built and compact rather than randomly generated — a random maze generator produces failures more often than demonstrations, and a simulation that only sometimes shows the phenomenon it claims to show is not worth shipping.