poe2-bot/docs/pathfinding.md

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

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()