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 pathfindingNextSteering BehaviorsAutonomous movement with steering
Documentation | Web Engine