Pathfinding

Overview

OpenFront implements multiple pathfinding algorithms optimized for different terrain types and use cases. The system is built around a flexible adapter pattern that allows different algorithms to be composed with transformers for enhanced functionality.

Architecture

The pathfinding system is organized into several layers:

Algorithms: Core pathfinding implementations (A*, BFS, Hierarchical)
PathFinders: Domain-specific pathfinding interfaces
Transformers: Composable path enhancement layers
Steppers: Animated path traversal for UI

PathFinder Interface

All pathfinding algorithms implement a common interface:

interface PathFinder<T> {
  findPath(start: T | T[], goal: T): T[] | null;
}

start

T | T[]

Starting position(s). Multiple starts enable multi-source pathfinding.

goal

Target destination position.

returns

T[] | null

Array of positions forming the path, or null if no path exists.

A* Algorithm

The core A* implementation uses an adapter pattern for flexibility:

src/core/pathfinding/algorithms/AStar.ts

export interface AStarAdapter {
  neighbors(node: number, buffer: Int32Array): number;
  cost(from: number, to: number, prev?: number): number;
  heuristic(node: number, goal: number): number;
  numNodes(): number;
  maxPriority(): number;
  maxNeighbors(): number;
}

export class AStar implements PathFinder<number> {
  private stamp = 1;
  private readonly closedStamp: Uint32Array;
  private readonly gScoreStamp: Uint32Array;
  private readonly gScore: Uint32Array;
  private readonly cameFrom: Int32Array;
  private readonly queue: PriorityQueue;
  private readonly adapter: AStarAdapter;
  private readonly neighborBuffer: Int32Array;
  private readonly maxIterations: number;

  constructor(config: AStarConfig) {
    this.adapter = config.adapter;
    this.maxIterations = config.maxIterations ?? 500_000;
    this.neighborBuffer = new Int32Array(this.adapter.maxNeighbors());
    this.closedStamp = new Uint32Array(this.adapter.numNodes());
    this.gScoreStamp = new Uint32Array(this.adapter.numNodes());
    this.gScore = new Uint32Array(this.adapter.numNodes());
    this.cameFrom = new Int32Array(this.adapter.numNodes());
    this.queue = new BucketQueue(this.adapter.maxPriority());
  }

  findPath(start: number | number[], goal: number): number[] | null {
    this.stamp++;
    if (this.stamp > 0xffffffff) {
      this.closedStamp.fill(0);
      this.gScoreStamp.fill(0);
      this.stamp = 1;
    }

    const stamp = this.stamp;
    // ... initialization

    queue.clear();
    const starts = Array.isArray(start) ? start : [start];
    for (const s of starts) {
      gScore[s] = 0;
      gScoreStamp[s] = stamp;
      cameFrom[s] = -1;
      queue.push(s, adapter.heuristic(s, goal));
    }

    let iterations = this.maxIterations;

    while (!queue.isEmpty()) {
      if (--iterations <= 0) {
        return null;
      }

      const current = queue.pop();

      if (closedStamp[current] === stamp) continue;
      closedStamp[current] = stamp;

      if (current === goal) {
        return this.buildPath(goal);
      }

      const currentG = gScore[current];
      const prev = cameFrom[current];
      const count = adapter.neighbors(current, buffer);

      for (let i = 0; i < count; i++) {
        const neighbor = buffer[i];
        if (closedStamp[neighbor] === stamp) continue;

        const tentativeG = currentG + adapter.cost(current, neighbor, prev);

        if (gScoreStamp[neighbor] !== stamp || tentativeG < gScore[neighbor]) {
          cameFrom[neighbor] = current;
          gScore[neighbor] = tentativeG;
          gScoreStamp[neighbor] = stamp;
          queue.push(neighbor, tentativeG + adapter.heuristic(neighbor, goal));
        }
      }
    }

    return null;
  }
}

Performance Optimizations

The A* implementation uses several optimization techniques:

Stamping: Avoids array clearing by using generation stamps
Typed Arrays: Uses Int32Array/Uint32Array for cache-friendly access
Buffer Reuse: Neighbor buffer allocated once, reused across searches
Bucket Queue: O(1) priority queue for integer priorities

Breadth-First Search (BFS)

BFS is used for unweighted searches and area exploration:

src/core/pathfinding/algorithms/BFS.ts

export interface BFSAdapter<T> {
  neighbors(node: T): T[];
}

export class BFS<T> {
  constructor(private adapter: BFSAdapter<T>) {}

  search<R>(
    start: T | T[],
    maxDistance: number,
    visitor: (node: T, dist: number) => R | null | undefined,
  ): R | null {
    const visited = new Set<T>();
    const queue: { node: T; dist: number }[] = [];
    const starts = Array.isArray(start) ? start : [start];

    for (const s of starts) {
      visited.add(s);
      queue.push({ node: s, dist: 0 });
    }

    while (queue.length > 0) {
      const { node, dist } = queue.shift()!;

      const result = visitor(node, dist);

      if (result !== null && result !== undefined) {
        return result;
      }

      if (result === null) {
        continue;
      }

      const nextDist = dist + 1;

      if (nextDist > maxDistance) {
        continue;
      }

      for (const neighbor of this.adapter.neighbors(node)) {
        if (visited.has(neighbor)) {
          continue;
        }

        visited.add(neighbor);
        queue.push({ node: neighbor, dist: nextDist });
      }
    }

    return null;
  }
}

Visitor Pattern

BFS uses a visitor pattern for flexible search termination:

Return R: Found target, return result immediately
Return undefined: Valid node, continue exploring
Return null: Invalid node, skip but continue search

PathFinding Factory

The PathFinding class provides convenient factory methods for different terrain types:

src/core/pathfinding/PathFinder.ts

export class PathFinding {
  static Water(game: Game): SteppingPathFinder<TileRef> {
    const pf = game.miniWaterHPA();
    const graph = game.miniWaterGraph();

    if (!pf || !graph || graph.nodeCount < 100) {
      return PathFinding.WaterSimple(game);
    }

    const miniMap = game.miniMap();
    const componentCheckFn = (t: TileRef) => graph.getComponentId(t);

    return PathFinderBuilder.create(pf)
      .wrap((pf) => new ComponentCheckTransformer(pf, componentCheckFn))
      .wrap((pf) => new SmoothingWaterTransformer(pf, miniMap))
      .wrap((pf) => new ShoreCoercingTransformer(pf, miniMap))
      .wrap((pf) => new MiniMapTransformer(pf, game.map(), miniMap))
      .buildWithStepper(tileStepperConfig(game));
  }

  static Rail(game: Game): SteppingPathFinder<TileRef> {
    const miniMap = game.miniMap();
    const pf = new AStarRail(miniMap);

    return PathFinderBuilder.create(pf)
      .wrap((pf) => new MiniMapTransformer(pf, game.map(), miniMap))
      .buildWithStepper(tileStepperConfig(game));
  }

  static Air(game: Game): SteppingPathFinder<TileRef> {
    const pf = new AirPathFinder(game);

    return PathFinderBuilder.create(pf).buildWithStepper({
      equals: (a, b) => a === b,
    });
  }

  static Stations(game: Game): SteppingPathFinder<TrainStation> {
    const pf = new StationPathFinder(game);

    return PathFinderBuilder.create(pf).buildWithStepper({
      equals: (a, b) => a.id === b.id,
      distance: (a, b) => game.manhattanDist(a.tile(), b.tile()),
    });
  }
}

Terrain-Specific Pathfinding

Water Pathfinding

Water pathfinding uses hierarchical pathfinding for large maps:

Component Check: Verifies start/goal are in same water body
Smoothing: Reduces path zigzagging
Shore Coercing: Keeps ships near coastlines when beneficial
Mini Map: Operates on downscaled map for performance

Hierarchical Pathfinding Algorithm (HPA*) divides the map into clusters with gateway nodes, dramatically reducing search space for long-distance paths.

Rail Pathfinding

Rail pathfinding operates on the rail network graph:

class AStarRail implements PathFinder<TileRef> {
  constructor(private miniMap: GameMap) {}

  findPath(start: TileRef, goal: TileRef): TileRef[] | null {
    // Only traverse tiles with rail infrastructure
    // Cost function accounts for rail type and connections
  }
}

Air Pathfinding

Air units use simplified pathfinding:

No terrain blocking: Can fly over any tile
Direct paths: Minimal pathfinding overhead
Range constraints: Limited by fuel/range

Path Transformers

Transformers wrap pathfinders to enhance functionality:

ComponentCheckTransformer

Early rejection for unreachable goals:

class ComponentCheckTransformer implements PathFinder<TileRef> {
  constructor(
    private inner: PathFinder<TileRef>,
    private getComponent: (t: TileRef) => number,
  ) {}

  findPath(start: TileRef, goal: TileRef): TileRef[] | null {
    if (this.getComponent(start) !== this.getComponent(goal)) {
      return null; // Different water bodies, no path possible
    }
    return this.inner.findPath(start, goal);
  }
}

SmoothingWaterTransformer

Reduces path zigzagging for more natural ship movement:

class SmoothingWaterTransformer implements PathFinder<TileRef> {
  constructor(
    private inner: PathFinder<TileRef>,
    private map: GameMap,
  ) {}

  findPath(start: TileRef, goal: TileRef): TileRef[] | null {
    const path = this.inner.findPath(start, goal);
    if (!path) return null;

    // Apply smoothing algorithm to reduce unnecessary turns
    return this.smoothPath(path);
  }
}

MiniMapTransformer

Maps between full resolution and downscaled pathfinding:

class MiniMapTransformer implements PathFinder<TileRef> {
  constructor(
    private inner: PathFinder<TileRef>,
    private fullMap: GameMap,
    private miniMap: GameMap,
  ) {}

  findPath(start: TileRef, goal: TileRef): TileRef[] | null {
    // Convert to mini map coordinates
    const miniStart = this.toMini(start);
    const miniGoal = this.toMini(goal);

    // Find path on mini map
    const miniPath = this.inner.findPath(miniStart, miniGoal);
    if (!miniPath) return null;

    // Convert back to full resolution
    return miniPath.map((t) => this.toFull(t));
  }
}

Mini maps are typically 4x-8x smaller than full maps, providing significant performance improvements for long-distance pathfinding.

Stepping PathFinders

Stepping pathfinders enable animated path traversal for UI:

interface SteppingPathFinder<T> extends PathFinder<T> {
  step(from: T, to: T): PathStep<T>;
}

type PathStep<T> = 
  | { status: PathStatus.FOUND; path: T[] }
  | { status: PathStatus.NOT_FOUND }
  | { status: PathStatus.IN_PROGRESS; next: T };

Usage Example

const pathfinder = PathFinding.Water(game);
let currentPos = startTile;

while (currentPos !== goalTile) {
  const step = pathfinder.step(currentPos, goalTile);
  
  if (step.status === PathStatus.FOUND) {
    // Path complete
    return step.path;
  } else if (step.status === PathStatus.IN_PROGRESS) {
    // Animate move to next position
    currentPos = step.next;
  } else {
    // No path found
    return null;
  }
}

Performance Considerations

Optimization Techniques

Stamp-based Visited Sets: Avoid clearing large arrays
Typed Arrays: Cache-friendly memory layout
Mini Maps: Reduce search space for long paths
Component Analysis: Early rejection of impossible paths
Buffer Reuse: Single allocation for neighbor queries

Iteration Limits

const maxIterations = 500_000;
let iterations = maxIterations;

while (!queue.isEmpty()) {
  if (--iterations <= 0) {
    return null; // Prevent infinite loops
  }
  // ... pathfinding logic
}

Iteration limits prevent pathfinding from hanging on extremely complex queries or bugs. For very large maps, the limit may need adjustment.

Game Loop - Pathfinding runs during tick execution
Intent/Execution - Movement executions use pathfinding
Alliances - Alliance members may share pathing information

Architecture

Game Systems

Map Generator

Overview

Architecture

PathFinder Interface

A* Algorithm

Performance Optimizations

Breadth-First Search (BFS)

Visitor Pattern

PathFinding Factory

Terrain-Specific Pathfinding

Water Pathfinding

Rail Pathfinding

Air Pathfinding

Path Transformers

ComponentCheckTransformer

SmoothingWaterTransformer

MiniMapTransformer

Stepping PathFinders

Usage Example

Performance Considerations

Optimization Techniques

Iteration Limits

Build docs developers (and LLMs) love

Architecture

Game Systems

Map Generator

Documentation Index

​Overview

​Architecture

​PathFinder Interface

​A* Algorithm

​Performance Optimizations

​Breadth-First Search (BFS)

​Visitor Pattern

​PathFinding Factory

​Terrain-Specific Pathfinding

​Water Pathfinding

​Rail Pathfinding

​Air Pathfinding

​Path Transformers

​ComponentCheckTransformer

​SmoothingWaterTransformer

​MiniMapTransformer

​Stepping PathFinders

​Usage Example

​Performance Considerations

​Optimization Techniques

​Iteration Limits

​Related Systems

Build docs developers (and LLMs) love

Overview

Architecture

PathFinder Interface

A* Algorithm

Performance Optimizations

Breadth-First Search (BFS)

Visitor Pattern

PathFinding Factory

Terrain-Specific Pathfinding

Water Pathfinding

Rail Pathfinding

Air Pathfinding

Path Transformers

ComponentCheckTransformer

SmoothingWaterTransformer

MiniMapTransformer

Stepping PathFinders

Usage Example

Performance Considerations

Optimization Techniques

Iteration Limits

Related Systems