Stadt-Bahn-Pilz
Zufällig erzeugte Städte mit eigenem U-Bahn-Netz, jede aus einer Startzahl (Seed). Drei Algorithmen suchen um die Wette den Weg zwischen zwei Stationen, die du antippst. Du siehst, welche Stationen sie sich anschauen und welche Route sie am Ende nehmen, und kannst einzelne Linien bestreiken lassen. Die Stadt steht als Modellbahn auf dem Tisch, zoomen geht mit dem Mausrad oder zwei Fingern, verschieben durch Ziehen.
Handy quer halten für mehr Platz
Deine Verbindung
Was du siehst
Alle drei im Vergleich
Pilz gegen Plan
Was steckt dahinter?
Die Stadt wächst aus dem Seed, einer Startzahl für den Zufall. Der gleiche Seed ergibt deshalb immer die gleiche Stadt. Zuerst werden Stationen zufällig verteilt, in der Mitte dichter als am Rand und nie zu nah beieinander. Dann verbindet eine Delaunay-Triangulierung jede Station mit ihren natürlichen Nachbarn. Aus diesem Netz werden die Linien ausgeschnitten. Jede läuft auf dem kürzesten Weg vom einen Stadtrand über ein Zentrum zum anderen, und größere Städte bekommen zusätzlich eine Ringlinie. Stationen, an denen keine Linie hält, fliegen raus.
BFS (Breitensuche) zählt nur Stationen. Sie findet die Verbindung mit den wenigsten Stopps, und es ist ihr egal, wie lange die Fahrt dauert oder ob man dreimal umsteigen muss. Dijkstra rechnet mit echten Fahrzeiten plus 4 Minuten pro Umstieg und findet garantiert die schnellste Verbindung, sucht dafür aber in alle Richtungen gleichzeitig. A* ist Dijkstra mit Orientierungssinn: Er schätzt die Restzeit über die Luftlinie ab und sucht deshalb zuerst Richtung Ziel. Solange die Schätzung nie zu hoch ist (hier ist das die Luftlinie bei Höchstgeschwindigkeit und ohne Halte), ist die gefundene Verbindung trotzdem die schnellste.
Damit Umsteigen etwas kostet, suchen Dijkstra und A* nicht auf Stationen, sondern auf Paaren aus Station und Linie: „Hauptbahnhof in der U2“ und „Hauptbahnhof in der U4“ sind zwei Knoten, zwischen denen 4 Minuten liegen. Fahrplan-Apps machen im Kern dasselbe, nur mit echten Fahrplänen und schnelleren Verfahren wie RAPTOR.
Fun Fact: Ein Schleimpilz hat Tokios Bahnnetz nachgebaut
2010 hat ein Team um Atsushi Tero und Toshiyuki Nakagaki Haferflocken an die Positionen von 36 Orten rund um Tokio auf eine feuchte Schale gelegt und den Schleimpilz Physarum polycephalum darauf losgelassen. Er hat sich ausgebreitet, das Futter gefunden und sich dann zu einem Röhrennetz zurückgezogen, das dem echten Bahnnetz erstaunlich nahe kam: ähnlich billig, ähnlich effizient und mindestens so ausfallsicher. Berge und Seen haben sie mit Licht nachgestellt, weil der Pilz Licht meidet. Daraus hat das Team ein einfaches Modell abgeleitet: Röhren, durch die viel fließt, werden dicker, ungenutzte verkümmern. Genau das läuft hier, wenn du den Schalter auf „Schleimpilz“ stellst, auf deiner Stadt. Vereinfacht ist, dass der Pilz hier am Anfang das ganze Delaunay-Netz bedeckt und die Haferflocken an den Umsteige- und Endstationen liegen.
Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D. P., Fricker, M. D., Yumiki, K., Kobayashi, R. & Nakagaki, T. (2010). Rules for biologically inspired adaptive network design. Science, 327(5964), 439–442.