Pathfinding

Find optimal paths through NavMesh with A* pathfinding, path smoothing algorithms, and path following behaviors.

Overview#

Web Engine's pathfinding system provides:

A* pathfinding on NavMesh
Funnel algorithm for path smoothing
Raycast-based path simplification
Path validation and length calculation
Path following with waypoint navigation
Integration with steering behaviors

Finding Paths#

Basic Pathfinding#

basic-pathfinding.ts

typescript

import { navMeshBridge } from '@web-engine-dev/core/engine/ai';
import * as THREE from 'three';

// Find path between two points
const start = new THREE.Vector3(0, 0, 0);
const end = new THREE.Vector3(10, 0, 10);

const result = await navMeshBridge.findPath(start, end);

if (result.success && result.path) {
  // Convert to Vector3 array
  const waypoints = result.path.map(p =>
    new THREE.Vector3(p.x, p.y, p.z)
  );

  console.log(`Path found with ${waypoints.length} waypoints`);
} else {
  console.error('No path found:', result.error);
}

Snap to NavMesh#

For accurate pathfinding, snap start/end positions to the NavMesh:

snap-to-navmesh.ts

typescript

// Snap positions to NavMesh before pathfinding
const startOnMesh = navMesh.getClosestPoint(start);
const endOnMesh = navMesh.getClosestPoint(end);

if (!startOnMesh || !endOnMesh) {
  console.error('Start or end position not on NavMesh');
  return null;
}

const result = await navMeshBridge.findPath(startOnMesh, endOnMesh);

Path Smoothing#

Funnel Algorithm#

The funnel algorithm creates the shortest path that stays within NavMesh bounds:

funnel-smoothing.ts

typescript

import { smoothPathFunnel } from '@web-engine-dev/core/engine/ai';

// Define portal edges between path segments
const portals = [
  { left: new THREE.Vector3(-1, 0, 5), right: new THREE.Vector3(1, 0, 5) },
  { left: new THREE.Vector3(-1, 0, 10), right: new THREE.Vector3(1, 0, 10) },
  { left: new THREE.Vector3(-1, 0, 15), right: new THREE.Vector3(1, 0, 15) },
];

// Original path from A*
const rawPath = [
  new THREE.Vector3(0, 0, 0),
  new THREE.Vector3(0, 0, 5),
  new THREE.Vector3(0, 0, 10),
  new THREE.Vector3(0, 0, 15),
  new THREE.Vector3(0, 0, 20),
];

// Apply funnel smoothing
const smoothed = smoothPathFunnel(rawPath, portals);

console.log(`Smoothed from ${rawPath.length} to ${smoothed.length} waypoints`);

Raycast Smoothing#

Simplify paths by removing waypoints with direct line-of-sight:

raycast-smoothing.ts

typescript

import { smoothPathRaycast } from '@web-engine-dev/core/engine/ai';

// Define raycast function (checks for obstacles)
const raycast = (start: THREE.Vector3, end: THREE.Vector3) => {
  const direction = new THREE.Vector3().subVectors(end, start);
  const distance = direction.length();
  direction.normalize();

  const raycaster = new THREE.Raycaster(start, direction, 0, distance);
  const intersects = raycaster.intersectObjects(obstacles, true);

  return {
    hit: intersects.length > 0,
    distance: intersects[0]?.distance ?? distance,
  };
};

// Smooth path with raycast validation
const smoothed = smoothPathRaycast(
  rawPath,
  raycast,
  maxIterations: 3  // Number of smoothing passes
);

Path Utilities#

Simplify Path#

Remove waypoints that are too close together:

simplify-path.ts

typescript

import { simplifyPath } from '@web-engine-dev/core/engine/ai';

// Remove points closer than 0.5 units
const simplified = simplifyPath(path, minDistance: 0.5);

// Result: fewer waypoints, smoother movement

Validate Path#

validate-path.ts

typescript

import { validatePath } from '@web-engine-dev/core/engine/ai';

// Check for NaN or infinite values
if (!validatePath(path)) {
  console.error('Invalid path detected');
  return;
}

// Safe to use path

Calculate Path Length#

path-length.ts

typescript

import { calculatePathLength } from '@web-engine-dev/core/engine/ai';

const totalLength = calculatePathLength(path);
console.log(`Path is ${totalLength.toFixed(2)} units long`);

// Use for travel time estimation
const speed = 5.0; // units per second
const estimatedTime = totalLength / speed;

Get Position Along Path#

position-along-path.ts

typescript

import { getPositionAlongPath } from '@web-engine-dev/core/engine/ai';

// Get position at distance 10 units along path
const position = getPositionAlongPath(path, distance: 10.0);

if (position) {
  console.log('Position:', position);
}

// Use for look-ahead in path following
const lookAheadDistance = 5.0;
const lookAheadPos = getPositionAlongPath(path, currentDistance + lookAheadDistance);

Path Following#

Basic Path Following#

basic-following.ts

typescript

import { SteeringBehaviors } from '@web-engine-dev/core/engine/ai';
import { Transform, Velocity } from '@web-engine-dev/core/engine/ecs/components';

// Path following state
let currentWaypointIndex = 0;
const waypointRadius = 1.0;

function followPath(eid: number, path: THREE.Vector3[], delta: number) {
  if (currentWaypointIndex >= path.length) {
    return; // Path complete
  }

  const agent = {
    position: Transform.position[eid],
    velocity: Velocity.linear[eid],
    maxSpeed: 5.0,
    maxForce: 10.0,
    radius: 0.5,
    mass: 1.0,
  };

  const target = {
    position: path[currentWaypointIndex],
  };

  // Use arrive behavior for smoother movement
  const result = SteeringBehaviors.arrive(agent, target, slowingRadius: 2.0);

  if (result.active) {
    // Apply steering force
    Velocity.linear[eid][0] += result.force.x * delta;
    Velocity.linear[eid][1] += result.force.y * delta;
    Velocity.linear[eid][2] += result.force.z * delta;
  }

  // Check if reached waypoint
  const agentPos = new THREE.Vector3().fromArray(agent.position);
  const waypointPos = new THREE.Vector3().fromArray(target.position);
  const distance = agentPos.distanceTo(waypointPos);

  if (distance < waypointRadius) {
    currentWaypointIndex++;
  }
}

Advanced Path Following with Steering#

advanced-following.ts

typescript

import { SteeringBehaviors, SteeringPath } from '@web-engine-dev/core/engine/ai';

// Create steering path
const steeringPath: SteeringPath = {
  points: waypoints,
  looped: false,
  radius: 1.0,
};

let currentIndex = 0;

function updatePathFollowing(eid: number, delta: number) {
  const agent = {
    position: Transform.position[eid],
    velocity: Velocity.linear[eid],
    maxSpeed: 5.0,
    maxForce: 10.0,
    radius: 0.5,
    mass: 1.0,
  };

  // Use pathFollowing behavior
  const { result, nextIndex } = SteeringBehaviors.pathFollowing(
    agent,
    steeringPath,
    currentIndex
  );

  currentIndex = nextIndex;

  if (result.active) {
    // Apply force
    Velocity.linear[eid][0] += result.force.x * delta;
    Velocity.linear[eid][1] += result.force.y * delta;
    Velocity.linear[eid][2] += result.force.z * delta;
  }

  // Check if path complete
  if (currentIndex >= steeringPath.points.length - 1 && !steeringPath.looped) {
    onPathComplete(eid);
  }
}

Integration with Behavior Trees#

Path Following Action#

bt-path-following.ts

typescript

import { BTAction, BTStatus, BTContext } from '@web-engine-dev/core/engine/ai';

const followPathAction = new BTAction('followPath', (ctx: BTContext) => {
  const path = ctx.blackboard.get<THREE.Vector3[]>('path');
  const waypointIndex = ctx.blackboard.get<number>('waypointIndex') ?? 0;

  if (!path || path.length === 0) {
    return BTStatus.FAILURE;
  }

  if (waypointIndex >= path.length) {
    ctx.blackboard.delete('path');
    ctx.blackboard.delete('waypointIndex');
    return BTStatus.SUCCESS; // Path complete
  }

  // Get agent and target
  const agent = {
    position: Transform.position[ctx.eid],
    velocity: Velocity.linear[ctx.eid],
    maxSpeed: 5.0,
    maxForce: 10.0,
    radius: 0.5,
    mass: 1.0,
  };

  const target = { position: path[waypointIndex] };

  // Apply steering
  const result = SteeringBehaviors.arrive(agent, target, slowingRadius: 2.0);

  if (result.active) {
    Velocity.linear[ctx.eid][0] += result.force.x * ctx.delta;
    Velocity.linear[ctx.eid][1] += result.force.y * ctx.delta;
    Velocity.linear[ctx.eid][2] += result.force.z * ctx.delta;
  }

  // Check waypoint reached
  const agentPos = new THREE.Vector3().fromArray(agent.position);
  const waypointPos = new THREE.Vector3().fromArray(target.position);

  if (agentPos.distanceTo(waypointPos) < 1.0) {
    ctx.blackboard.set('waypointIndex', waypointIndex + 1);
  }

  return BTStatus.RUNNING;
});

Pathfinding Action#

bt-pathfinding.ts

typescript

import { BTAction, BTStatus } from '@web-engine-dev/core/engine/ai';

const findPathAction = new BTAction('findPath', async (ctx: BTContext) => {
  const targetPos = ctx.blackboard.get<THREE.Vector3>('targetPosition');

  if (!targetPos) {
    return BTStatus.FAILURE;
  }

  const agentPos = new THREE.Vector3().fromArray(Transform.position[ctx.eid]);

  // Find path
  const result = await navMeshBridge.findPath(agentPos, targetPos);

  if (result.success && result.path) {
    const waypoints = result.path.map(p =>
      new THREE.Vector3(p.x, p.y, p.z)
    );

    // Store path in blackboard
    ctx.blackboard.set('path', waypoints);
    ctx.blackboard.set('waypointIndex', 0);

    return BTStatus.SUCCESS;
  }

  return BTStatus.FAILURE;
});

// Use in behavior tree
const moveToTargetSequence = new BTSequence([
  new BTCondition('hasTarget', (ctx) => ctx.blackboard.has('targetPosition')),
  findPathAction,
  followPathAction,
]);

Dynamic Pathfinding#

Replanning#

Recalculate paths when obstacles change or target moves:

replanning.ts

typescript

// Replan threshold - distance target must move to trigger replan
const replanThreshold = 5.0;

// Track last path calculation
let lastTargetPosition: THREE.Vector3 | null = null;
let lastPathTime = 0;
const minReplanInterval = 1.0; // seconds

function shouldReplan(
  currentTarget: THREE.Vector3,
  time: number
): boolean {
  if (!lastTargetPosition) return true;

  // Check time threshold
  if (time - lastPathTime < minReplanInterval) {
    return false;
  }

  // Check distance threshold
  const distance = currentTarget.distanceTo(lastTargetPosition);
  return distance > replanThreshold;
}

// In update loop
if (shouldReplan(targetPosition, time)) {
  const result = await navMeshBridge.findPath(agentPos, targetPosition);

  if (result.success && result.path) {
    currentPath = result.path;
    lastTargetPosition = targetPosition.clone();
    lastPathTime = time;
  }
}

Obstacle Avoidance During Path Following#

path-with-avoidance.ts

typescript

import { SteeringCombiner, SteeringPriority } from '@web-engine-dev/core/engine/ai';

function followPathWithAvoidance(
  eid: number,
  path: THREE.Vector3[],
  obstacles: SteeringObstacle[]
) {
  const agent = {
    position: Transform.position[eid],
    velocity: Velocity.linear[eid],
    maxSpeed: 5.0,
    maxForce: 10.0,
    radius: 0.5,
    mass: 1.0,
  };

  const combiner = new SteeringCombiner();

  // High priority: avoid obstacles
  const avoidance = SteeringBehaviors.obstacleAvoidance(
    agent,
    obstacles,
    lookAhead: 5.0
  );
  combiner.add('avoidance', SteeringPriority.Critical, 1.0, avoidance.force, avoidance.active);

  // Normal priority: follow path
  const pathFollowing = SteeringBehaviors.pathFollowing(
    agent,
    { points: path, looped: false, radius: 1.0 },
    currentWaypointIndex
  );
  combiner.add('pathFollow', SteeringPriority.Normal, 1.0, pathFollowing.result.force, pathFollowing.result.active);

  // Calculate combined force (priority-based)
  const finalForce = combiner.calculatePrioritized(agent.maxForce);

  // Apply force
  Velocity.linear[eid][0] += finalForce.x * delta;
  Velocity.linear[eid][1] += finalForce.y * delta;
  Velocity.linear[eid][2] += finalForce.z * delta;

  combiner.clear();
}

Performance Tips#

Path Caching#

path-caching.ts

typescript

// Cache paths for common routes
const pathCache = new Map<string, THREE.Vector3[]>();

function getCachedPath(
  start: THREE.Vector3,
  end: THREE.Vector3
): THREE.Vector3[] | null {
  const key = `${start.toArray().join(',')}->${end.toArray().join(',')}`;
  return pathCache.get(key) ?? null;
}

function cachePath(
  start: THREE.Vector3,
  end: THREE.Vector3,
  path: THREE.Vector3[]
): void {
  const key = `${start.toArray().join(',')}->${end.toArray().join(',')}`;
  pathCache.set(key, path);
}

// Clear cache when NavMesh changes
function clearPathCache() {
  pathCache.clear();
}

Async Pathfinding#

Always use async pathfinding to avoid blocking the main thread:

async-pathfinding.ts

typescript

// Queue pathfinding requests
const pathRequests = new Map<number, Promise<PathResult>>();

async function requestPath(
  eid: number,
  start: THREE.Vector3,
  end: THREE.Vector3
): Promise<void> {
  // Avoid duplicate requests
  if (pathRequests.has(eid)) {
    return;
  }

  const promise = navMeshBridge.findPath(start, end);
  pathRequests.set(eid, promise);

  const result = await promise;
  pathRequests.delete(eid);

  if (result.success && result.path) {
    // Store path for entity
    const waypoints = result.path.map(p =>
      new THREE.Vector3(p.x, p.y, p.z)
    );

    setBlackboardValue(
      AIAgent.blackboardId[eid],
      'path',
      waypoints
    );
  }
}

Example: Complete Pathfinding Setup#

complete-pathfinding.ts

typescript

import {
  navMeshBridge,
  smoothPathRaycast,
  simplifyPath,
  validatePath,
  SteeringBehaviors,
} from '@web-engine-dev/core/engine/ai';

async function setupPathfinding(
  eid: number,
  targetPosition: THREE.Vector3
) {
  // 1. Get agent position
  const agentPos = new THREE.Vector3().fromArray(Transform.position[eid]);

  // 2. Find path
  const result = await navMeshBridge.findPath(agentPos, targetPosition);

  if (!result.success || !result.path) {
    console.error('Pathfinding failed');
    return;
  }

  // 3. Convert to Vector3 array
  let waypoints = result.path.map(p =>
    new THREE.Vector3(p.x, p.y, p.z)
  );

  // 4. Smooth path
  waypoints = smoothPathRaycast(waypoints, raycastFunction, maxIterations: 2);

  // 5. Simplify path
  waypoints = simplifyPath(waypoints, minDistance: 0.5);

  // 6. Validate path
  if (!validatePath(waypoints)) {
    console.error('Invalid path generated');
    return;
  }

  // 7. Store in blackboard
  const blackboardId = AIAgent.blackboardId[eid];
  setBlackboardValue(blackboardId, 'path', waypoints);
  setBlackboardValue(blackboardId, 'waypointIndex', 0);

  console.log(`Path generated with ${waypoints.length} waypoints`);
}

// In game loop
function updatePathFollowing(eid: number, delta: number) {
  const blackboardId = AIAgent.blackboardId[eid];
  const path = getBlackboardValue<THREE.Vector3[]>(blackboardId, 'path');
  const waypointIndex = getBlackboardValue<number>(blackboardId, 'waypointIndex') ?? 0;

  if (!path || waypointIndex >= path.length) {
    return; // No path or complete
  }

  const agent = {
    position: Transform.position[eid],
    velocity: Velocity.linear[eid],
    maxSpeed: 5.0,
    maxForce: 10.0,
    radius: 0.5,
    mass: 1.0,
  };

  const target = { position: path[waypointIndex] };
  const result = SteeringBehaviors.arrive(agent, target, slowingRadius: 2.0);

  if (result.active) {
    Velocity.linear[eid][0] += result.force.x * delta;
    Velocity.linear[eid][1] += result.force.y * delta;
    Velocity.linear[eid][2] += result.force.z * delta;
  }

  // Check waypoint reached
  const agentPos = new THREE.Vector3().fromArray(agent.position);
  const waypointPos = new THREE.Vector3().fromArray(target.position);

  if (agentPos.distanceTo(waypointPos) < 1.0) {
    setBlackboardValue(blackboardId, 'waypointIndex', waypointIndex + 1);
  }
}

PreviousNavigation MeshGenerate NavMesh for pathfinding NextSteering BehaviorsAutonomous movement with steering

Web Engine Docs

Preparing documentation

Documentation0%

Use the search bar to quickly find any topic

Content

Examples

Ready

Web Engine v0.1.0-alpha

Edit this page on GitHub

Last updated: 1/15/2026

Was this page helpful?