← Back to Blog
Technical Deep Dive 2025-09-21 9 min read

A* vs Dijkstra: Choosing the Right Pathfinding Algorithm for EVE Frontier

When you calculate a route in EF-Map, you're triggering one of two pathfinding algorithms under the hood: A* (A-star) or Dijkstra's algorithm. Both find the shortest path between star systems, but they do it in fundamentally different ways—and understanding the difference can help you choose the right tool for your navigation needs.

This post breaks down how these algorithms work, when to use each one, and why we implemented both in EF-Map instead of picking a single "best" option.

The Problem: Finding Paths in a Graph

EVE Frontier's star map is a graph: systems are nodes, stargates and wormholes are edges. When you want to travel from System A to System Z, the pathfinding algorithm explores this graph to find the optimal route.

But "optimal" can mean different things:

Both A* and Dijkstra can handle these scenarios, but their performance characteristics differ dramatically.

Dijkstra's Algorithm: The Exhaustive Explorer

Dijkstra's algorithm is the older, more straightforward approach. It explores the graph systematically, expanding outward from the starting system like a wavefront: 

function dijkstra(start: System, goal: System): Path {
    const distances = new Map<System, number>();
    const previous = new Map<System, System>();
    const unvisited = new Set<System>(allSystems);
    
    distances.set(start, 0);
    
    while (unvisited.size > 0) {
        // Find unvisited system with smallest distance
        const current = findMin(unvisited, distances);
        
        if (current === goal) {
            return reconstructPath(previous, goal);
        }
        
        unvisited.delete(current);
        
        // Update distances to neighbors
        for (const neighbor of getNeighbors(current)) {
            const altDistance = distances.get(current) + cost(current, neighbor);
            
            if (altDistance < distances.get(neighbor)) {
                distances.set(neighbor, altDistance);
                previous.set(neighbor, current);
            }
        }
    }
}

How Dijkstra Works

  1. Start at the source system with distance 0
  2. Explore all neighboring systems, calculating their distance from source
  3. Always expand the closest unexplored system next
  4. Repeat until you reach the goal (or explore the entire graph)

The key insight: Dijkstra guarantees the shortest path by exploring systems in order of their distance from the start. Once you reach the goal, you know you've found the optimal route—there's no shorter path left to discover.

Dijkstra Strengths

Dijkstra Weaknesses

For a route from one side of New Eden to the other (200+ jumps), Dijkstra might explore 50,000+ systems before finding the goal—most of them completely irrelevant to the final path.

A* (A-Star): The Informed Navigator

A* algorithm is Dijkstra's smarter cousin. It uses a heuristic (educated guess) to bias exploration toward the goal, dramatically reducing wasted computation: 

function aStar(start: System, goal: System): Path {
    const gScore = new Map<System, number>(); // Distance from start
    const fScore = new Map<System, number>(); // gScore + heuristic to goal
    const previous = new Map<System, System>();
    const openSet = new PriorityQueue<System>();
    
    gScore.set(start, 0);
    fScore.set(start, heuristic(start, goal));
    openSet.enqueue(start, fScore.get(start));
    
    while (!openSet.isEmpty()) {
        const current = openSet.dequeue();
        
        if (current === goal) {
            return reconstructPath(previous, goal);
        }
        
        for (const neighbor of getNeighbors(current)) {
            const tentativeGScore = gScore.get(current) + cost(current, neighbor);
            
            if (tentativeGScore < gScore.get(neighbor)) {
                previous.set(neighbor, current);
                gScore.set(neighbor, tentativeGScore);
                fScore.set(neighbor, tentativeGScore + heuristic(neighbor, goal));
                
                if (!openSet.contains(neighbor)) {
                    openSet.enqueue(neighbor, fScore.get(neighbor));
                }
            }
        }
    }
}

The Magic: The Heuristic Function

A* works because of its heuristic function h(n), which estimates the cost from any system to the goal: 

function heuristic(system: System, goal: System): number {
    // Straight-line distance (Euclidean distance in 3D space)
    const dx = system.x - goal.x;
    const dy = system.y - goal.y;
    const dz = system.z - goal.z;
    return Math.sqrt(dx * dx + dy * dy + dz * dz);
}

This heuristic tells A: "You're currently 150 light-years from the goal as the crow flies." A uses this to prioritize systems that move you closer to the goal, ignoring systems in the wrong direction.

A* Strengths

A* Weaknesses

Real-World Performance Comparison

We benchmarked both algorithms on typical EF-Map routes:

Short Routes (5-10 jumps)

Medium Routes (20-40 jumps)

Long Routes (100+ jumps)

For the routes most players calculate (20-50 jumps), A* is dramatically faster—finishing in the time it takes Dijkstra to warm up.

When to Use Each Algorithm

Use Dijkstra When:

  1. Finding all paths from a source: If you want distances to every system from a starting point, Dijkstra is perfect. We use it for the "Show systems within X jumps" feature.
  1. The graph is small: For tiny subgraphs (<100 systems), Dijkstra's simplicity beats A*'s overhead.
  1. No good heuristic exists: If you can't estimate distance to the goal, Dijkstra is your only option.
  1. Debugging: Dijkstra's exhaustive exploration makes it easier to verify correctness.

Use A* When:

  1. Point-to-point routing: Single source to single destination—A*'s bread and butter.
  1. Large graphs: The bigger the graph, the more A shines. EVE Frontier's 200k systems? A all day.
  1. You have a good heuristic: Straight-line distance works great for spatial graphs like star maps.
  1. Performance matters: If users expect sub-100ms response times, A* is essential.

Implementation Details: EF-Map's Routing Engine

In EF-Map, we default to A* for all point-to-point routing but expose Dijkstra as an option for power users: 

interface RoutingOptions {
    algorithm: 'astar' | 'dijkstra';
    optimizeFor: 'jumps' | 'distance' | 'safety';
    maxJumps?: number;
    avoidSystems?: Set<string>;
}

export function findPath(
    start: System,
    goal: System,
    options: RoutingOptions
): Path {
    if (options.algorithm === 'dijkstra') {
        return dijkstraSearch(start, goal, options);
    } else {
        return aStarSearch(start, goal, options);
    }
}

Optimizing A* for EVE Frontier

We made several enhancements to vanilla A*:

1. Spatial Grid Acceleration

Instead of searching all neighbors linearly, we use a spatial grid: 

const CELL_SIZE = 50; // light-years
const spatialGrid = new Map<string, System[]>();

function getCellKey(system: System): string {
    const cx = Math.floor(system.x / CELL_SIZE);
    const cy = Math.floor(system.y / CELL_SIZE);
    const cz = Math.floor(system.z / CELL_SIZE);
    return `${cx},${cy},${cz}`;
}

function getNeighbors(system: System): System[] {
    const cellKey = getCellKey(system);
    return spatialGrid.get(cellKey) || [];
}

This reduces neighbor lookup from O(n) to O(1) for typical cases.

2. Jump Range Constraints

Many ships can't jump more than 6-8 light-years. We pre-filter neighbors: 

function getReachableNeighbors(system: System, maxJumpRange: number): System[] {
    return getNeighbors(system).filter(neighbor => {
        const distance = calculateDistance(system, neighbor);
        return distance <= maxJumpRange;
    });
}

3. Bidirectional Search

For very long routes, we search from both ends simultaneously: 

function bidirectionalAStar(start: System, goal: System): Path {
    const forwardSearch = initAStar(start, goal);
    const backwardSearch = initAStar(goal, start);
    
    while (true) {
        forwardSearch.step();
        backwardSearch.step();
        
        // Check if searches met
        const meeting = findIntersection(forwardSearch, backwardSearch);
        if (meeting) {
            return mergePaths(forwardSearch.pathTo(meeting), backwardSearch.pathTo(meeting));
        }
    }
}

This can cut exploration by another 50% for ultra-long routes.

Edge Cases and Gotchas

Heuristic Admissibility

A*'s optimality guarantee requires an admissible heuristic—one that never overestimates. For EVE Frontier: 

// ✅ Admissible: straight-line distance is always ≤ actual path distance
function goodHeuristic(a: System, b: System): number {
    return euclideanDistance(a, b);
}

// ❌ Not admissible: could overestimate if we multiply
function badHeuristic(a: System, b: System): number {
    return euclideanDistance(a, b) * 1.5; // Breaks A* optimality!
}

Negative Edge Weights

Both algorithms assume non-negative edge weights. If you model "danger" as negative cost (rewards), they break. Use positive costs instead: 

// ❌ Broken
const cost = baseDistance - (dangerLevel * 10); // Can go negative!

// ✅ Correct
const cost = baseDistance + (dangerLevel * 10); // Always positive

Dynamic Graphs

When Smart Gates open/close or wormholes shift, the graph changes. We invalidate cached paths: 

let pathCache = new Map<string, Path>();

function onGateStatusChange(gateId: string) {
    pathCache.clear(); // Invalidate all cached paths
}

Visualizing the Difference

If you enable "Debug Mode" in EF-Map, you can see the algorithms in action:

The difference is striking on long routes—Dijkstra floods the entire graph, while A* carves a narrow corridor straight to the destination.

Future: Beyond A* and Dijkstra

We're exploring even faster algorithms for special cases:

But for now, A* and Dijkstra cover 99% of use cases beautifully.

Try It Yourself

Open EF-Map's Routing panel and toggle "Algorithm: A" vs "Algorithm: Dijkstra" while calculating a long route. Watch the exploration counter—A will explore far fewer systems. For most navigation, A* is the clear winner, but understanding both algorithms makes you a better navigator in New Eden.

Related Posts

algorithmspathfindinga-stardijkstragraph theoryrouting