Building a Graph of High Frontier
Foreword: When I started this project, I had never used or studied graph theory beyond being aware of the basic idea. I thought making a graph for this massive board game could be used to calculate optimal routes between sites, but mostly it seemed like a fun thing to do. I use Python all the time, and the NetworkX module looked easy to work with and mature. This story is about the process I took to build the graph and all the things I’ve learned along the way.
In the board game High Frontier, players build rocket ships to travel & prospect the solar system. The spaces of the board represent sites (places to go like the Moon or an asteroid), hazards (things like radiation or Venus’s acid clouds), Lagrange points (stable gravity pockets between two large bodies) and most importantly, the magenta burn spaces, which represent a delta-V cost of spending fuel to accelerate. Each large body also has a corresponding flyby space which gives the player some number of “free burns” to pass through magenta spaces they encounter later in their turn.
Naturally, we can imagine describing the spaces as a set of nodes (and their connections, called edges, which may be directed or undirected) to represent the board. We can define costs to traverse between two nodes by weighting the corresponding edge. From these simple axioms emerges the whole discipline of graph theory, which can be applied to things like the Internet, linguistics, road or social networks and even quantum field theory.
For High Frontier, the graph needs to be a directed graph, since while most connections are bidirectional (or undirected, really), there are paths that represent aerobraking which are strictly one-way. Later, I also figured out the graph would need to be a multigraph since on a few instances, there are both conventional landing edges & aerobrake edges between the same two nodes.
G = nx.MultiGiGraph()
Problem 1: How to handle Hohmann intersections
When players move around the board along the routes that represent various trajectories, they may come across the intersection of two routes. Continuing straight through the intersection is a free move which represents coasting. Players may also spend 2 burns to change directions and pivot at the intersection to continue moving that turn. Alternatively, they may end their turn on the intersection, and on a following turn continue for free in any direction.
My instinct was to represent these intersections as nodes on the graph. After all, they are truly spaces a player may stop on, and are easily identified (with some very loose naming conventions — look, naming things is hard…) by labels I had been keeping track of in Paint over an image of the board.
Unfortunately, this was doomed to fail. I thought I could simulate the “free”-ness of straight paths through intersections by creating an edge between every node along the straight path (and quickly realizing I should hide these supplemental edges when plotting the graph, lest it become even less readable). This will eventually create free edges from the other intersection’s nodes, and that doesn’t capture the pivot costs.
Around the same time, I was puzzled by my understanding that edges were the weighted interfaces for graphs, not nodes. But in High Frontier, burns are spaces. Was my model all wrong?
add_all_edges(‘Flyby Luna Purple’, ‘HI_P0’, ‘HI_P1’, ‘HI_P2’, ‘HI_P3’, ‘Burn Purple 1’)
Problem 2: Are the spaces nodes? Or are the route edges nodes?
It really felt natural that spaces on the board were nodes in the graph and trying to even look at it any other way was challenging. But, if I wanted to calculate any shortest paths, I needed to get this part right, preferably before I got too far in making the graph of the board.
There was something really nice to the route edges being nodes when it came to Hohmann intersections: it was easy to represent going straight vs. pivoting. Graphs don’t have any concept of “straight”, just connectivity, and because of this, intersections are far more complex than they seem.
Six edges and four nodes are required per two-way intersection, as above, to represent all of the ways a player might travel through. Even though in a game a player can stop on the intersection (and I didn’t put a node in for the intersection itself), it’s not necessary when calculating costs. Each edge has a property for the burn cost (2) and the game-turn cost (1), so I can calculate the best routes under either criteria.
I also figured out that I could indeed weight nodes, so most of the spaces on the board could stay nodes, which was a relief. Only intersections of routes would be a little more complicated, but I wrote a fancy function to take care of this for me which added a bunch of cardinal indicators to my notated board as necessary.
add_turns(‘Burn Lagrange Earth-Luna L3’, ‘HI_Venus_Signpost’, free=(‘N’), exclude=(‘S’), east=’Burn Lagrange Sol-Venus L4', north=’Lagrange Sol-Venus L1')
Problem 3: Shortest path algorithms & negative cycles
To compute shortest paths between nodes in a graph, there are a handful of available algorithms that do better than simple brute force. Dijkstra’s algorithm is the fastest known, but requires non-negative weights. However, recall that the board contains Flyby spaces for many planets and larger moons which grant free burns. For example, the Flyby Earth space grants +2 burns; I would give it a cost in the graph of -2 burns, since at the end of a route, a player would have indeed paid 2 less burns as a result of the flyby bonus.
So, Dijkstra’s won’t work. But, graph theory is plenty mature and there are other options, and the Bellman-Ford algorithm (originally proposed by Alfonso Shimbel, and I point that out because it seems like he was not recognized for the work by sheer bad luck) can handle negative weights.
Unfortunately, there is another problem: negative cycles.
When I ran a query on a shortest path for the High Frontier graph, Bellman-Ford raised that it detected a negative cycle in my graph. Amusingly, detecting the presence of a negative cycle and knowing where it is are two entirely different things.
After adding a bounty to an old question on stackexchange, I was able to find a function that could return negative cycles, and so I ran it on my graph.
>>> find_negative_cycle(G, weight_func=burns_advanced)
[‘Radiation Jupiter G1’, ‘Flyby Jupiter’, ‘Radiation Jupiter G1’]
What? Why are we going back and forth, here?
Wait, no, spaceships can’t just reverse direction mid-flight! That’s a negative cycle!?
But that’s not something graphs care about. My graph is directed, but most nodes are connected by edges in both directions since you can go in either direction, of course. You can’t, however, reverse direction in a single move.
For now, this problem is still unsolved… I may return to it with a brute force solution, but for now I can’t actually calculate shortest paths that include negative flyby bonuses.
The complete picture
Firstly, you might notice that this graph looks a lot nicer than the previous plots. I discovered there was a better algorithm for placing the nodes in the plot, Kamada & Kawai, that uses a path-length cost function.
Secondly, the outer solar system really skews things. This actually makes a lot of sense since the heliopause really is just very far away from everything else, it gives the graph a sense of real scale, something that Eklund certainly intended with how realistic many of the games rules are.
Here’s just the inner solar system, including Jupiter:
Unsurprisingly, comets and the moons of Jupiter are now opposite Mercury and the Solar Oberth Flyby. The dense network of intersecting routes with lots of asteroids strewn about is a little less cluttered, and the web of cardinal intersections makes a nice pattern.
I tried to do as much error checking as I could, though that by itself is a tricky task. One quick thing I did was look for nodes that only had a single neighbor, but weren’t a site (since most sites are terminal). I found a handful of typos and forgotten connections this way, and only a few mid-aerobrake hazards were exceptions to the exercise.
I’m not sure what’s next for the graph, but I definitely can’t wait to play the actual game again, now that I’m so much more familiar with all the routes and sites!