EVE Online: Jita to Amarr

EVE Online is a fun, and possibly psychotic MMORPG that takes place in an expansive stellar cluster with some truly mind-boggling distances involved. To fully explore this universe you can expect to spend over 9 years of your life.

In a game where logistics and industry make news-worth battles possible, calculating optimal routes between systems and stations becomes an important task.

The EVE Universe
The EVE Universe from the in-game map.

Taking our first look at the EVE Universe can be a little daunting. A total of 8285 solar systems make up the stellar cluster, although not all of them are player-accessible. A few, known as wormholes or J-space, are not permanently attached to any part of the map and their connections roam around. The remaining systems that are permanently connected to each other make up what is known as k-space, or known-space. 13753 stargates form the permanent connection points between the stars. What if we sketched out EVE's main trade-hub, Jita, and its connections to its neighboring systems?

graph TB
    A["Jita"] --> B["Perimeter"]
    A --> C["Mausari"]
    A --> D["New Caldari"]
    A --> E["Niyabainen"]
    A --> F["Sobaseki"]
    A --> G["Mouvolailer"]

If you've ever done graph theory, this hopefully looks pretty familiar. We can easily represent the EVE map as a graph where each solar system is a vertex (or node), in the graph, and each pair of stargates forms an edge between two vertices.

We're going to use Python to create a graph we can use to answer simple questions like "What's the shortest route to get from Jita to Amarr". Later, we'll make it a bit more complex so we can add new conditions, like finding the safest route. In the actual tool this article is based off of, we pull the systems and stargates from EVE's API, known as the ESI, but to keep things simple you can simply download these two JSON files, which contain all the systems and stargates.

There are several popular libraries for working with graphs in Python, such as networkx and igraph. Networkx is a native python library that trades intuitive usage, flexible types and good error messages for high memory usage and slower speed. igraph is a C library with python bindings that is harder to use and less intuitive, but offers significantly better memory usage and faster lookups. For this article, we want simple, so we're sticking with networkx.

Our first step is to load the data. Remember, our systems are our nodes, and the connections between stargates form our edges:

import json
import networkx as nx

graph = nx.Graph()

with open('systems.json', 'rb') as systems_json:
    systems = json.load(systems_json)

    for system in systems:
        graph.add_node(system['system_id'], name=system['name'])

graph.add_node() takes a unique identifier for the node and any extra attributes we want to save on it, in this case the name of the system. One nice thing we get from networkx is the ability to use our system's IDs as the node ID. In igraph, we get incremental numbers as our node IDs. Now that we have all the systems added, we're going to add the edges:

with open('stargates.json', 'rb') as stargates_json:
    stargates = json.load(stargates_json)

    for stargate in stargates:
        graph.add_edge(
            stargate['system_id'],
            stargate['destination_system_id']
        )

We're actually done here. We can answer our original question of "What's the shortest route to get from Jita to Amarr" with what we've done already:

print(
   nx.shortest_path(
        graph,
        30000142, # The System ID for Jita
        30002187  # The System ID for Amarr
    )
)
[30000142, 30000138, 30000132, 30000134, 30005196, 30005192,
    30004083, 30004078, 30004079, 30004080, 30002282, 30002187]

Those numbers are the systems IDs we'd need to pass through to get from Jita to Amarr in the shortest possible distance, and we got the answer in less than a millisecond. Not very useful on their own, but we could easily look up the names from the systems.json file we loaded earlier.

When we called nx.shortest_path(), networkx used an algorithm called Dijkstra's algorithm to efficiently find the shortest path between Jita (30000142) and Amarr (30002187). It's actually a very simple algorithm, and if you don't want to use networkx you could implement it yourself pretty quickly.

Not all roads are worth taking

Just because a route is the shortest on paper doesn't mean it's the best route to take. If you took the original 11-jump route in a freighter, you'd be dead long before you made it to Amarr.

In EVE, the relative safety of a system is represented as a value known a its "security status", which is a number with 3 ranges:

low high name
-1 0 null-sec
0 0.5 low-sec
0.5 1 high-sec

Beware the rounding of numbers here, which is a constant source of pain in EVE. The rules for rounding numbers are different depending on where they're used and occasionally just broken to the point where "CCP_Round giveth and CCP_Round taketh" is a running gag. We're keeping it simple for this article, but it's not really low-sec at 0.5, but 0.45. Usually.

Remember that short 11-jump route we found earlier? You would probably have died 4 jumps in as that system is low-sec, allowing other players to attack you with minimal repercussions.

["Jita", 30000138, 30000132, 30000134, "DEATH", 30005192,
    30004083, 30004078, 30004079, 30004080, 30002282, "Amarr"]

If you never make it to your destination, it's not really the shortest route now, is it? We're going to fix this by adding some more information to our graph. Let's go back to where we loaded up nodes and edges and make a few changes:

import json
import networkx as nx

graph = nx.MultiDiGraph()

with open('systems.json', 'rb') as systems_json:
    systems = {
        system['system_id']: system
        for system in json.load(systems_json)
    }

with open('stargates.json', 'rb') as stargates_json:
    stargates = json.load(stargates_json)


for system_id, system in systems.items():
    graph.add_node(system_id, name=system['name'])


for stargate in stargates:
    security = systems[stargate['destination_system_id']]['security_status']

    graph.add_edge(
        stargate['system_id'],
        stargate['destination_system_id'],
        ls=0 if security < 0.45 else 1,
        hs=0 if security >= 0.45 else 1
    )

Right away you should notice a few things. Our graph is no longer a nx.Graph(), it's now a nx.MultiDiGraph(). This is important! Our original graph didn't have a concept of direction, and didn't allow multiple edges between the same nodes. We've also stored two attributes on each edge, hs (high-security) and ls (low-security), which are weights we'll use later to determine if we should take this edge when looking for safe or unsafe paths.

So why have we changed the type of graph we're making? If we sketched our original graph two connected systems would look something like this:

graph LR
    A["Jita"] --> B["Perimeter"]

Then we add the return paths, turning our graph into a directed graph with multiple edges, or a MultiDiGraph() in networkx:

graph LR
    A["Jita"] --> B["Perimeter"]
    B["Perimeter"] --> C["Mausari"]
    B --> A
    C --> B

Now our graph has all the information we need to pick a much safer route. Let's try our shortest path between Jita and Amarr again:

nx.shortest_path(
    graph,
    30000142, # The System ID for Jita
    30002187, # The System ID for Amarr
    weight='hs' # Use the 'hs' attribute for weights
)
[30000142, 30000144, 30000139, 30002802, 30002801, 30002803, 30002768,
 30002765, 30002764, 30002761, 30004972, 30004970, 30002633, 30002634,
 30002641, 30002681, 30002682, 30002048, 30002049, 30002053, 30002543,
 30002544, 30002568, 30002529, 30002530, 30002507, 30002509, 30000004,
 30000005, 30000002, 30002973, 30002969, 30002974, 30002972, 30002971,
 30002970, 30002963, 30002964, 30002991, 30002994, 30003545, 30003548,
 30003525, 30003523, 30003522, 30002187]

That's quite a bit longer, at 46 jumps! However, we're more likely to actually arrive at our destination by taking a route through safer systems.

Note that we've simply done safe or unsafe here. Instead of a 0 or a 1, we could have scaled the weight by how safe the system was. We could also mix in other values, such as "Has someone died here recently?"

Sometimes you want to stay in the less-secure systems. If you're a criminal, you don't want to run into the police now, do you? We would simply use weight='ls' instead of weight='hs' to get a route that we keep us in less-secure space.