# Pathfinding Tests

This directory contains benchmarking tools, scenario generators, and an interactive playground for testing and optimizing pathfinding algorithms in OpenFrontIO.

## TLDR

```bash
npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all
npx tsx tests/pathfinding/playground/server.ts
```

## Directory Structure

```
tests/pathfinding/
├── benchmark.ts          # Benchmarking tool
├── scenarios/            # Scenarios for benchmarks
│   ├── default.ts        # Hand-picked scenario
│   └── synthetic/        # Auto-generated synthetic scenarios
└── playground/           # Interactive web-based visualization
```

## Available algorithms

- **NavSat** - **future** implementation - NavigationSatellite (HPA\*)
- **PF.Mini** - **current** implementation - PathFinder.Mini (A\*)

## Benchmarking

### Running a Single Scenario

```bash
# Run default scenario with default adapter (NavSat)
npx tsx tests/pathfinding/benchmark/run.ts

# Run specific scenario
npx tsx tests/pathfinding/benchmark/run.ts default

# Run with specific adapter
npx tsx tests/pathfinding/benchmark/run.ts default legacy
```

### Running Synthetic Scenarios

Synthetic scenarios are auto-generated from maps with random port selections and routes.

```bash
# Run single synthetic scenario
npx tsx tests/pathfinding/benchmark/run.ts --synthetic iceland

# Run single synthetic scenario with specific adapter
npx tsx tests/pathfinding/benchmark/run.ts --synthetic iceland legacy

# Run ALL synthetic scenarios (comprehensive benchmark)
npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all

# Run all with specific adapter
npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all legacy
```

### Benchmark Metrics

The benchmark measures three key metrics:

1. **Initialization Time** - How long it takes to preprocess the map
2. **Path Distance** - Total distance across all routes (quality metric)
3. **Pathfinding Time** - How long it takes to compute paths (performance metric)

### Example Output

```
================================================================================
METRIC 1: INITIALIZATION TIME
================================================================================

Initialization time: 45.32ms

================================================================================
METRIC 2: PATH DISTANCE
================================================================================

Route                                    Path Length
Miami → Boston                           346 tiles
Miami → Houston                          212 tiles
...

Total distance: 52432 tiles
Routes completed: 22 / 22

================================================================================
METRIC 3: PATHFINDING TIME
================================================================================

Route                                    Time
Miami → Boston                           2.45ms
Miami → Houston                          1.82ms
...

Total time: 156.34ms
Average time: 7.11ms
Routes benchmarked: 22 / 22

================================================================================
SUMMARY
================================================================================

Adapter: default
Scenario: default

Scores:
  Initialization: 45.32ms
  Pathfinding: 156.34ms
  Distance: 52432 tiles
```

## Generating Scenarios

### Generate Synthetic Scenarios

Synthetic scenarios are generated by:

1. Finding all water shoreline tiles on a map
2. Randomly selecting 200 ports
3. Creating 1000 routes connecting nearby ports

```bash
# Generate scenario for a single map
npx tsx tests/pathfinding/benchmark/generate.ts iceland

# Generate scenarios for all maps
npx tsx tests/pathfinding/benchmark/generate.ts --all

# Force overwrite existing scenarios
npx tsx tests/pathfinding/benchmark/generate.ts iceland --force
npx tsx tests/pathfinding/benchmark/generate.ts --all --force
```

## Interactive Playground

The playground provides a web-based UI for visualizing pathfinding results, comparing algorithms, and debugging.

### Starting the Playground

```bash
# Start with path caching enabled (default)
npx tsx tests/pathfinding/playground/server.ts

# Start without path caching (to measure uncached performance)
npx tsx tests/pathfinding/playground/server.ts --no-cache
```

Then open http://localhost:5555 in your browser.