Cities are randomly placed on a plane. Every pair of cities is a candidate road with a build cost equal to the straight-line distance between them:
cost(i, j) = sqrt( (xi - xj)² + (zi - zj)² )
The planner sorts every candidate road cheapest-first and applies Kruskal's algorithm with a union-find structure: it adds the next cheapest road only if its two cities are not already connected (no wasted loops) and the running total stays inside the construction budget. This is the standard greedy method for a minimum-spanning-tree road network — the cheapest possible layout that reaches every city, cut short wherever money runs out.
sort candidates by cost
for each candidate (a, b):
if find(a) != find(b) and spent + cost <= budget:
union(a, b); spent += cost; build road
A spanning tree is efficient but fragile: every road in it is a graph bridge — removing any single one splits the network. The redundancy budget spends extra money on the next cheapest unused roads to close loops, computed with Tarjan's bridge-finding algorithm (a DFS that tracks discovery time and the lowest reachable discovery time low[u] for each city):
low[u] = min(disc[u], min over neighbors v:
disc[v] if (u,v) is a back edge,
low[v] if v is a DFS child)
edge (u,v) is a bridge ⇔ low[v] > disc[u]
- Cities / Construction budget — set how many cities to connect and how much money is available; the tree is rebuilt live as the budget slider moves.
- Redundancy budget — extra money spent on backup loops after the tree is built, turning critical bridges (amber) into safe roads (green).
- Simulate Road Failure — knocks out one random built road and recomputes which cities are still reachable from the gold capital — a direct test of the network's resilience.
Real-world relevance: this is the same trade-off civil and transport engineers face — a minimum-cost spanning network is cheapest to build but every link is a critical failure point, so real infrastructure budgets always reserve money for redundant routes.