Scout Optimizer: Solving the Traveling Salesman Problem in Space

Published October 15, 2025 • 10 min read

Scouts in EVE Frontier face a unique challenge: visiting multiple star systems efficiently. Unlike simple point-to-point navigation, scout routes require visiting 5, 10, or even 20 systems in a single expedition. Finding the optimal order to visit them is a classic computer science problem—and one that becomes exponentially harder as you add more waypoints.

Here's how we built EF-Map's Scout Optimizer to solve this problem in real-time.

The Problem: Traveling Salesman in Space

The Traveling Salesman Problem (TSP) asks: "Given a list of cities and the distances between them, what is the shortest possible route that visits each city exactly once?"

This problem is NP-hard, meaning there's no known algorithm that can solve it perfectly in polynomial time. For 10 systems, there are 3.6 million possible routes. For 20 systems? 2.4 quintillion routes.

Brute-forcing the answer isn't an option.

Our challenge: Find a "good enough" route in under 2 seconds that users can trust for real gameplay.

The Algorithm: Genetic Optimization

We chose a genetic algorithm approach combined with spatial grid optimization to balance speed and solution quality.

Why Genetic Algorithms?

Genetic algorithms mimic natural selection:

1. Generate a population of random routes
2. Evaluate each route's fitness (total distance)
3. Select the best routes to "reproduce"
4. Create offspring by combining parts of parent routes
5. Add random mutations to explore new solutions
6. Repeat for N generations

This approach doesn't guarantee the perfect route, but it consistently finds routes within 5-10% of optimal in a fraction of the time.

Population Size and Generations

After extensive testing, we settled on:

• Population size: 100 routes
• Generations: 50 iterations
• Elite preservation: Keep top 10% unchanged each generation
• Mutation rate: 15% chance to swap two waypoints

These parameters balance solution quality with computation time. On average, the algorithm runs in 800-1200ms for 15 waypoints.

Spatial Grid Optimization

Before running the genetic algorithm, we pre-compute a spatial grid to accelerate neighbor lookups.

The Problem with Naive Distance Calculations

Calculating distances between all pairs of systems is expensive:

For N systems: N × (N-1) / 2 distance calculations
For 20 systems: 190 calculations
For 50 systems: 1,225 calculations

Repeated across 50 generations and 100 population members, this becomes a bottleneck.

The Solution: Spatial Hashing

We divide the map into a 3D grid of cells. Each system belongs to one cell based on its coordinates:

const CELL_SIZE = 50; // lightyears

const getCellKey = (x, y, z) => {
  const cellX = Math.floor(x / CELL_SIZE);
  const cellY = Math.floor(y / CELL_SIZE);
  const cellZ = Math.floor(z / CELL_SIZE);
  return `${cellX},${cellY},${cellZ}`;
};

When calculating the distance from system A to system B, we only check:

• Systems in A's cell
• Systems in A's 26 neighboring cells

This reduces the search space dramatically. For a map with 1,000 systems, we might only check 20-30 candidates instead of all 1,000.

Performance impact: Distance lookups went from O(N) to O(1) average case.

Route Crossover Strategies

Creating "offspring" routes requires combining two parent routes without duplicating waypoints. We use Ordered Crossover (OX):

const crossover = (parent1, parent2) => {
  // Select a random segment from parent1
  const start = randomInt(0, parent1.length);
  const end = randomInt(start + 1, parent1.length);
  
  const segment = parent1.slice(start, end);
  const offspring = new Array(parent1.length);
  
  // Copy segment to offspring
  for (let i = start; i < end; i++) {
    offspring[i] = segment[i - start];
  }
  
  // Fill remaining positions from parent2 (in order, skipping duplicates)
  let p2Index = 0;
  for (let i = 0; i < offspring.length; i++) {
    if (offspring[i] === undefined) {
      while (segment.includes(parent2[p2Index])) {
        p2Index++;
      }
      offspring[i] = parent2[p2Index];
      p2Index++;
    }
  }
  
  return offspring;
};

This preserves relative ordering from both parents while avoiding duplicate waypoints.

Mutation: Escaping Local Optima

Without mutation, the algorithm can get stuck in local optima—routes that are better than their neighbors but not globally optimal.

We use swap mutation: randomly select two waypoints and exchange their positions.

const mutate = (route, mutationRate = 0.15) => {
  if (Math.random() > mutationRate) return route;
  
  const i = randomInt(0, route.length);
  const j = randomInt(0, route.length);
  
  [route[i], route[j]] = [route[j], route[i]];
  return route;
};

This simple operation occasionally produces dramatic improvements by breaking up inefficient route segments.

Handling Special Constraints

EVE Frontier's navigation has unique considerations beyond pure distance:

1. Fuel Costs vs. Jump Counts

Should we optimize for:

• Shortest total distance (minimize fuel consumption)?
• Fewest jumps (minimize time)?

We let users choose via a toggle. The algorithm adapts by changing the cost function:

const calculateCost = (route, optimizeFor) => {
  if (optimizeFor === 'fuel') {
    // Sum of direct distances between waypoints
    return route.reduce((sum, system, i) => {
      if (i === 0) return 0;
      return sum + distance(route[i - 1], system);
    }, 0);
  } else {
    // Count jumps via pathfinding (respects stargates)
    return route.reduce((sum, system, i) => {
      if (i === 0) return 0;
      const path = findPath(route[i - 1], system);
      return sum + path.length;
    }, 0);
  }
};

2. Start/End Points

Users can lock specific systems as the start or end of their route. The algorithm respects these constraints by:

• Fixing those positions in all generated routes
• Only mutating/crossing over the unlocked waypoints

3. Smart Gate Access

Some routes require avoiding restricted Smart Gates. We integrate with EF-Map's gate access snapshot to filter valid paths during cost calculation.

Performance Optimizations

Running genetic algorithms in the browser requires careful optimization:

Web Workers

We offload the entire optimization to a Web Worker to keep the UI responsive:

// Main thread
const worker = new Worker('/workers/scout_optimizer_worker.js');
worker.postMessage({ waypoints, settings });

worker.onmessage = (e) => {
  displayOptimizedRoute(e.data.route);
};

Caching

We cache spatial grids and neighbor lookups based on parameters:

const spatialGrids = new Map();

const getOrCreateGrid = (systems, cellSize) => {
  const key = `${systems.length}-${cellSize}`;
  if (!spatialGrids.has(key)) {
    spatialGrids.set(key, buildSpatialGrid(systems, cellSize));
  }
  return spatialGrids.get(key);
};

Incremental Updates

If a user adds a single waypoint to an existing route, we don't recompute from scratch:

const incrementalOptimize = (existingRoute, newWaypoint) => {
  // Try inserting newWaypoint at each position
  let bestRoute = null;
  let bestCost = Infinity;
  
  for (let i = 0; i <= existingRoute.length; i++) {
    const candidate = [
      ...existingRoute.slice(0, i),
      newWaypoint,
      ...existingRoute.slice(i)
    ];
    
    const cost = calculateCost(candidate);
    if (cost < bestCost) {
      bestCost = cost;
      bestRoute = candidate;
    }
  }
  
  return bestRoute;
};

Results and User Feedback

Since launching the Scout Optimizer:

• Average route improvement: 22% shorter than user-manual ordering
• Optimization time: 950ms median for 12 waypoints
• User satisfaction: 4.7/5 rating (from in-app feedback)

Most impressive result: A user planning a 28-waypoint expedition saw a 38% distance reduction compared to their manual route. That's multiple hours saved in-game.

Edge Cases and Failures

No algorithm is perfect. We've encountered several interesting edge cases:

Cluster Imbalance

If waypoints form two distant clusters, the algorithm sometimes "zig-zags" between them inefficiently. We added cluster detection to handle this:

const detectClusters = (waypoints) => {
  // Use k-means clustering (k=2) to identify groups
  const clusters = kMeans(waypoints, 2);
  
  // If clusters are well-separated, optimize each independently
  if (clusterSeparation(clusters) > THRESHOLD) {
    const route1 = optimizeRoute(clusters[0]);
    const route2 = optimizeRoute(clusters[1]);
    return [...route1, ...route2]; // Or connect with shortest bridge
  }
  
  return null; // Fall back to standard optimization
};

Premature Convergence

Early versions would occasionally converge too quickly, missing better solutions. We fixed this by:

• Increasing mutation rate from 10% to 15%
• Adding "fitness diversity" bonus (reward routes that differ from the population average)

Pathfinding Timeout

For extremely dense route graphs, A* pathfinding between some waypoints could timeout. We now:

• Use bidirectional search for distant waypoints
• Cache previously computed paths
• Fall back to straight-line distance if pathfinding exceeds 500ms

Try the Scout Optimizer

Plan your next EVE Frontier expedition with intelligent route optimization. Open EF-Map's Scout Optimizer →

Future Improvements

We're exploring several enhancements:

1. Multi-objective optimization: Balance fuel, time, and danger zones simultaneously
2. Dynamic waypoints: Suggest additional systems to visit based on resources or POIs
3. Fleet coordination: Optimize routes for multiple scouts splitting duties
4. Learning from history: Adapt to user preferences over time

Related Posts

• Three.js Rendering: Building a 3D Starfield for 200,000 Systems - The rendering engine that visualizes optimized routes in 3D space
• Route Sharing: Building a URL Shortener for Spatial Navigation - How we compress and share optimized routes with corpmates
• Database Architecture: From Blockchain Events to Queryable Intelligence - The spatial indexing that powers fast neighbor lookups in the genetic algorithm

---

EF-Map is an open-source interactive map for EVE Frontier. Optimize your scout routes at ef-map.com or explore the source code on GitHub.