Besides for the packet routing (which is just computing the shortest path along the graph using Dijkstra’s algorithm), most of the math that went into it is in the generation of the starting graph.
The general approach is that it generates a bunch of points in a circle-ish area and then connects some/most of the points together with edges. I had 4? different ways of generating the circles:
- Pick points randomly in a circle, and then space them out with some heuristics (in this case, badly-implemented llyod relaxation)
- Pick points in concentric rings, with each ring having a multiple of some number of points. (Basically, ring 0 as 1 point; ring 1 has n points at distance 1; ring 2 has 2n points at distance 2; etc, where n is randomly generated for each cluster)
- Pick points according to a Fibonacci spiral (see the first part of this SO answer for an explanation)
- Pick points randomly using Poisson-Disc sampling
Then the points are connected together with edges:
- Create an initial set of edges using Delaunay triangulation; I used a library for this
- Compute a minimum spanning tree of the cluster’s graph
- For each edge that isn’t in the minimum spanning tree, remove it with some probability
Maintaining the minimum spanning tree edges means that there will never be disconnected segments in the graph, since the MST connects all vertices.
The top-level map is actually just another generated cluster of points, where each point was replaced with another generated cluster, and the edges are replaced with edges between the outermost points in the inner clusters.
If you have any questions or clarifications, feel free to ask! This was an interesting project to work on, and the graph generation and visuals were much more interesting to make than the actual gameplay.