Pathfinding & Navigation

Pathfinding & Navigation

This document covers the server-authoritative pathfinding system, spatial data structures, and NPC navigation for RentEarth. The server (Rust/Axum) is the single source of truth for entity movement - Unity clients only interpolate and render.

Architecture Overview

┌─────────────────────────────────────────────────────────────────┐
│                        SERVER (Axum/Rust)                       │
├─────────────────────────────────────────────────────────────────┤
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────────────────┐  │
│  │   Physics   │  │  Pathfind   │  │    NPC Controller       │  │
│  │   Worker    │  │   Module    │  │    (10 Hz tick)         │  │
│  │  (Rapier3D) │  │  (A*/Flow)  │  │                         │  │
│  └──────┬──────┘  └──────┬──────┘  └───────────┬─────────────┘  │
│         │                │                     │                │
│         └────────────────┼─────────────────────┘                │
│                          │                                      │
│                    ┌─────▼─────┐                                │
│                    │  Entity   │                                │
│                    │   State   │                                │
│                    │  Manager  │                                │
│                    └─────┬─────┘                                │
│                          │                                      │
│                    ┌─────▼─────┐                                │
│                    │  Network  │                                │
│                    │ Snapshot  │                                │
│                    └─────┬─────┘                                │
└──────────────────────────┼──────────────────────────────────────┘
                           │ WebSocket (10 Hz)
┌──────────────────────────▼──────────────────────────────────────┐
│                      CLIENT (Unity)                             │
├─────────────────────────────────────────────────────────────────┤
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────────────────┐  │
│  │  Snapshot   │  │  Network    │  │    Visual Rendering     │  │
│  │ Interpolate │──▶  Entity    │──▶   (PhysX for visuals)   │  │
│  │   (60fps)   │  │  Manager    │  │                         │  │
│  └─────────────┘  └─────────────┘  └─────────────────────────┘  │
└─────────────────────────────────────────────────────────────────┘

Current Implementation Status

Component	Status	Description
Physics (Rapier3D)	✅ Complete	Raycasts, overlaps, terrain height
NPC Controller	✅ Complete	Patrol, chase, guard, harvest behaviors
WaypointGraph	✅ Complete	Graph-based navigation with A* pathfinding
Waypoint System	✅ Complete	Typed waypoints with edges and costs
Movement Variation	✅ Complete	Speed/drift variation for natural motion
Combat Shortcuts	✅ Complete	Direct pursuit bypasses graph in combat
Spatial Queries	✅ Complete	Chunk-based entity lookups
Unity Waypoint Editor	✅ Complete	Visual waypoint placement and connection
Flow Fields	🔲 Planned	Mass unit movement
Quadtree	🔲 Planned	Spatial partitioning
KD-Tree	🔲 Planned	Nearest neighbor queries

---

Spatial Data Structures

Current: Chunk-Based Spatial Hashing

The existing system uses 50×50m chunks for spatial partitioning:

// EntityStateManager uses DashMap for chunk-entity mapping
chunk_entities: Arc<DashMap<(i32, i32), HashSet<Uuid>>>
entity_chunks: Arc<DashMap<Uuid, HashSet<(i32, i32)>>>

// Query entities near a position
fn get_entities_near_position(&self, pos: &Position) -> Vec<Uuid> {
    let chunk = self.position_to_chunk(pos);
    // Check current chunk + neighbors (3x3 = 9 chunks)
    for dx in -1..=1 {
        for dz in -1..=1 {
            // Collect entities from (chunk.0 + dx, chunk.1 + dz)
        }
    }
}

Pros: Simple, O(1) chunk lookup, good for uniform density Cons: Poor for varied density, no hierarchy, fixed resolution

Planned: Quadtree

Hierarchical spatial partitioning that adapts to entity density:

/// Quadtree node for 2D spatial partitioning (XZ plane)
pub struct QuadtreeNode {
    bounds: AABB2D,           // Axis-aligned bounding box
    entities: Vec<EntityRef>, // Entities at this node (leaf only)
    children: Option<Box<[QuadtreeNode; 4]>>, // NW, NE, SW, SE
    depth: u8,
}

impl QuadtreeNode {
    const MAX_ENTITIES: usize = 8;  // Split threshold
    const MAX_DEPTH: u8 = 8;        // ~0.2m resolution at 50m root

    /// Insert entity, splitting node if needed
    pub fn insert(&mut self, entity: EntityRef, pos: Vec2) {
        if self.is_leaf() {
            self.entities.push(entity);
            if self.entities.len() > Self::MAX_ENTITIES && self.depth < Self::MAX_DEPTH {
                self.split();
            }
        } else {
            let quadrant = self.get_quadrant(pos);
            self.children.as_mut().unwrap()[quadrant].insert(entity, pos);
        }
    }

    /// Query all entities within radius
    pub fn query_radius(&self, center: Vec2, radius: f32, results: &mut Vec<EntityRef>) {
        if !self.bounds.intersects_circle(center, radius) {
            return;
        }
        if self.is_leaf() {
            results.extend(self.entities.iter().cloned());
        } else {
            for child in self.children.as_ref().unwrap().iter() {
                child.query_radius(center, radius, results);
            }
        }
    }
}

Use cases:

• Hostile detection (NPCs scanning for players)
• AoE spell targeting
• Collision broad-phase

Planned: KD-Tree

Optimal for nearest-neighbor queries:

/// KD-Tree for k-nearest neighbor queries
pub struct KDTree {
    nodes: Vec<KDNode>,
    points: Vec<(Vec3, Uuid)>, // Position + entity ID
}

pub struct KDNode {
    point_idx: usize,
    split_axis: u8,      // 0=X, 1=Y, 2=Z
    left: Option<usize>,
    right: Option<usize>,
}

impl KDTree {
    /// Build tree from entity positions (O(n log n))
    pub fn build(entities: &[(Vec3, Uuid)]) -> Self {
        // Recursive median-split construction
    }

    /// Find k nearest entities to query point
    pub fn k_nearest(&self, query: Vec3, k: usize) -> Vec<(Uuid, f32)> {
        let mut heap = BinaryHeap::new(); // Max-heap by distance
        self.search_recursive(0, query, k, &mut heap);
        heap.into_sorted_vec()
    }

    /// Find all entities within radius
    pub fn range_search(&self, center: Vec3, radius: f32) -> Vec<Uuid> {
        // Prune branches outside radius
    }
}

Use cases:

• Find closest enemy/ally
• Social AI (NPC group behavior)
• Resource finding for harvest bots

---

Pathfinding Algorithms

Current: Graph-Based A* Pathfinding

NPCs navigate using a WaypointGraph with A* pathfinding. The system supports typed waypoints, weighted edges, and combat shortcuts for direct pursuit.

// website/axum/src/game/npc/waypoint.rs

pub type WaypointId = u32;

/// A waypoint in the navigation graph
#[derive(Clone, Debug)]
pub struct Waypoint {
    pub id: WaypointId,
    pub position: Position,
    pub waypoint_type: WaypointType,
    pub radius: f32,
    pub name: Option<String>,
    pub tags: HashSet<String>,
    pub active: bool,
}

/// Types of waypoints for different NPC behaviors
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum WaypointType {
    Navigation,   // Standard navigation waypoint
    Patrol,       // Patrol point - NPCs pause briefly here
    GuardPost,    // Guard post - NPCs hold position and watch
    Spawn,        // Spawn point for NPCs
    Rest,         // Rest area - NPCs can idle here
    Combat,       // Combat hotspot - expect engagement
    Chokepoint,   // Choke point - narrow passage
    Cover,        // Cover position - defensive location
}

/// Edge connecting two waypoints
#[derive(Clone, Debug)]
pub struct WaypointEdge {
    pub target: WaypointId,
    pub cost: f32,
    pub bidirectional: bool,
    pub tags: HashSet<String>,
}

/// Graph of waypoints for NPC navigation
pub struct WaypointGraph {
    waypoints: HashMap<WaypointId, Waypoint>,
    edges: HashMap<WaypointId, Vec<WaypointEdge>>,
    next_id: WaypointId,
}

impl WaypointGraph {
    /// A* pathfinding between waypoints
    pub fn find_path(&self, start: WaypointId, goal: WaypointId) -> Option<Vec<WaypointId>> {
        if start == goal {
            return Some(vec![start]);
        }

        let mut open_set = BinaryHeap::new();
        let mut came_from: HashMap<WaypointId, WaypointId> = HashMap::new();
        let mut g_score: HashMap<WaypointId, f32> = HashMap::new();
        let mut in_open: HashSet<WaypointId> = HashSet::new();

        g_score.insert(start, 0.0);
        open_set.push(PathNode { id: start, f_score: self.heuristic(start, goal) });
        in_open.insert(start);

        while let Some(current) = open_set.pop() {
            if current.id == goal {
                return Some(self.reconstruct_path(&came_from, current.id));
            }

            for edge in self.get_edges(current.id) {
                let tentative_g = g_score[&current.id] + edge.cost;
                if tentative_g < *g_score.get(&edge.target).unwrap_or(&f32::INFINITY) {
                    came_from.insert(edge.target, current.id);
                    g_score.insert(edge.target, tentative_g);
                    if !in_open.contains(&edge.target) {
                        open_set.push(PathNode {
                            id: edge.target,
                            f_score: tentative_g + self.heuristic(edge.target, goal),
                        });
                        in_open.insert(edge.target);
                    }
                }
            }
        }
        None
    }

    /// Create a patrol route from positions (auto-connected loop)
    pub fn create_patrol_route(&mut self, positions: Vec<Position>, loop_back: bool) -> Vec<WaypointId> {
        let ids: Vec<_> = positions.iter().map(|pos| {
            self.add_waypoint(*pos, WaypointType::Patrol, 1.0)
        }).collect();

        // Connect sequentially
        for i in 0..ids.len().saturating_sub(1) {
            let cost = self.waypoints[&ids[i]].position.distance_2d(&self.waypoints[&ids[i+1]].position);
            self.connect(ids[i], ids[i+1], cost, true);
        }

        // Loop back to start
        if loop_back && ids.len() > 1 {
            let cost = self.waypoints[ids.last().unwrap()].position.distance_2d(&self.waypoints[&ids[0]].position);
            self.connect(*ids.last().unwrap(), ids[0], cost, true);
        }

        ids
    }
}

Combat Shortcuts: Direct Pursuit

During combat, NPCs can bypass graph navigation for direct line-of-sight pursuit:

// In tick_guard_with_combat()
if instance.direct_pursuit_enabled {
    // COMBAT SHORTCUT: Direct pursuit toward target
    // Bypasses graph navigation for immediate, aggressive chase
    let dx = target_pos.x - current_pos.x;
    let dz = target_pos.z - current_pos.z;
    let dist = (dx * dx + dz * dz).sqrt();

    if dist > 0.1 {
        let dir_x = dx / dist;
        let dir_z = dz / dist;
        let speed = CHASE_SPEED * instance.speed_multiplier;
        // Move directly toward target
    }
}

Planned: A* Grid Pathfinding

For fine-grained obstacle-aware navigation:

/// Grid-based A* pathfinder
pub struct GridPathfinder {
    grid: Vec<Vec<CellType>>,  // WALKABLE, BLOCKED, WATER, etc.
    width: usize,
    height: usize,
    cell_size: f32,            // World units per cell (e.g., 1.0m)
}

#[derive(Clone, Copy, PartialEq)]
pub enum CellType {
    Walkable,
    Blocked,
    Water,      // Requires swimming
    Slow,       // Half speed (mud, tall grass)
}

impl GridPathfinder {
    /// Find path from start to goal, returns waypoints
    pub fn find_path(&self, start: Vec2, goal: Vec2) -> Option<Vec<Vec2>> {
        let start_cell = self.world_to_cell(start);
        let goal_cell = self.world_to_cell(goal);

        let mut open_set = BinaryHeap::new();
        let mut came_from: HashMap<(i32, i32), (i32, i32)> = HashMap::new();
        let mut g_score: HashMap<(i32, i32), f32> = HashMap::new();

        g_score.insert(start_cell, 0.0);
        open_set.push(AStarNode {
            cell: start_cell,
            f_score: self.heuristic(start_cell, goal_cell),
        });

        while let Some(current) = open_set.pop() {
            if current.cell == goal_cell {
                return Some(self.reconstruct_path(&came_from, current.cell));
            }

            for neighbor in self.get_neighbors(current.cell) {
                let tentative_g = g_score[&current.cell] + self.move_cost(current.cell, neighbor);

                if tentative_g < *g_score.get(&neighbor).unwrap_or(&f32::INFINITY) {
                    came_from.insert(neighbor, current.cell);
                    g_score.insert(neighbor, tentative_g);
                    open_set.push(AStarNode {
                        cell: neighbor,
                        f_score: tentative_g + self.heuristic(neighbor, goal_cell),
                    });
                }
            }
        }
        None // No path found
    }

    fn heuristic(&self, a: (i32, i32), b: (i32, i32)) -> f32 {
        // Octile distance (diagonal movement)
        let dx = (a.0 - b.0).abs() as f32;
        let dy = (a.1 - b.1).abs() as f32;
        (dx + dy) + (1.414 - 2.0) * dx.min(dy)
    }
}

Planned: Hierarchical Pathfinding (HPA*)

For long-distance paths across chunks:

/// Hierarchical pathfinding across chunk boundaries
pub struct HPAGraph {
    /// Per-chunk local pathfinding grids
    chunk_grids: HashMap<(i32, i32), GridPathfinder>,

    /// Abstract graph connecting chunk portals
    portal_graph: Graph<PortalNode, f32>,
}

pub struct PortalNode {
    chunk: (i32, i32),
    position: Vec2,
    portal_type: PortalType, // Edge, Interior
}

impl HPAGraph {
    /// Find path across multiple chunks
    pub fn find_path(&self, start: Vec3, goal: Vec3) -> Option<Vec<Vec3>> {
        let start_chunk = world_to_chunk(start);
        let goal_chunk = world_to_chunk(goal);

        if start_chunk == goal_chunk {
            // Same chunk - use local A*
            return self.chunk_grids[&start_chunk].find_path(start.xz(), goal.xz());
        }

        // 1. Find nearest portal from start
        // 2. A* on portal graph to goal chunk
        // 3. Local A* from goal portal to goal
        // 4. Stitch paths together
    }
}

Planned: Flow Fields

For mass unit movement (100+ entities to same destination):

/// Flow field for efficient mass navigation
pub struct FlowField {
    grid: Vec<Vec<Vec2>>,  // Direction vectors
    cost_field: Vec<Vec<u8>>,
    integration_field: Vec<Vec<u16>>,
    goal: (i32, i32),
    width: usize,
    height: usize,
}

impl FlowField {
    /// Generate flow field toward goal
    pub fn generate(grid: &GridPathfinder, goal: Vec2) -> Self {
        let mut field = Self::new(grid.width, grid.height);
        field.goal = grid.world_to_cell(goal);

        // 1. Build cost field (terrain costs)
        field.build_cost_field(grid);

        // 2. Dijkstra from goal to build integration field
        field.build_integration_field();

        // 3. Calculate flow directions
        field.build_flow_vectors();

        field
    }

    /// Get movement direction for entity at position
    pub fn get_direction(&self, pos: Vec2) -> Vec2 {
        let cell = self.world_to_cell(pos);
        self.grid[cell.1][cell.0]
    }

    fn build_flow_vectors(&mut self) {
        for y in 0..self.height {
            for x in 0..self.width {
                // Find neighbor with lowest integration cost
                let mut best_dir = Vec2::ZERO;
                let mut best_cost = self.integration_field[y][x];

                for (dx, dy) in [(-1,0), (1,0), (0,-1), (0,1), (-1,-1), (1,-1), (-1,1), (1,1)] {
                    let nx = x as i32 + dx;
                    let ny = y as i32 + dy;
                    if self.in_bounds(nx, ny) {
                        let cost = self.integration_field[ny as usize][nx as usize];
                        if cost < best_cost {
                            best_cost = cost;
                            best_dir = Vec2::new(dx as f32, dy as f32).normalize();
                        }
                    }
                }
                self.grid[y][x] = best_dir;
            }
        }
    }
}

Use cases:

• Swarm enemies converging on player
• Flee behavior (reverse flow from threats)
• RTS-style unit commands

---

Waypoint System

The waypoint system is fully implemented in both Rust (server) and Unity (client visualization).

Server: Rust Implementation

// website/axum/src/game/npc/waypoint.rs

impl WaypointGraph {
    /// Find nearest waypoint to a world position
    pub fn nearest_waypoint(&self, pos: Position) -> Option<WaypointId> {
        self.waypoints
            .values()
            .filter(|w| w.active)
            .min_by(|a, b| {
                let da = a.position.distance_2d(&pos);
                let db = b.position.distance_2d(&pos);
                da.partial_cmp(&db).unwrap_or(Ordering::Equal)
            })
            .map(|w| w.id)
    }

    /// Find all waypoints within a radius
    pub fn waypoints_in_radius(&self, pos: Position, radius: f32) -> Vec<WaypointId> {
        self.waypoints
            .values()
            .filter(|w| w.active && w.position.distance_2d(&pos) <= radius)
            .map(|w| w.id)
            .collect()
    }

    /// Find waypoints by type
    pub fn waypoints_by_type(&self, wp_type: WaypointType) -> Vec<WaypointId> {
        self.waypoints
            .values()
            .filter(|w| w.active && w.waypoint_type == wp_type)
            .map(|w| w.id)
            .collect()
    }

    /// Find waypoints with a specific tag
    pub fn waypoints_with_tag(&self, tag: &str) -> Vec<WaypointId> {
        self.waypoints
            .values()
            .filter(|w| w.active && w.tags.contains(tag))
            .map(|w| w.id)
            .collect()
    }

    /// Auto-connect waypoints within a distance threshold
    pub fn auto_connect(&mut self, max_distance: f32) {
        let ids: Vec<WaypointId> = self.waypoints.keys().copied().collect();
        for i in 0..ids.len() {
            for j in (i + 1)..ids.len() {
                let wp_a = &self.waypoints[&ids[i]];
                let wp_b = &self.waypoints[&ids[j]];
                let dist = wp_a.position.distance_2d(&wp_b.position);
                if dist <= max_distance {
                    self.connect(ids[i], ids[j], dist, true);
                }
            }
        }
    }
}

Client: Unity Waypoint Components

// unity/rentearth/Assets/Scripts/Navigation/Waypoint.cs

public enum WaypointType
{
    Navigation,   // Standard navigation waypoint
    Patrol,       // Patrol point - NPCs pause briefly here
    GuardPost,    // Guard post - NPCs hold position and watch
    Spawn,        // Spawn point for NPCs
    Rest,         // Rest area - NPCs can idle here
    Combat,       // Combat hotspot - expect engagement
    Chokepoint,   // Choke point - narrow passage
    Cover         // Cover position - defensive location
}

public class Waypoint : MonoBehaviour
{
    [Header("Waypoint Settings")]
    public uint waypointId;
    public WaypointType waypointType = WaypointType.Navigation;
    public float radius = 1.0f;
    public string waypointName;
    public List<string> tags = new List<string>();
    public bool active = true;

    [Header("Connections")]
    public List<WaypointConnection> connections = new List<WaypointConnection>();

    public bool IsReached(Vector3 position) {
        Vector3 diff = transform.position - position;
        diff.y = 0; // 2D distance check
        return diff.sqrMagnitude <= radius * radius;
    }

    public void Connect(Waypoint target, float cost = 1f, bool bidirectional = true) {
        if (target == null || target == this) return;
        connections.Add(new WaypointConnection { target = target, cost = cost, bidirectional = bidirectional });
        if (bidirectional) target.Connect(this, cost, false);
    }
}

[System.Serializable]
public class WaypointConnection
{
    public Waypoint target;
    public float cost = 1f;
    public bool bidirectional = true;
    public List<string> tags = new List<string>();
}

Unity: WaypointGraph with A* Pathfinding

// unity/rentearth/Assets/Scripts/Navigation/WaypointGraph.cs

public class WaypointGraph : MonoBehaviour
{
    public bool autoDiscoverWaypoints = true;
    public float autoConnectDistance = 0f;

    private Dictionary<uint, Waypoint> _waypoints = new Dictionary<uint, Waypoint>();

    /// A* pathfinding from start to goal
    public List<Waypoint> FindPath(Waypoint start, Waypoint goal) {
        if (start == null || goal == null) return null;
        if (start == goal) return new List<Waypoint> { start };

        var openSet = new SortedSet<PathNode>(new PathNodeComparer());
        var cameFrom = new Dictionary<uint, uint>();
        var gScore = new Dictionary<uint, float>();

        gScore[start.waypointId] = 0;
        openSet.Add(new PathNode { waypointId = start.waypointId, fScore = Heuristic(start, goal) });

        while (openSet.Count > 0) {
            var current = openSet.First();
            openSet.Remove(current);

            if (current.waypointId == goal.waypointId)
                return ReconstructPath(cameFrom, current.waypointId);

            var currentWp = GetWaypoint(current.waypointId);
            foreach (var conn in currentWp.connections) {
                float tentativeG = gScore[current.waypointId] + conn.cost;
                if (!gScore.ContainsKey(conn.target.waypointId) || tentativeG < gScore[conn.target.waypointId]) {
                    cameFrom[conn.target.waypointId] = current.waypointId;
                    gScore[conn.target.waypointId] = tentativeG;
                    openSet.Add(new PathNode {
                        waypointId = conn.target.waypointId,
                        fScore = tentativeG + Heuristic(conn.target, goal)
                    });
                }
            }
        }
        return null; // No path found
    }
}

Unity Editor Tools

// unity/rentearth/Assets/Scripts/Navigation/Editor/WaypointEditor.cs

[CustomEditor(typeof(Waypoint))]
public class WaypointEditor : UnityEditor.Editor
{
    private static Waypoint _connectionSource;

    public override void OnInspectorGUI() {
        DrawDefaultInspector();
        var waypoint = (Waypoint)target;

        EditorGUILayout.LabelField("Connection Tools", EditorStyles.boldLabel);

        if (_connectionSource == null) {
            if (GUILayout.Button("Start Connection")) {
                _connectionSource = waypoint;
            }
        } else if (_connectionSource == waypoint) {
            if (GUILayout.Button("Cancel Connection")) {
                _connectionSource = null;
            }
        } else {
            if (GUILayout.Button($"Connect from {_connectionSource.name}")) {
                Undo.RecordObject(_connectionSource, "Connect Waypoints");
                _connectionSource.Connect(waypoint);
                _connectionSource = null;
            }
        }
    }
}

/// Window for creating waypoint networks
public class WaypointNetworkWindow : EditorWindow
{
    [MenuItem("RentEarth/Navigation/Waypoint Network Tool")]
    public static void ShowWindow() => GetWindow<WaypointNetworkWindow>("Waypoint Network");

    // Create Circle Patrol, Square Patrol with auto-connection
}

---

NPC State Machine

Bitwise State Flags

Compact, efficient state representation using i64 bitflags:

/// Emotional state (mood, reactions)
pub mod emotional {
    pub const NEUTRAL: i64  = 0;
    pub const ALERT: i64    = 1 << 0;   // Investigating
    pub const AFRAID: i64   = 1 << 1;   // Fleeing
    pub const ANGRY: i64    = 1 << 2;   // Aggressive
    pub const CURIOUS: i64  = 1 << 3;   // Slower, looking around
    // Bits 8-15: Intensity (0-255)
    // Bits 16-31: Duration (ticks)
}

/// Combat state
pub mod combat {
    pub const IDLE: i64       = 0;
    pub const ENGAGED: i64    = 1 << 0;  // In combat
    pub const PURSUING: i64   = 1 << 1;  // Chasing target
    pub const RETREATING: i64 = 1 << 2;  // Backing away
    pub const STUNNED: i64    = 1 << 6;  // Cannot act
    // Bits 8-15: Attack cooldown
    // Bits 32-47: Target entity hash
}

/// Behavior state
pub mod behavior {
    pub const IDLE: i64    = 0;
    pub const PATROL: i64  = 1 << 0;
    pub const GUARD: i64   = 1 << 1;
    pub const HARVEST: i64 = 1 << 2;
    pub const FLEE: i64    = 1 << 5;
    pub const RETURN_HOME: i64 = 1 << 6;
    pub const WANDER: i64  = 1 << 7;
    // Bits 16-23: Waypoint index
}

/// Social state (factions, groups)
pub mod social {
    pub const FACTION_NEUTRAL: u8 = 0;
    pub const FACTION_PLAYER: u8  = 1;
    pub const FACTION_TOWN: u8    = 2;
    pub const FACTION_WILDLIFE: u8 = 3;
    pub const FACTION_HOSTILE: u8 = 4;
    // Bits 8-15: Group ID
}

NPC Instance

NPCs use graph-based navigation with waypoint IDs instead of raw positions:

// website/axum/src/game/npc/controller.rs

pub struct NpcInstance {
    pub entity_id: Uuid,
    pub state: NpcState,           // Bitwise flags

    // Graph-based navigation
    pub home_position: Position,
    pub home_waypoint_id: Option<WaypointId>,      // Home waypoint in graph
    pub patrol_waypoint_ids: Vec<WaypointId>,      // Patrol route (graph IDs)
    pub current_path: Vec<WaypointId>,             // A* computed path
    pub path_index: usize,                         // Current position in path

    // Target tracking
    pub target_id: Option<Uuid>,
    pub last_target_position: Option<Position>,
    pub ticks_since_target_seen: u32,

    // Combat shortcuts
    pub direct_pursuit_enabled: bool,  // Bypass graph for direct chase

    // Movement variation for natural motion
    pub speed_multiplier: f32,     // 0.85 - 1.15
    pub drift_direction: f32,      // -1.0 to 1.0
    pub variation_seed: u32,

    // Combat
    pub attack_damage: f32,
    pub attack_cooldown: u8,

    // Harvesting
    pub harvest_target_waypoint: Option<WaypointId>,
    pub harvest_ticks_remaining: u32,
    pub collected_resources: u32,
}

/// NPC Controller with shared waypoint graph
pub struct NpcController {
    npcs: Vec<NpcInstance>,
    stats: NpcStats,
    combat_events: Vec<CombatEvent>,
    waypoint_graph: Option<Arc<WaypointGraph>>,  // Shared graph reference
}

---

Movement Constants

// Speed (units per tick at 10 Hz = units/sec ÷ 10)
const PATROL_SPEED: f32 = 0.3;   // 3 units/sec
const CHASE_SPEED: f32 = 0.5;    // 5 units/sec
const RETURN_SPEED: f32 = 0.4;   // 4 units/sec
const HARVEST_SPEED: f32 = 0.25; // 2.5 units/sec

// Movement variation for natural motion
const SPEED_VARIATION: f32 = 0.15;      // ±15%
const DRIFT_AMOUNT: f32 = 0.02;         // Lateral drift per tick
const DRIFT_CHANGE_CHANCE: f32 = 0.1;   // 10% chance to change drift

// Detection and combat
const DETECTION_RADIUS: f32 = 15.0;     // Hostile scan range
const CHASE_ABANDON_DISTANCE: f32 = 30.0;
const ATTACK_RANGE: f32 = 2.0;
const WAYPOINT_THRESHOLD: f32 = 1.0;    // Arrival distance

---

Unity Client Integration

Waypoint Visualization (Editor)

/// Unity editor component for waypoint visualization
public class WaypointGizmos : MonoBehaviour
{
    public WaypointGraph graph;
    public Color waypointColor = Color.cyan;
    public Color connectionColor = Color.yellow;
    public float waypointRadius = 0.5f;

    void OnDrawGizmos()
    {
        if (graph == null) return;

        foreach (var waypoint in graph.waypoints.Values)
        {
            // Draw waypoint sphere
            Gizmos.color = GetWaypointColor(waypoint.waypointType);
            Gizmos.DrawWireSphere(waypoint.position, waypointRadius);

            // Draw connections
            Gizmos.color = connectionColor;
            foreach (var conn in waypoint.connections)
            {
                if (graph.waypoints.TryGetValue(conn.targetId, out var target))
                {
                    Gizmos.DrawLine(waypoint.position, target.position);

                    // Arrow head for direction
                    if (!conn.bidirectional)
                    {
                        DrawArrow(waypoint.position, target.position);
                    }
                }
            }
        }
    }

    Color GetWaypointColor(WaypointType type) => type switch
    {
        WaypointType.Patrol => Color.blue,
        WaypointType.GuardPost => Color.red,
        WaypointType.HarvestPoint => Color.green,
        WaypointType.SpawnPoint => Color.magenta,
        _ => waypointColor
    };
}

NPC Path Debugging

/// Debug visualization for NPC paths
public class NPCPathDebug : MonoBehaviour
{
    public bool showCurrentPath = true;
    public bool showWaypoints = true;
    public bool showDetectionRadius = false;

    void OnDrawGizmosSelected()
    {
        var npc = GetComponent<NetworkEntity>();
        if (npc == null || !showCurrentPath) return;

        // Draw path to current waypoint
        Gizmos.color = Color.green;
        // ... draw line to target position from server state

        if (showDetectionRadius)
        {
            Gizmos.color = new Color(1, 0, 0, 0.2f);
            Gizmos.DrawWireSphere(transform.position, 15f); // DETECTION_RADIUS
        }
    }
}

---

Data Flow

1. SPAWN
   world_runtime::initialize_npc_controller()
     → Create WaypointGraph
     → waypoint_graph.create_patrol_route(positions, loop_back=true)
       → Returns Vec<WaypointId> for patrol route
     → controller.set_waypoint_graph(Arc::new(waypoint_graph))
     → spawn_town_guard(entity_state, position, patrol_route)
       → NpcInstance::new().with_patrol_route(patrol_route)
       → controller.register(instance)
       → entity_state.update_entity_chunks()

2. TICK (10 Hz)
   npc_controller.tick(entity_state, physics_worker)
     → for each NpcInstance:
         match behavior:
           PATROL → tick_patrol()
             → Get target waypoint from patrol_waypoint_ids[path_index]
             → Look up waypoint position from graph
             → update_movement_variation()
             → calculate direction to waypoint
             → apply speed × variation + drift
             → calculate_facing_rotation()
             → entity_state.update_position()
             → entity_state.mark_dirty()

           GUARD → tick_guard_with_combat()
             → check_for_hostiles()
             → if target && direct_pursuit_enabled:
                 → COMBAT SHORTCUT: direct line-of-sight chase
             → else if target:
                 → Use graph.find_path() for A* navigation
             → Attack if in range
             → return CombatEvent if damage dealt

           HARVEST → tick_harvest()
             → Move to harvest_target_waypoint
             → Collect resources
             → Return to home_waypoint_id

3. NETWORK (10 Hz)
   process_tick()
     → entity_state.take_dirty_entities()
     → for each recipient:
         → build EntitySnapshot with position, rotation, animation
         → delta compress against client cache
         → send WorldSnapshot via WebSocket

4. CLIENT (60 fps)
   SnapshotInterpolator.Update()
     → interpolate between snapshots
     → ApplyInterpolatedState() to NetworkEntity
     → smooth lerp position/rotation

---

Future Enhancements

Phase E - Advanced Pathfinding

• WaypointGraph A pathfinding* - Complete graph-based navigation
• Combat shortcuts - Direct pursuit bypasses graph in combat
• Grid-based A* with terrain costs
• Hierarchical pathfinding (HPA*) for cross-chunk paths
• Dynamic obstacle avoidance
• Jump/climb link support

Phase F - Spatial Optimization

• Quadtree for broad-phase collision
• KD-Tree for nearest-neighbor queries
• Flow fields for swarm behavior
• Level-of-detail AI (distant NPCs tick slower)

Phase G - Waypoint Tooling

• Unity waypoint editor - Visual placement and connection tools
• WaypointGraph component - A* pathfinding in Unity
• Waypoint Network Window - Create circle/square patrol routes
• JSON export/import for waypoint graphs
• Runtime waypoint modification (quests, events)
• Waypoint path visualization in-game (debug mode)

---

References

• Rapier Physics Documentation
• A* Pathfinding (Red Blob Games)
• Flow Field Pathfinding
• Hierarchical Pathfinding (HPA*)