跳转到内容
ESEngine

增量寻路

增量寻路 (Incremental Pathfinding) 允许将寻路计算分散到多帧执行，避免阻塞主线程，适合大量代理同时寻路的场景。

核心特性

Section titled “核心特性”
  • 时间切片 - 每帧执行有限次迭代
  • 暂停/恢复 - 随时暂停和恢复搜索
  • 动态重规划 - 障碍物变化时自动处理
  • 路径缓存 - 可选的结果缓存

基础用法

Section titled “基础用法”
import {
    createIncrementalAStarPathfinder,
    PathfindingState,
    GridMap
} from '@esengine/pathfinding';


const grid = new GridMap(200, 200);
const pathfinder = createIncrementalAStarPathfinder(grid);


// 1. 请求寻路（非阻塞）
const request = pathfinder.requestPath(0, 0, 199, 199);
console.log('Request ID:', request.id);


// 2. 每帧执行一定次数的迭代
function gameLoop() {
    const progress = pathfinder.step(request.id, 100); // 每帧 100 次迭代


    console.log('Progress:', (progress.estimatedProgress * 100).toFixed(1) + '%');


    if (progress.state === PathfindingState.Completed) {
        const result = pathfinder.getResult(request.id);
        console.log('Path found!', result?.path);
        pathfinder.cleanup(request.id); // 清理资源
    } else if (progress.state === PathfindingState.InProgress) {
        requestAnimationFrame(gameLoop);
    } else {
        console.log('Failed or cancelled');
    }
}


gameLoop();

状态管理

Section titled “状态管理”

PathfindingState 枚举

Section titled “PathfindingState 枚举”
状态说明
Idle空闲，未开始
InProgress搜索进行中
Paused已暂停
Completed搜索完成，找到路径
Failed搜索完成，未找到路径
Cancelled已取消

暂停和恢复

Section titled “暂停和恢复”
const request = pathfinder.requestPath(0, 0, 199, 199);


// 执行一些步骤
pathfinder.step(request.id, 500);


// 暂停
pathfinder.pause(request.id);
console.log(pathfinder.getProgress(request.id)?.state); // 'paused'


// 恢复
pathfinder.resume(request.id);
pathfinder.step(request.id, 500); // 继续执行

取消请求

Section titled “取消请求”
const request = pathfinder.requestPath(0, 0, 199, 199);


// 不需要这个路径了
pathfinder.cancel(request.id);


// 清理资源
pathfinder.cleanup(request.id);

多代理管理

Section titled “多代理管理”

优先级队列模式

Section titled “优先级队列模式”
class PathfindingManager {
    private pathfinder: IncrementalAStarPathfinder;
    private requests: Map<number, { id: number; priority: number; entityId: string }>;
    private budgetPerFrame = 2000; // 每帧总迭代预算


    requestPath(entityId: string, sx: number, sy: number, ex: number, ey: number, priority = 50) {
        const request = this.pathfinder.requestPath(sx, sy, ex, ey);
        this.requests.set(request.id, { id: request.id, priority, entityId });
        return request.id;
    }


    update() {
        // 按优先级排序
        const sorted = [...this.requests.values()].sort((a, b) => b.priority - a.priority);


        let budget = this.budgetPerFrame;
        const iterPerAgent = Math.max(10, Math.floor(budget / sorted.length));


        for (const req of sorted) {
            if (budget <= 0) break;


            const progress = this.pathfinder.getProgress(req.id);
            if (!progress || progress.state !== PathfindingState.InProgress) continue;


            this.pathfinder.step(req.id, iterPerAgent);
            budget -= iterPerAgent;
        }
    }
}

ECS 集成

Section titled “ECS 集成”

如需在 ECS 框架中使用增量寻路，推荐使用 NavigationSystem 的时间切片功能：

import {
    NavigationSystem,
    NavigationAgentComponent,
    createIncrementalAStarPlanner
} from '@esengine/pathfinding/ecs';
import { createGridMap } from '@esengine/pathfinding';


const gridMap = createGridMap(200, 200);


// 创建增量寻路适配器
const planner = createIncrementalAStarPlanner(gridMap, undefined, {
    cellSize: 20
});


// 启用时间切片
const navSystem = new NavigationSystem({
    enableTimeSlicing: true,     // 启用时间切片
    iterationsBudget: 1000,      // 每帧总迭代预算
    maxAgentsPerFrame: 10,       // 每帧最大处理代理数
    maxIterationsPerAgent: 200   // 每代理每帧最大迭代数
});


navSystem.setPathPlanner(planner);
scene.addSystem(navSystem);


// 创建代理
const entity = scene.createEntity('Agent');
const nav = entity.addComponent(new NavigationAgentComponent());
nav.priority = 10;  // 高优先级，优先分配迭代预算
nav.setDestination(100, 100);


// 检查寻路状态
if (nav.isComputingPath) {
    console.log(`寻路进度: ${(nav.pathProgress * 100).toFixed(0)}%`);
}

详细文档请参阅 统一导航系统。

动态重规划

Section titled “动态重规划”

障碍物变化通知

Section titled “障碍物变化通知”
const pathfinder = createIncrementalAStarPathfinder(grid);


// 创建寻路请求
const request = pathfinder.requestPath(0, 0, 99, 99);
pathfinder.step(request.id, 500);


// 动态添加障碍物
grid.setWalkable(50, 50, false);


// 通知寻路器障碍物变化区域
pathfinder.notifyObstacleChange(45, 45, 55, 55);


// 继续执行 - 检查请求是否受影响
if (pathfinder.isAffectedByChange(request.id)) {
    console.log('Path may be affected by obstacle change');
    // 可以选择取消并重新请求，或继续执行
    pathfinder.clearChangeFlag(request.id); // 清除标记
}

路径验证器

Section titled “路径验证器”
import { createPathValidator } from '@esengine/pathfinding';


const validator = createPathValidator(grid);


// 验证现有路径
const path = result.path;
const validation = validator.validate(path);


if (!validation.valid) {
    console.log('Path blocked at index:', validation.blockedIndex);
    console.log('Blocked point:', validation.blockedPoint);
    // 需要重新寻路
}

路径缓存

Section titled “路径缓存”

启用缓存可大幅提升重复查询性能：

const pathfinder = createIncrementalAStarPathfinder(grid, {
    enableCache: true,
    cacheConfig: {
        maxEntries: 1000,  // 最大缓存数
        ttlMs: 60000,      // 过期时间 60 秒
    }
});


// 第一次请求 - 实际计算
const req1 = pathfinder.requestPath(0, 0, 99, 99);
pathfinder.step(req1.id, 10000);


// 第二次相同请求 - 从缓存返回
const req2 = pathfinder.requestPath(0, 0, 99, 99);
pathfinder.step(req2.id, 10000); // 立即完成


// 查看缓存统计
const stats = pathfinder.getCacheStats();
console.log('Hit rate:', (stats.hitRate * 100).toFixed(1) + '%');

配置选项

Section titled “配置选项”
interface IIncrementalPathfinderConfig {
    maxNodes?: number;        // 最大搜索节点数，默认 10000
    heuristicWeight?: number; // 启发式权重，默认 1.0
    enableCache?: boolean;    // 启用缓存，默认 false
    cacheConfig?: IPathCacheConfig; // 缓存配置
}


const pathfinder = createIncrementalAStarPathfinder(grid, {
    maxNodes: 50000,
    heuristicWeight: 1.2,
    enableCache: true,
    cacheConfig: {
        maxEntries: 500,
        ttlMs: 30000
    }
});

性能调优

Section titled “性能调优”

迭代次数选择

Section titled “迭代次数选择”
场景建议每帧迭代数说明
单个代理500-20001-2 帧完成
10 个代理总计 2000每个约 200
100 个代理总计 2000-5000每个约 20-50
1000 个代理总计 5000-10000分批处理

帧时间预算

Section titled “帧时间预算”
class AdaptivePathfinding {
    private targetFrameTime = 2; // 目标帧时间 2ms
    private iterationsPerStep = 100;


    step(requestId: number) {
        const start = performance.now();
        this.pathfinder.step(requestId, this.iterationsPerStep);
        const elapsed = performance.now() - start;


        // 自适应调整迭代次数
        if (elapsed < this.targetFrameTime * 0.8) {
            this.iterationsPerStep = Math.min(1000, this.iterationsPerStep + 10);
        } else if (elapsed > this.targetFrameTime) {
            this.iterationsPerStep = Math.max(10, this.iterationsPerStep - 20);
        }
    }
}

完整示例

Section titled “完整示例”

游戏中的代理移动

Section titled “游戏中的代理移动”
class Agent {
    x: number;
    y: number;
    path: IPoint[] = [];
    pathIndex = 0;
    requestId?: number;


    private pathfinder: IncrementalAStarPathfinder;


    moveTo(targetX: number, targetY: number) {
        // 取消之前的请求
        if (this.requestId !== undefined) {
            this.pathfinder.cancel(this.requestId);
            this.pathfinder.cleanup(this.requestId);
        }


        // 请求新路径
        const request = this.pathfinder.requestPath(
            Math.floor(this.x),
            Math.floor(this.y),
            targetX,
            targetY
        );
        this.requestId = request.id;
        this.pathIndex = 0;
    }


    update(dt: number) {
        // 处理寻路
        if (this.requestId !== undefined) {
            const progress = this.pathfinder.step(this.requestId, 100);


            if (progress.state === PathfindingState.Completed) {
                const result = this.pathfinder.getResult(this.requestId);
                this.path = result?.path ?? [];
                this.pathfinder.cleanup(this.requestId);
                this.requestId = undefined;
            }
        }


        // 沿路径移动
        if (this.path.length > 0 && this.pathIndex < this.path.length) {
            const target = this.path[this.pathIndex];
            const dx = target.x - this.x;
            const dy = target.y - this.y;
            const dist = Math.sqrt(dx * dx + dy * dy);


            if (dist < 0.1) {
                this.pathIndex++;
            } else {
                const speed = 5 * dt;
                this.x += (dx / dist) * speed;
                this.y += (dy / dist) * speed;
            }
        }
    }
}

相关文档

Section titled “相关文档”
赣ICP备2025064788号-2