Unit 6: Working with Navmesh

CSE434 — Game Development In 3D 8 min read

I. Orientation: AI Navigation and Networked 3D Worlds

A navigation mesh (navmesh) is a simplified, convex-polygon representation of the walkable surface of a 3D level, used so that agents can reason about "where can I stand and how do I get there" without testing raw geometry. The technique was popularised by Greg Snook's "Simplified 3D Movement and Pathfinding Using Navigation Meshes" (Game Programming Gems, 2000); Unity's implementation is built on the open-source Recast & Detour libraries (Mikko Mononen, 2009) — Recast bakes the mesh by voxelisation, Detour queries it at runtime. This unit pairs that single-machine AI navigation with networked play, because agent movement is one of the largest sources of replicated state in a multiplayer game.

Assumptions and conventions used throughout:

Agent abstraction: every agent is a capsule described by radius, height, step height and max slope; the navmesh is baked per agent type, not per character.
Erosion: the baked surface is shrunk inward by the agent radius, so an agent's centre point can be treated as a dimensionless point during search.
Polygon, not grid: the search graph nodes are convex polygons; a straight line between any two points inside one polygon is guaranteed walkable.
Static vs dynamic: baked geometry is static; moving blockers are handled by NavMeshObstacle carving, not by re-baking.
Server authority (networking): in a multiplayer build, pathfinding is normally executed only on the server/host; clients receive positions.
Units: distances in Unity metres, angles in degrees, speeds in m/s, network rates in Hz (ticks or sends per second).

II. Basics of Navmesh

A. The bake pipeline and its parameters

Baking converts arbitrary triangle soup into a walkable polygon mesh through voxelisation.

Stages: rasterise static geometry into voxels → filter walkable voxel spans by slope and step → build a region/contour set → simplify contours into convex polygons → link neighbouring polygons.
Agent Radius (default 0.5 m): erodes the walkable area away from walls; halving it doubles the number of narrow gaps agents can enter.
Agent Height (2 m) and Step Height (0.4 m): clearance test and the maximum ledge an agent may climb without an off-mesh link.
Max Slope (45°): any triangle steeper than this is discarded as non-walkable.
Voxel Size (advanced): default is agent radius / 3 ≈ 0.166 m; smaller voxels give finer geometry but a much longer bake and larger data.
Tile size (256 voxels default): the navmesh is cut into square tiles so a single tile can be rebuilt at runtime instead of the whole level.

B. Runtime components

NavMeshSurface (AI Navigation package): bakes a surface for one Agent Type, with collectObjects set to All / Volume / Children, and supports BuildNavMesh() at runtime.
NavMeshAgent: steers a character; key fields are speed, angularSpeed (120 °/s), acceleration (8 m/s²), stoppingDistance, autoBraking, obstacleAvoidanceType and avoidancePriority (0–99, lower value = higher priority).
NavMeshObstacle: a moving blocker; with Carve enabled it cuts a hole in the navmesh, re-carving only when it moves more than the Carve Only Stationary threshold (0.1 m default).
OffMeshLink / NavMesh Link: an explicit edge for jumps, ladders and doors, with a cost override so a jump can be made expensive relative to walking.
Areas and costs: up to 32 area types (Walkable = 0, Not Walkable = 1, Jump = 2). An agent's areaMask filters areas; area cost multiplies traversal length (e.g. Water cost 5 makes a 10 m wade equal a 50 m detour).

C. Applications and limitations

Applications: enemy chase and patrol AI, click-to-move RPG control, crowd flow, spawn-point validity tests via NavMesh.SamplePosition.
Limitations: 2.5D only (no true overhangs on the same surface without separate layers), no dynamic geometry without carving or tile rebuild, agents are cylinders so no crouching/prone volumes, and off-mesh traversal animation must be authored manually.

III. Path Finding using Navmesh

A. The search algorithm

Detour runs A* over the polygon graph, using polygon centres (or portal midpoints) as node positions.

TEXT

f(n) = g(n) + h(n)
g(n) = accumulated cost from start to n  (length × areaCost)
h(n) = straight-line distance from n to goal   // admissible heuristic

Node expansion: the open list is a priority queue ordered by f; the first polygon containing the goal point terminates the search.
String pulling (funnel algorithm): the raw polygon corridor is converted to a minimal corner list by dragging a funnel of left/right portal endpoints — this is why NavMeshPath.corners contains only turn points, not every polygon.
Steering: the agent moves toward corners[1], applying local avoidance (RVO-style velocity obstacles) each frame before writing transform.position.

B. Querying paths in code

CSHARP

[SerializeField] Transform target;
NavMeshAgent agent;

void Start() => agent = GetComponent<NavMeshAgent>();

void Update() {
    if (!agent.pathPending &&
         agent.remainingDistance > agent.stoppingDistance)
        agent.SetDestination(target.position);
}

// Validate before committing
bool CanReach(Vector3 dest) {
    var path = new NavMeshPath();
    NavMesh.CalculatePath(transform.position, dest, NavMesh.AllAreas, path);
    return path.status == NavMeshPathStatus.PathComplete;
}

NavMeshPathStatus: PathComplete (goal reached), PathPartial (blocked; ends at nearest point), PathInvalid (no start/end polygon found).
NavMesh.SamplePosition(pos, out hit, maxDistance, mask): snaps an arbitrary world point onto the mesh — essential before SetDestination, since a click on a wall yields a partial path.
agent.Warp(position): teleports and re-links the agent to the correct polygon; setting transform.position directly desynchronises the internal agent.
agent.isStopped / ResetPath(): pause versus discard the corridor.

C. Path quality and failure handling

Partial paths: treat PathPartial as "move as close as possible, then re-evaluate", otherwise agents grind against obstacles.
Repath budget: re-issue SetDestination only when the target has moved more than ~1 m, or on a 0.2–0.5 s timer, rather than every frame.
Crowd deadlock: identical avoidancePriority on many agents causes jitter; stagger priorities, and raise obstacleAvoidanceType only for near-camera agents.

IV. Multiplayer Game Development using Photon / Unity Netcode

A. Architecture fundamentals

Both stacks are authoritative-server models over a topology of one host and n clients; the difference is who runs the simulation and how state is replicated.

Server authority: the server owns AI navmesh agents, health and score; clients send intent (input), not results.
Replication primitives: state synchronisation (continuous, e.g. transforms) and events (discrete, e.g. "fire").
Client-side interpolation: clients render remote objects ~100 ms in the past to smooth over packet jitter.

1. Unity Netcode for GameObjects (NGO)

NetworkManager with a transport (Unity Transport/UTP) starts Host, Server or Client.
NetworkObject gives a spawned prefab a NetworkObjectId and an owner; NetworkBehaviour exposes the sync API.