# Nexus.Pathfinding — Navigation & Exploration

## Overview

Two classes: **NavigationController** (state machine — decides *where* to go) and **PathFinder** (A* algorithm — decides *how* to get there).

---

## NavigationController

### Modes

| Mode | Trigger | Behavior |
|------|---------|----------|
| Idle | `Stop()` | No movement |
| NavigatingToPosition | `NavigateTo(pos)` | Path to fixed world coordinates |
| NavigatingToEntity | `NavigateToEntity(id)` | Chase a moving entity (re-targets each tick) |
| Exploring | `Explore()` | BFS frontier exploration of unmapped terrain |

### Update Loop (called every tick)

```
1. Area change detection → clear path, explored grid, stuck history
2. EnsureExploredGrid() → allocate/resize to match terrain (preserves old data on expansion)
3. MarkExplored(playerPos) → mark cells near player as visited (radius 150 grid cells)
4. ResolveGoal() → get target position based on mode
5. If no goal and Exploring → PickExploreTarget() via BFS
6. Reach detection → within WaypointReachedDistance (80u), clear goal or stop
7. Stuck detection → if < 30u movement in 60 ticks (~1s), repath or pick new target
8. Pathfinding → A* from player to goal (with explored grid bias in explore mode)
9. Waypoint advancement → advance index as player reaches each waypoint
10. Output → DesiredDirection (normalized vector to next waypoint)
```

### Explored Grid

Parallel bool array matching terrain dimensions. Tracks which cells the player has visited.

- **Mark radius**: 150 grid cells (~1630 world units) — circular region around player
- **Preservation**: On terrain expansion, overlapping explored data is copied to new grid
- **Offset-aware**: Uses same OffsetX/OffsetY as terrain for absolute grid coordinates

### BFS Exploration (PickExploreTarget)

When Exploring mode needs a new goal:

1. **BFS frontier search** (up to 100,000 iterations)
   - 8-directional BFS outward from player
   - Finds nearest unexplored walkable cell
   - Returns that cell as world coordinates

2. **Random distant target** (if BFS finds nothing)
   - 20 attempts at random directions, 1500-3500 world units away
   - Pushes player toward terrain edges where expansion triggers

3. **Edge fallback** (if random fails)
   - Heads toward nearest terrain boundary (10 cells from edge)
   - Guarantees continued exploration with infinite terrain

4. **Exploration complete** (only if all fallbacks fail)
   - Sets `IsExplorationComplete = true`
   - Prevents expensive re-BFS every tick
   - Reset on area change

### Stuck Detection

- **Window**: Last 60 positions (~1 second at 60Hz)
- **Threshold**: Must move at least 30 world units in window
- **Grace period**: 120 ticks (2 seconds) after picking new explore target
- **On stuck while exploring**: Mark failed goal as explored, pick new target, set grace period
- **On stuck otherwise**: Repath

### Path Failure Handling

- **Explored bias fallback**: If A* with explored grid bias fails, retry without bias (bias can make distant targets unreachable)
- **Cooldown**: 3 seconds before retrying after path failure (prevents CPU burn on impossible paths)

---

## PathFinder — A* Implementation

### Signature

```csharp
public static List<Vector2>? FindPath(
    WalkabilitySnapshot terrain, Vector2 start, Vector2 goal, float worldToGrid,
    bool[]? exploredGrid, int exploredWidth, int exploredHeight,
    int exploredOffsetX, int exploredOffsetY)
```

Returns world-coordinate waypoints or null if unreachable.

### Movement Model

- **8-directional grid**: Cardinal + diagonal
- **Costs**: Cardinal = 1.0, Diagonal = √2 ≈ 1.414
- **Explored penalty**: ×1.5 multiplier for explored cells (biases paths through unexplored territory)

### Heuristic

```
h = max(dx, dy) + 0.414 * min(dx, dy)
```
Diagonal/Chebyshev-based. Admissible and consistent.

### Algorithm

1. **Snap to walkable**: If start/goal in wall, BFS search for nearest walkable cell (radius up to 20)
2. **A* search** (budget: 200,000 iterations):
   - Priority queue ordered by f = g + h
   - 8 neighbors per expansion
   - **Corner-cut check**: Diagonals require at least one adjacent cardinal cell walkable
   - **Explored grid bias**: Multiply step cost by 1.5 for explored cells
   - Track `bestNode` (closest reachable) for fallback
3. **Path reconstruction**: Backtrack via cameFrom map
4. **Simplification**: Remove collinear waypoints, keep only turning points
5. **Fallback**: If goal unreachable but bestNode is meaningfully closer (within 80% of starting heuristic), path to closest reachable cell

### Data Structures

| Structure | Type | Purpose |
|-----------|------|---------|
| Open set | PriorityQueue<(int,int), float> | Nodes to expand, ordered by f-score |
| Closed set | HashSet<(int,int)> | Already expanded nodes |
| gScore | Dictionary<(int,int), float> | Best known cost to each node |
| cameFrom | Dictionary<(int,int), (int,int)> | Backtracking map |

---

## Integration

```
AreaProgressionSystem
    │ .Explore() / .NavigateTo() / .NavigateToEntity()
    ▼
NavigationController
    │ .Update(GameState) → computes path, sets DesiredDirection
    │ calls PathFinder.FindPath() for A* routing
    ▼
NavigationSystem
    │ reads DesiredDirection → submits MoveAction
    ▼
ActionQueue → BotEngine → MovementKeyTracker → WASD keys
```

### Coordinate Systems

| Space | Example | Conversion |
|-------|---------|------------|
| World | (1517, 4491) | Raw game units |
| Grid | (139, 413) | world × WorldToGrid (23/250) |
| Local grid | (139-ox, 413-oy) | grid - terrain offset |
| Screen | project via CameraMatrix | WorldToScreen.Project() |