寻路系统 (Pathfinding)

@esengine/pathfinding 提供了完整的 2D 寻路解决方案，包括 A* 算法、网格地图、导航网格和路径平滑。

安装

npm install @esengine/pathfinding

快速开始

网格地图寻路

import { createGridMap, createAStarPathfinder } from '@esengine/pathfinding';

// 创建 20x20 的网格地图
const grid = createGridMap(20, 20);

// 设置障碍物
grid.setWalkable(5, 5, false);
grid.setWalkable(5, 6, false);
grid.setWalkable(5, 7, false);

// 创建寻路器
const pathfinder = createAStarPathfinder(grid);

// 查找路径
const result = pathfinder.findPath(0, 0, 15, 15);

if (result.found) {
    console.log('找到路径！');
    console.log('路径点:', result.path);
    console.log('总代价:', result.cost);
    console.log('搜索节点数:', result.nodesSearched);
}

导航网格寻路

import { createNavMesh } from '@esengine/pathfinding';

// 创建导航网格
const navmesh = createNavMesh();

// 添加多边形区域
navmesh.addPolygon([
    { x: 0, y: 0 }, { x: 10, y: 0 },
    { x: 10, y: 10 }, { x: 0, y: 10 }
]);

navmesh.addPolygon([
    { x: 10, y: 0 }, { x: 20, y: 0 },
    { x: 20, y: 10 }, { x: 10, y: 10 }
]);

// 自动建立连接
navmesh.build();

// 寻路
const result = navmesh.findPath(1, 1, 18, 8);

核心概念

核心接口

interface IPoint {
    readonly x: number;
    readonly y: number;
}

interface IPathResult {
    readonly found: boolean;       // 是否找到路径
    readonly path: readonly IPoint[]; // 路径点列表
    readonly cost: number;         // 路径总代价
    readonly nodesSearched: number; // 搜索的节点数
}

interface IPathfindingOptions {
    maxNodes?: number;        // 最大搜索节点数（默认 10000）
    heuristicWeight?: number; // 启发式权重（>1 更快但可能非最优）
    allowDiagonal?: boolean;  // 是否允许对角移动（默认 true）
    avoidCorners?: boolean;   // 是否避免穿角（默认 true）
}

启发式函数

函数	适用场景	说明
manhattanDistance	4方向移动	曼哈顿距离
euclideanDistance	任意方向	欧几里得距离
chebyshevDistance	8方向移动	切比雪夫距离
octileDistance	8方向移动	八角距离（默认）

网格 vs 导航网格

特性	GridMap	NavMesh
适用场景	规则瓦片地图	复杂多边形地形
内存占用	较高 (width × height)	较低 (多边形数)
精度	网格对齐	连续坐标
动态修改	容易	需要重建

文档导航

• 网格地图 API - 网格操作和 A* 寻路
• 导航网格 API - NavMesh 构建和查询
• 路径平滑 - 视线简化和曲线平滑
• 实际示例 - 游戏移动、动态障碍物、分层寻路