## DOTS Air A* Pathfinding for large Terrains 
(under development, upcoming Unity Asset)\
A high-performance, terrain-aware A* pathfinding solution built on Unity's Data-Oriented Technology Stack (DOTS) with Burst compilation. Designed for games requiring efficient pathfinding across complex 3D terrain with elevation changes.
![A* Algorithm](Recordings/AirPathlarge.jpg)
### Core Features

**Octile Distance Heuristic**
Unlike traditional Manhattan or Euclidean distance, this implementation uses the octile distance formula for more accurate diagonal movement estimation:

`h(n) = D × max(|dx|, |dy|) + (D × √2 - D) × min(|dx|, |dy|)`

This provides optimal paths with natural-looking diagonal movement patterns while maintaining admissibility for A* guarantees.

**3D Terrain-Aware Pathfinding**\
The system incorporates vertical movement costs through a configurable fly cost multiplier:

*Upward movement*: `AdditionalCost = heightDifference × flyCostMultiplier`\
*Downward movement*: No additional cost (gravity-assisted)\
*Enables realistic* path planning for flying units, climbing mechanics, or terrain traversal

**Optimized Neighbor Evaluation**

Cardinal directions `(N, S, E, W)` processed with cost factor of 1.0\
Diagonal movements use `√2 ≈ 1.414` cost factor\
Smart corner-cutting prevention ensures paths don't clip through obstacles

![A* Algorithm Demo](Recordings/Gif/output.gif)
### Performance Optimization
**DOTS Architecture**

*Burst Compilation:* Leverages Unity's Burst compiler for near-native performance\
*Job System Integration:* Fully parallelizable pathfinding calculations\
*Native Collections:* Zero garbage collection pressure using NativeArrays\
*Cache-Friendly Data Layout:* Struct-of-Arrays design for optimal CPU cache utilization

**Use Cases**

*Strategy Games:* Calculate hundreds of paths simultaneously for large unit groups\
*Open World Games:* Efficient long-distance pathfinding across varied terrain\
*Flying/Climbing Mechanics:* Natural path generation for 3D movement with elevation costs\
*Tower Defense:* Real-time path recalculation for dynamic obstacles\
*Procedural Worlds:* Works with runtime-generated terrain

### Key Components
**Pathfinding Service Layer**

*Boundary Handling:* Automatic position clamping for out-of-bounds requests\
*World-to-Grid Conversion:* Seamless coordinate system translation\
*Path Caching:* Reusable working arrays minimize allocation overhead

**Visualization & Debugging**

*Heat Map Visualization:* See terrain costs at a glance\
*Path Overlay System:* Visualize calculated paths with customizable colors\
*Grid Debug Mode:* Inspect individual cell states and costs

### Technical Specifications

*Grid Size:* Configurable up to terrain limits\
*Cell Resolution:* Adjustable cell size for precision vs performance tradeoffs\
*Height Sampling:* Automatic terrain height integration\
*Memory Footprint:* `~16 bytes` per grid cell (highly optimized)

### Configuration
The system provides extensive configuration through ScriptableObjects:

*Pathfinding Configuration:* Core algorithm parameters\
*Visualization Configuration:* Debug and display settings\
Runtime adjustable parameters for dynamic gameplay needs

<!-- [Image: Unity Inspector showing the configuration options] -->
### Algorithm Complexity

*Time Complexity:* `O(n log n)` where n is the number of cells explored\
*Space Complexity:* `O(n)` for the open list and path storage\
*Optimizations:* Early termination, efficient priority queue implementation


This asset provides a production-ready pathfinding solution that scales from small indie projects to large-scale strategy games, combining mathematical elegance with raw performance through Unity's cutting-edge DOTS technology.