orion-ecs / keen-eye / 20703329942

65%

push

github

feat(navigation): Add grid-based A* pathfinding for 2D games

Implements Issue #638 - Grid-based A* pathfinding without DotRecast dependency.

Deliverables:
- NavigationGrid: 2D grid representation with walkability and area types
- GridCoordinate: Value type for grid positions with distance calculations
- GridCell: Cell data structure with walkability and cost information
- AStarPathfinder: A* algorithm with cardinal and diagonal movement support
- GridNavigationProvider: INavigationProvider implementation for grid navigation
- GridNavigationPlugin: World plugin for easy integration
- Zero-allocation path queries via Span<GridCoordinate> overloads

Features:
- 4-directional (cardinal) and 8-directional (diagonal) movement
- Multiple heuristics: Manhattan, Chebyshev, Octile, Euclidean
- Area-based cost multipliers for terrain types
- NavAreaMask filtering for traversable areas
- Corner-cutting prevention for diagonal movement
- Async path request support via IPathRequest
- Bresenham's line algorithm for raycasting
- Configurable iteration limits

Includes 167 comprehensive unit tests covering:
- GridCoordinate operations and conversions
- NavigationGrid cell access and bounds checking
- A* pathfinding with various obstacles and configurations
- GridNavigationProvider full API coverage
- GridConfig validation

5403 of 6664 branches covered (81.08%)

Branch coverage included in aggregate %.

34672 of 44775 relevant lines covered (77.44%)

1.1 hits per line