Cocos Creator A* 分帧寻路 二叉堆
这是一个TypeScript实现的高效寻路算法, 开放列表使用二叉堆结构, 并支持异步分帧计算.
功能介绍
- 使用二叉堆实现开放列表, 解决开放列表频繁更新排序的问题.
- 使用异步分帧计算的方式, 解决寻路帧大量集中占用CPU的问题.
- 使用对象池, 解决大量节点对象频繁创建销毁引起的内存波动问题.
- 支持 Creator 2.4.x | 3.6.x | 3.7.x
性能测试(同一帧)
- 地图大小 20 * 30 | 障碍比例 10%
- 500 次寻路: 耗时 13ms.
- 1000 次寻路: 耗时 23ms.
- 地图大小 20 * 30 | 障碍比例 20%
- 500 次寻路: 耗时 13ms.
- 1000 次寻路: 耗时 23ms.
- 地图大小 30 * 40 | 障碍比例 10%
- 500 次寻路: 耗时 20ms.
- 1000 次寻路: 耗时 35ms.
如何使用它
1. 构建数据和对象
const graph = new Graph([
[1,1,1,1],
[0,1,1,0],
[0,0,1,1]
]);
// 当前帧检查开放列表中的所有节点
const astar = new AsyncAStar(graph);
// 每帧检查开放列表中的100个节点
// new AsyncAStar(graph, { open_step: 100 });
2. 在 component 脚本中挂载 update 方法
Component::update (deltaTime: number) {
astar.update();
}
3. 使用格子坐标查找路径
const start = astar.graph.grids[0][0];
const end = astar.graph.grids[1][2];
astar.search(start, end, function(frames, list) {
// frames: 消耗的帧数
// list: 一个倒序的路径节点数组
});
4. 对角线
const graph_diagonal = new Graph([
[1,1,1,1],
[0,1,1,0],
[0,0,1,1]
], { diagonal: true });
5. 权重
const graph_with_weight = new Graph([
[1,1,2,30],
[0,4,1.3,0],
[0,0,5,1]
]);
关于权重值的说明:
- 0 表示是墙
- 1 表示开放
- 权重值 > 1
启发算法
- Heuristic 启发算法与特定场景绑定, 所以请大家根据实际情况自行研究, 默认使用 manhattan.
const manhattan = function(start_node: GridNode, end_node: GridNode) {
const d1 = Math.abs(end_node.x - start_node.x);
const d2 = Math.abs(end_node.y - start_node.y);
return d1 + d2;
};
new AsyncAStar(graph, { heuristic: manhattan });
