28. Navigation and Pathfinding

Every NPC that walks from the market to the tavern, every enemy that chases you through town, every character that navigates around obstacles - all rely on pathfinding algorithms that transform spatial problems into traversable routes.

The Fractal Code Cycle Applied to Navigation

Recall our fundamental pattern:

Input → Processing → Output

For our navigation system:

• Input: Start position, goal position, walkable surfaces, obstacles
• Processing: Generate navigation grid, calculate optimal path using A*
• Output: Sequence of waypoints from start to goal

What Is Navigation Good For?

NPC Movement

• Characters walking between locations
• Enemies pursuing the player
• Scheduled NPC routines (going to work, returning home)

Dynamic Behaviour

• Avoiding obstacles in real-time
• Responding to changing environments
• Following complex patrol routes

Gameplay Mechanics

• Escort missions where NPCs follow the player
• Enemy formations and tactical movement
• Quest objectives requiring navigation

The Navigation Grid Concept

Rather than calculating paths through continuous 3D space, we discretise the world into a grid of traversable nodes. This transforms the spatial problem into a graph traversal problem.

Grid Generation

The navgrid generation process:

1. Sample the ground plane: For each walkable surface (quad), create a grid of potential nodes
2. Filter by obstacles: Reject nodes too close to static geometry
3. Connect neighbours: Create edges between adjacent valid nodes
4. Store in graph structure: Maintain nodes and edges for pathfinding queries

From the implementation:

navgrid_generate :: proc(
    ground: []Quad,
    obstacles: []OBB3,
    allocator := context.allocator,
) -> Navgrid {
    MIN_OBSTACLE_DIST :: f32(0.5)
    MAX_EDGE_DIST :: f32(2.1)
    
    // Create nodes on ground surfaces
    // Filter out nodes near obstacles
    // Connect valid neighbours
    // Return completed navgrid
}

Spatial Hashing for Efficiency

To avoid checking every node against every other node during edge creation, we use spatial hashing:

spatial_map := make(map[Vec3i][dynamic]int, context.temp_allocator)

This groups nodes by their rounded world position, allowing us to only check nearby cells when creating edges.

The Graph Data Structure

Navigation requires a generic graph structure to represent nodes and edges. We've created a reusable graph package:

Graph :: struct($T: typeid) {
    nodes:     [dynamic]T,
    edges:     map[int][dynamic]int,
    allocator: mem.Allocator,
}

This generic structure allows us to store any node type (in our case, Navgrid_Node containing position data) whilst maintaining efficient edge lookups via the map.

Graph Operations

The graph package provides fundamental operations:

• init: Initialise the graph with an allocator
• add: Add a node, returning its index
• connect_by_index: Create an edge between nodes
• neighbors: Retrieve connected nodes

A* Pathfinding Algorithm

A* (pronounced "A-star") is the industry standard pathfinding algorithm. It combines:

• Dijkstra's algorithm: Finds the shortest path by exploring nodes in order of cost from start
• Greedy best-first search: Prioritises nodes that appear closest to the goal

The key is the priority function:

priority = cost_so_far + heuristic(current, goal)

Implementation Structure

astar :: proc(
    ng: Navgrid,
    start_idx: int,
    goal_idx: int,
    heuristic: proc(ng: Navgrid, a, b: int) -> f32 = nav_default_heuristic,
    less: proc(a, b: Nav_Path_Node) -> bool = nav_default_less,
    allocator := context.allocator,
) -> (path: [dynamic]int, ok: bool)

The Algorithm Steps

1. Initialise frontier: Priority queue with start node
2. Track visited nodes: Map from node index to previous node
3. Track costs: Map from node index to accumulated cost
4. Expand frontier: Process lowest-cost node, adding unvisited neighbours
5. Reconstruct path: Backtrack from goal to start using the came_from map

Heuristic Function

Our heuristic estimates distance to goal whilst preferring flatter terrain:

nav_default_heuristic :: proc(ng: Navgrid, a, b: int) -> f32 {
    VERTICAL_WEIGHT :: f32(-2)
    diff := ng.graph.nodes[b].pos - ng.graph.nodes[a].pos
    return math.sqrt(diff.x * diff.x + diff.y * diff.y * VERTICAL_WEIGHT + diff.z * diff.z)
}

The negative vertical weight encourages paths that minimise elevation changes.

Integration with Entities

Waypoint System Modifications

Entities now use dynamic slices for waypoints instead of fixed arrays:

Entity :: struct {
    // ...
    waypoints:        []Vec3,  // Changed from [8]Vec3
    waypoint_count:   int,
    waypoint_index:   int,
    // ...
}

Waypoint Following Behaviour

The entity update loop now handles waypoint reversal for patrol routes:

if entity.waypoint_index == len(entity.waypoints) {
    entity.waypoint_index = 0
    slice.reverse(entity.waypoints)
}

This creates natural back-and-forth patrol behaviour.

Path to Waypoints Conversion

A simple conversion function extracts world positions from path indices:

waypoints_from_path :: proc(ng: Navgrid, path: []int, allocator := context.allocator) -> []Vec3 {
    points := make([]Vec3, len(path), allocator)
    for idx, i in path {
        points[i] = ng.graph.nodes[idx].pos
    }
    return points
}

Vertical Movement Constraints

The navigation system respects vertical step limits when connecting nodes:

MAX_STEP_HEIGHT :: 1.0

if abs(pa.y - pb.y) > MAX_STEP_HEIGHT do continue

This prevents paths that require unrealistic vertical traversal.

Debug Visualisation

The implementation includes comprehensive debug rendering:

Navigation Grid

• Red boxes show all valid navigation nodes
• Cyan lines show graph edges

Active Paths

• Yellow boxes highlight the current path
• Entity waypoints shown as yellow bounding boxes

This visualisation is critical for verifying that:

• The navgrid covers walkable areas
• Obstacles properly block navigation
• Generated paths make sense spatially

Navigation System in the System Stack

Recall our System Stack organisation:

• Base Layer: Entities, Input, Time, Assets, Save/Load
• Presentation: Camera, Shaders, Animation, UI, Particles
• Interaction: Player, Collisions, AI/Pathfinding, Scenes
• Game Systems: Stats, Combat, Inventory, Abilities
• Content: Dialogue, Quests, NPC Schedules

Navigation sits in the World Layer because:

1. It depends on scene geometry (walkable surfaces, obstacles)
2. It depends on entities (for positioning and movement)
3. It provides services to AI and NPC systems
4. It enables higher-level gameplay systems (quests, schedules)

Design Considerations

Grid Resolution Trade-offs

Finer grids (smaller cell size):

• More accurate paths
• Smoother movement
• Higher memory usage
• Slower pathfinding

Coarser grids (larger cell size):

• Less memory usage
• Faster pathfinding
• More angular paths
• Potential gaps in coverage

Our implementation uses 1-metre cells, suitable for our game scale.

Diagonal Movement

The current implementation disables diagonal connections:

is_diagonal := pa.x != pb.x && pa.z != pb.z
if is_diagonal do continue

This simplifies pathfinding and creates more natural-looking movement for the game's isometric perspective. Enable diagonals if your game requires smoother, more direct paths.

Dynamic vs Static Navgrids

Our current approach generates the navgrid once during scene load. This works well for static environments but doesn't handle:

• Moving obstacles (doors, platforms)
• Destructible terrain
• Dynamic quest objects

For dynamic navigation, you'd need to:

• Regenerate portions of the grid
• Maintain multiple navgrids (one per configuration)
• Use hierarchical pathfinding for large worlds

Performance Optimisation Opportunities

Spatial Partitioning: The current implementation uses basic spatial hashing. For larger worlds, consider hierarchical spatial structures.

Path Caching: Frequently requested paths (between common locations) could be cached.

Hierarchical Pathfinding: Large worlds benefit from multi-level navigation - coarse paths between regions, fine paths within regions.

Path Smoothing: A* paths follow grid edges exactly. Post-processing can create smoother, more natural-looking routes.

Try It Yourself

1. Modify the heuristic function to heavily favour paths near walls (useful for stealth games)
2. Implement path smoothing that removes unnecessary waypoints when line-of-sight exists
3. Add support for diagonal movement and observe how it affects path quality
4. Create a "difficulty map" that makes certain terrain types have higher traversal costs

The Big Idea

Pathfinding transforms continuous spatial navigation into discrete graph traversal. By pre-computing a navigation grid and using A* to find optimal paths, we enable intelligent NPC movement whilst maintaining reasonable performance.

The key insight is the separation of concerns: navgrid generation happens once per scene, pathfinding happens on-demand, and entity movement consumes pre-computed waypoints. Each system focuses on its specific responsibility within the larger navigation pipeline.