Smart Gate Routing: Bidirectional Dijkstra and Gate Directionality

When your pathfinding algorithm suggests a route through a one-way gate—in the wrong direction—you have a problem. This is the story of how we optimized EVE Frontier Map's routing with bidirectional Dijkstra search, then discovered and fixed a subtle bug where Smart Gates (player-built warp structures) were being traversed backwards.

The Performance Problem

EVE Frontier's universe contains over 24,000 star systems. When a player asks for a fuel-optimized route, our Dijkstra implementation would explore outward from the origin until it reached the destination. For cross-galaxy routes, this meant visiting tens of thousands of systems—taking 5-30 seconds.

The solution is well-known in computer science: bidirectional search. Instead of searching from just the origin, we simultaneously search from the destination. When the two search frontiers meet, we've found the optimal path—having explored roughly half the nodes from each direction.

Implementing Bidirectional Dijkstra

The core idea is simple: maintain two priority queues (MinHeaps) and alternate between them:

// Two frontiers expanding toward each other
const forwardHeap = new MinHeap();  // From origin
const backwardHeap = new MinHeap(); // From destination

forwardHeap.push(origin, 0);
backwardHeap.push(destination, 0);

while (!forwardHeap.isEmpty() && !backwardHeap.isEmpty()) {
  // Alternate between frontiers
  if (forwardHeap.peekPriority() <= backwardHeap.peekPriority()) {
    expandForward();
  } else {
    expandBackward();
  }
  
  // Check termination: have frontiers met?
  if (meetingPointFound) break;
}

The tricky part is termination. You can't stop as soon as both frontiers have visited the same node—you need to ensure no better path exists. The correct condition is:

// Terminate when the sum of frontier minimums exceeds best known path
if (forwardHeap.peekPriority() + backwardHeap.peekPriority() >= bestPathCost) {
  // No better path can exist
  break;
}

The MinHeap Foundation

Our original implementation used a naive priority queue that sorted the entire array on every insert—O(n log n) per operation. We replaced it with a proper binary heap:

For a 24,000-system search with ~50,000 heap operations, this change alone provided a significant speedup.

The Directionality Bug

With bidirectional search working, we deployed to preview and tested routes. Everything looked great—until a player reported an impossible route suggestion. The path included a Smart Gate that could only be traversed from A to B, but our route had the player going from B to A.

The bug was subtle. When the backward search (expanding from destination) found a Smart Gate neighbor, it was using the same adjacency lookup as the forward search. It asked "who can I reach from here?" when it should have asked "who can reach me?"

The Fix: Dual Adjacency Maps

We now build two separate adjacency maps for Smart Gates:

// Forward adjacency: smartAdj[a] = [b] means you can go FROM a TO b
const smartAdj = new Map<number, number[]>();

// Reverse adjacency: smartAdjReverse[b] = [a] means you can go TO b FROM a
const smartAdjReverse = new Map<number, number[]>();

// Build both maps from gate link data
for (const link of smartGateLinks) {
  // Forward: from origin to destination
  if (!smartAdj.has(link.origin)) smartAdj.set(link.origin, []);
  smartAdj.get(link.origin)!.push(link.destination);
  
  // Reverse: indexed by destination, points to origins
  if (!smartAdjReverse.has(link.destination)) smartAdjReverse.set(link.destination, []);
  smartAdjReverse.get(link.destination)!.push(link.origin);
}

The getNeighbors() function now accepts an isBackwardSearch flag:

function getNeighbors(systemId, smartAdj, smartAdjReverse, isBackward) {
  const neighbors = [];
  
  // Regular stargates are always bidirectional
  neighbors.push(...regularGateNeighbors);
  
  // Smart Gates depend on search direction
  if (isBackward) {
    // "Who can reach me?" - use reverse adjacency
    neighbors.push(...(smartAdjReverse.get(systemId) || []));
  } else {
    // "Who can I reach?" - use forward adjacency
    neighbors.push(...(smartAdj.get(systemId) || []));
  }
  
  return neighbors;
}

Cache Key Poisoning

We also discovered a cache pollution issue. The neighbor cache was keyed only by system ID, not by search direction. This meant a forward search's cached neighbors could be incorrectly reused by the backward search.

The fix was simple: include direction in the cache key:

const cacheKey = `${systemId}:${isBackward ? 'bwd' : 'fwd'}`;

Early Termination for Impossible Routes

Another optimization: detecting impossible routes quickly. Before running full Dijkstra, we now perform a fast BFS check using existsPathWithin(). If no path exists at the current ship range, we use binary search (7 iterations) to find the minimum required range and return immediately with a helpful message.

// Quick reachability check before expensive pathfinding
if (!existsPathWithin(origin, destination, maxJumpRange)) {
  const minRequired = computeMinRequiredRange(origin, destination);
  return {
    success: false,
    minRequiredShipRange: minRequired,
    message: `No path exists. Minimum ship range needed: ${minRequired} LY`
  };
}

Results

The combination of MinHeap, bidirectional search, early termination, and proper gate directionality handling makes EVE Frontier Map's routing both faster and correct.

Lessons Learned

1. Bidirectional search doubles complexity: Every edge traversal now needs direction awareness. Plan for this upfront.
2. Caches need complete keys: Any memoization must account for all parameters that affect the result.
3. Test with real data: The directionality bug only surfaced with actual player-created asymmetric gates.
4. Fail fast, fail informatively: Detecting impossible routes early with a helpful message is better than a 30-second timeout.

Related Posts

• A* vs Dijkstra: Choosing the Right Pathfinding Algorithm - When to use each algorithm and why we support both
• Web Workers: Keeping the UI Responsive - How we run pathfinding off the main thread
• Smart Gate Authorization: Blockchain-Powered Access Control - How Smart Gate permissions work on-chain
• Exploration Mode: Real-Time Pathfinding Visualization - Visualizing the search as it happens