Tracing Katia Sae's Steps

On March 9, 2019, all accessible star systems in EVE Online were explored for the first time. Katia Sae has reported taking over nine years for this journey and visiting 7806 systems in the game world.

A little over nine years ago, 1st of December YC111, my journey began to explore all of New Eden and today, this day, 9th of March YC121, I have done just that. With the exception of the 230 unreachable Jove systems, I have visited every High Sec, Low Sec, Null Sec, and yes, every wormhole system – Every system in New Eden – without losing a single ship.

EVE’s systems can be divided into two classes: On the one hand, there is “Known Space” (K-Space), where individual stars are linked by warp gates. Each star is surrounded by one or more gates, each leading to a different system. This creates a network of warp connections that define the players’ travel routes. The second class consists of “Wormhole Space” systems. These are interconnected and linked to K-Space via randomly appearing and disappearing wormholes. While 5201 systems are reachable via warp gates, the Wormhole Space comprises roughly half that amount, namely 2604.

Tracing Katia’s Journey #

Inspired by Katia’s journey, countless players like me are motivated to do the same. However, my EVE character would rather sit in Hek and chug down Quafe after Quafe (or something like that) than go through nearly 8000 systems. But let’s assume he were less lazy: How long would it take him to visit all of EVE’s systems? Finding the right wormholes requires a good dose of luck and a lot of patience. What’s hard to estimate for wormhole systems could at least be roughly calculated for K-space: The warp gates are marked on the map and can be easily flown.

With the journey now restricted to the 5201 systems connected by warp gates to New Eden, the adventurous pilot faces the question of how many jumps a ship actually needs to visit all systems. While some systems serve as hubs with many warp gates, others are bottlenecks on the map or dead ends. So he’ll need to visit some systems more than once. But the goal is clear: We’re looking for the shortest path through all systems, which gives the story a bit of the famous Traveling Salesman Problem vibe.

Python in the Board Computer #

Since a Travelling Spaceman doesn’t want to find this optimal path by hand on the map, a small Python script should help. The approach is a partly randomized pathfinding executed a few thousand times in good old brute-force fashion. The program has several areas of responsibility:

• Loading the star systems and their warp gates via the EVE Online API
• Logic for finding a path through all systems
• Rolling some parameters and executing frequently
• Outputting the best path and some statistics

The journey begins, as Katia’s did, in Saisio. The algorithm tries to reach an unvisited system in as few jumps as possible. The only flexibility in this approach is choosing the warp gate when multiple candidates lead to unvisited systems. If no suitable gate is found at the current location, the search field expands step by step. If it remains unsuccessful here, it follows the path system by system back and searches the predecessors for remaining systems. This ensures that all 5201 systems can be flown by the end.

In the initial approach, the warp gate was chosen purely at random. In the next attempt, gates of the same constellation should be preferred. The idea is that stars in New Eden are arranged in constellations. While systems within a constellation often have many connections, routes between constellations are rarer and represent bottlenecks. In the third attempt, systems with fewer connections should be visited first. The idea is that stars with many gates represent hubs that must be flown through sooner or later. As a fourth step, the two previous methods should be combined. The final optimization attempt was to not only consider the number of gates but also check whether the systems they lead to have already been visited.

All Roads Lead to Itamo #

Each approach was executed thousands of times, with about one second per attempt. Which brings us finally to what EVE players, aka “Spreadsheet Simulator” players, like to read most: Statistics! First, a comparison of the different approaches:

It looks like the optimizations actually optimized something. At least a path length of under 8000 jumps doesn’t sound bad. Let’s look at which systems were visited most.

Right at the top are systems that connect multiple dead ends to the rest of the galaxy. The leader Itamo is a prime example here. What’s surprising is that the algorithm apparently decided a few times to visit it more than six times. In contrast, 1366 systems were visited more than once in none of the runs. For comparison, along for the ride: The famous trading hub Jita. Even though it has seven gates, it was visited on average less than twice.

After about 20,000 attempts, the best result was a path with 7825 jumps. It’s of course not inconceivable that with a few more runs (or further logic optimizations) a better route can be found. The ultimate comparison is of course with our heroine’s route herself: Katia published the order of the systems she visited. However, only the newly visited systems are recorded here. If you fill the gaps with the necessary jumps, you get a route of at least 8217 stars. According to our results, Katia could have done it in almost 400 fewer jumps. But apart from the fact that she probably had other things to do along the way: What are 400 stars for someone who has seen an entire galaxy?

All EVE Online related materials are the property of CCP Games