29. NPC Movement Optimisation

Pathfinding entities don't need collision detection. They follow pre-validated paths that already avoid obstacles.

This seemingly minor optimisation yields significant performance benefits and solves difficult terrain navigation.

The Fractal Code Cycle Applied to Pathfinding Optimisation

Recall our fundamental pattern:

Input → Processing → Output

For pathfinding entity physics:

• Input: Entity noclip flag status, waypoint positions, velocity

• Processing: Skip collision detection for noclip entities, apply velocity directly

• Output: Updated entity positions without collision overhead

The Problem

Pathfinding entities were running through the full collision system despite following paths that already avoid obstacles.

Observed Issues:

• Entities getting stuck on terrain elevation changes

• Wasted CPU cycles checking collisions that would never occur

• Frame rate drops when multiple pathfinding entities were active

The Solution: Noclip Flag

Add a flag to bypass collision detection for entities following pre-validated paths:

Entity_Flag :: enum {
    Sprite,
    Waypoints,
    Noclip,
}

Physics System Changes

The physics update now checks the noclip flag:

physics_update :: proc(ws: ^Scene_State) {
    for &entity in ws.entities {
        if .Noclip in entity.flags {
            entity.position += entity.velocity
        } else {
            entity.position = physics_calculate_next_position(
                ws,
                entity.position,
                entity.velocity,
                entity.collider_radius,
            )
        }
    }
}

Noclip entities skip the entire collision detection and response pipeline.

Performance Impact

Measured on 100 entities over multiple frames:

Before (with collision):

• 870 microseconds per physics update

• When combined with debug rendering, exceeded 16.67ms frame budget

• Frame rate dropped by ~10 FPS

After (noclip enabled):

• 2.475 microseconds per physics update

• 351x performance improvement

• Frame rate stable at 60 FPS

Why This Works

Navgrid paths are already obstacle-aware. The grid generation samples collision geometry, so valid paths never intersect with static obstacles.

What noclip entities skip:

• Sphere vs OBB3 collision detection

• Coordinate space transformations

• Iterative collision response calculations

• Ground sampling (handled by waypoint elevation)

What they retain:

• Path following logic

• Waypoint progression

• Movement velocity

Waypoint Optimisation

The path generation was also optimised to reduce redundant waypoints:

waypoints_from_path :: proc(ng: Navgrid, path: []int, allocator := context.allocator) -> []Vec3 {
    if len(path) == 0 do return nil

    points := make([dynamic]Vec3, allocator)

    i := 0
    for i < len(path) {
        curr_pos := ng.graph.nodes[path[i]].pos
        append(&points, curr_pos)
        if i + 1 >= len(path) do break

        next_pos := ng.graph.nodes[path[i + 1]].pos

        dx := next_pos.x != curr_pos.x
        dy := next_pos.y != curr_pos.y

        i += 1
        for i < len(path) - 1 {
            curr_pos := ng.graph.nodes[path[i]].pos
            next_pos := ng.graph.nodes[path[i + 1]].pos
            curr_dx := curr_pos.x != next_pos.x
            curr_dy := curr_pos.y != next_pos.y
            if curr_dx != dx || curr_dy != dy do break
            i += 1
        }
    }

    return points[:]
}

This greedy algorithm eliminates waypoints along straight paths, keeping only direction changes.

Waypoint Following Simplification

With noclip enabled, waypoint following becomes straightforward:

if .Waypoints in entity.flags && len(entity.waypoints) > 0 {
    dist_check := entity.movement_speed * dt
    dest := entity.waypoints[entity.waypoint_index]
    dest.y += entity.collider_radius

    dir := rl.Vector3Normalize(dest - entity.position)
    entity.velocity = dir * entity.movement_speed * dt
    dist := rl.Vector3Length(dest - entity.position)
    
    if dist < dist_check {
        entity.waypoint_index = entity.waypoint_index + 1
        if entity.waypoint_index == len(entity.waypoints) {
            entity.waypoint_index = 0
        }
    }
}

No ground sampling, no XZ plane restrictions. Direct 3D movement to waypoints.

The Performance Threshold Principle

Small overheads compound. Individual systems may seem cheap, but when frame time approaches 16.67ms, any overhead can cause drops below 60 FPS.

The 870 microseconds wasn't "expensive" by itself, but combined with debug rendering overhead, it pushed total frame time over budget.

Optimising it to 2.475 microseconds created enough headroom to maintain stable frame rate.

Design Implications

When to use noclip:

• Entities following navgrid paths

• Movement guaranteed not to intersect obstacles

• NPC patrol routes

• Quest-directed entity movement

When to use collision:

• Player-controlled entities

• Dynamic obstacle interaction required

• Physics-based gameplay mechanics

• Entities that can be pushed or blocked

The Big Idea

Domain-specific optimisations outperform general solutions. Pathfinding entities don't need full physics simulation because their movement is already constrained by the navgrid.

The 351x performance gain demonstrates how architectural decisions (separating collision from movement) enable targeted optimisations that would be impossible in tightly coupled systems.