Exploration Mode: Real-Time Pathfinding Visualization

Watching an algorithm think is mesmerizing. When we built bidirectional Dijkstra for EVE Frontier Map, we realized we could visualize the search in real-time—showing users exactly how the pathfinding algorithm explores the galaxy to find their route.

The Concept

Standard pathfinding shows you the input (origin, destination) and output (route). But the process—thousands of systems being evaluated, frontiers expanding, dead ends being abandoned—that's invisible. Exploration Mode makes it visible.

When enabled, you see:

• Forward frontier (blue): Systems explored from origin
• Backward frontier (orange): Systems explored from destination
• Meeting point (green): Where the frontiers connect
• Final path (white): The optimal route

Technical Architecture

The challenge: our pathfinding runs in a Web Worker to avoid blocking the UI. We needed to stream intermediate state from the worker to the main thread for rendering.

Worker-Side: VisitedNode Batching

Sending a message for every visited node would flood the message channel. Instead, we batch nodes and emit them periodically:

// routing_worker.ts
interface VisitedNode {
  systemId: number;
  x: number;
  y: number;
  z: number;
  direction: 'forward' | 'backward';
  timestamp: number;
}

const BATCH_SIZE = 50;
const EMIT_INTERVAL = 100; // ms

let visitedBatch: VisitedNode[] = [];
let lastEmit = 0;

function recordVisited(node: VisitedNode) {
  visitedBatch.push(node);
  
  const now = performance.now();
  if (visitedBatch.length >= BATCH_SIZE || now - lastEmit > EMIT_INTERVAL) {
    postMessage({
      type: 'visited',
      nodes: visitedBatch,
    });
    visitedBatch = [];
    lastEmit = now;
  }
}

Main Thread: Temporal Rendering

Received nodes are rendered as small spheres with a timestamp. The animation loop fades them based on age:

// App.tsx animation loop
const FADE_DURATION = 5000; // 5 seconds

visitedNodes.forEach((node, index) => {
  const age = now - node.timestamp;
  
  if (age > FADE_DURATION) {
    // Remove expired node
    scene.remove(node.mesh);
    visitedNodes.splice(index, 1);
    return;
  }
  
  // Fade opacity based on age
  const opacity = 1 - (age / FADE_DURATION);
  node.mesh.material.opacity = opacity;
  
  // Color based on search direction
  const color = node.direction === 'forward' 
    ? new THREE.Color(0x4a90d9)  // Blue
    : new THREE.Color(0xd97b4a); // Orange
  node.mesh.material.color = color;
});

Performance Optimizations

Rendering 10,000+ transient spheres is expensive. We applied several optimizations:

1. Instanced Meshes

Instead of individual THREE.Mesh objects, we use THREE.InstancedMesh:

// Create instanced geometry once
const geometry = new THREE.SphereGeometry(0.5, 8, 8);
const material = new THREE.MeshBasicMaterial({ transparent: true });
const instancedMesh = new THREE.InstancedMesh(geometry, material, MAX_VISIBLE_NODES);

// Update instance matrix for each node
const matrix = new THREE.Matrix4();
visitedNodes.forEach((node, i) => {
  matrix.setPosition(node.x, node.y, node.z);
  instancedMesh.setMatrixAt(i, matrix);
});
instancedMesh.instanceMatrix.needsUpdate = true;

2. Distance Culling

Don't render nodes that are too far from the camera:

const MAX_RENDER_DISTANCE = 500; // light-years

visitedNodes.forEach(node => {
  const distance = camera.position.distanceTo(node.position);
  node.mesh.visible = distance < MAX_RENDER_DISTANCE;
});

3. Throttled Updates

The worker batches at 100ms intervals. We further throttle rendering updates to match the display refresh rate:

let lastRenderUpdate = 0;
const RENDER_THROTTLE = 16; // ~60fps

function onWorkerMessage(event) {
  if (event.data.type === 'visited') {
    pendingNodes.push(...event.data.nodes);
  }
}

// In animation loop
const now = performance.now();
if (now - lastRenderUpdate > RENDER_THROTTLE) {
  processPendingNodes();
  lastRenderUpdate = now;
}

Visual Design Decisions

Why 5-Second Fade?

We tested various durations:

Why Blue and Orange?

Color-blindness considerations: blue vs. orange is distinguishable by most people with color vision deficiencies (unlike red/green). The colors are also semantically intuitive—blue is "cool" (origin), orange is "warm" (destination/goal).

Meeting Point Highlight

When the bidirectional frontiers meet, we briefly highlight the connection point with a green pulse. This shows users the moment the algorithm "knows" it has found a path:

// When frontiers meet
if (forwardVisited.has(currentNode) && backwardVisited.has(currentNode)) {
  postMessage({
    type: 'meeting_point',
    systemId: currentNode,
    x: systems[currentNode].x,
    y: systems[currentNode].y,
    z: systems[currentNode].z,
  });
}

User Controls

Exploration Mode is toggled via a checkbox in the Routing panel. When enabled:

• Route calculation takes ~10-20% longer (worker batching overhead)
• Memory usage increases (~5MB for a cross-galaxy route)
• GPU load increases (rendering transient nodes)

We warn users on lower-end devices and auto-disable if frame rate drops below 30fps.

Educational Value

Exploration Mode has unexpected educational benefits:

• Why routes aren't straight lines: Users see the algorithm respecting jump range constraints
• Gate network topology: Dense regions light up faster than sparse ones
• Bidirectional efficiency: Visible comparison of forward-only vs. meeting-in-middle
• Smart Gate impact: Player-built gates create shortcuts visible in the exploration pattern

Related Posts

• Smart Gate Routing: Bidirectional Dijkstra - The algorithm being visualized
• Web Workers: Background Computation - How we keep the UI responsive during search
• Jump Bubble Visualization: Thin-Film Shaders - Another visual effect for spatial understanding
• A* vs Dijkstra: Algorithm Comparison - Why we chose Dijkstra for exploration visualization