拖入地图背景
修改蜂窝格子大小 生成静态地图数据
添加障碍
点击 添加障碍 后 按住 alt键盘 加 鼠标拖拽 快速建立障碍地形或者墙体
选择终点和起点
空格键 + 鼠标 拖拽地图
查看寻路细节
优化路径点数 寻路返回的实际路点列表 仅拐角部分
模拟寻路
修改寻路 k 值权重
>当k=0时，f(n)= h(n) ，最佳优先算法；以距离目标最近为导向
当k=1时，f(n)= g(n) ，迪杰斯特拉算法；以距离自己最近为导向
当k=0.5时，f(n)=g(n)+h(n) ，A星算法; 以距离自己最近 + 距离目标最近 为导向
无障碍物时，最佳优先算法的步骤和结果路径都是最优的
有障碍物时，采用A*算法
下载并保存地图json数据
{
"timestamp": 1661536249564,
"mapWidth": 2048,
"mapHeight": 2048,
"outerRadius": 30,
"k": 0.5,
"roadDataArr":[...]
}
json地图数据
timestamp 生成的时间戳
mapWidth&mapHeight 地图大小
outerRadius 格子外径
k 寻路优先权重值
roadDataArr 地图格子节点静态数据
下载a*寻路核心库
使用A*库
import Coord = astar.Coord;
import HoneycombSeeker = astar.HoneycombSeeker;
import MapData = astar.MapData;
import RoadNode = astar.RoadNode;
//mapData就是下载的地图json反序列化后的object对象
//JSON.parse(mapJsonTextContent);
//至于 mapJsonTextContent 是你加载 map_data.json的文本内容
// 你可以使用 cc.load 来加载
// 也可以使用 Laya.loader 来加载
// 当然你如果是纯html 也可以用 fetch
let seeker = new HoneycombSeeker(mapData);
let startNode = seeker.GetRoadNodeByPosition(startPoint[0], startPoint[1]);
let targetNode = seeker.GetRoadNodeByPosition(targetPoint[0], targetPoint[1]);
if (!targetNode || !startNode) {
alert(`开始节点和结束节点位置不对\nstartPoint:${startPoint[0]},${startPoint[1]}\ntargetPoint:${targetPoint[0]},${targetPoint[1]}\nmapData:${mapData.roadDataArr[0].length},${mapData.roadDataArr.length}`);
return;
}
let paths = seeker.SeekPath(startNode, targetNode);
你需要根据情况 对最后一个至多个节点位置进行优化
即: 寻路路径 p0->p1->p2->p3->p4->p5
当移动到p4时 他的下一个目标位置应该时 mouseMapPos位置 鼠标对应的地图位置
关于大地图的处理
你可以在编辑器中将整张大地图用来处理生成碰撞地形格子数据 然后使用切图工具 将图片切成大小相同的底图
在游戏内实时去计算玩家的位置和屏幕的视角范围 去实时添加和移除地图块 来优化大地图的性能开销
另外单张地图的格子数量上限时 4096 x 4096 理论上已经够用了
当你超过4096的需求时 会自动帮你计算成 4096需要的蜂窝格子大小
==如果你有其它特殊需求 可以csdn留言或者联系我的邮箱 我会及时处理==
关于寻路的性能问题
该寻路算法采用的 高低位 存储x,y 使用map的方式去查找访问 高效轻量
get key(): number {
//这个值可以根据实际情况来调整
//12位的最大存储值是4096 x,y不能超过4096
//你可以上调但要保证不能溢出 也可以根据实际情况 下调
return this.x << 12 | this.y;
}
/**
* 可以通过key来反推出x,y坐标值
* 静态方法
* @param key
* @returns
*/
public static key2Coord(key: number) {
return new Coord(key >> 12 & 0xfff, key & 0xfff);
}
同时在回溯路径的过程中 对路径点数计算优化
实际寻路路点数量 = 拐角数 + 2 ( 起点 和 终点)
已对数组和对象进行高度复用 同时也需要约束开发者
返回的节点仅供读取访问数据 不可赋值
是否支持es5？
支持
打包库的目标版本就是 es5 且向上兼容
尚未优化的点
- 当寻路被打断 第二次寻路的目标位置 与 第一次寻路的目标位置 距离较近时 可以选择从尾部查找 一次排序找到 距离下次位置较近的点 （ 可以设置一个阈值 低于这个阈值的时候 从当前点开始寻路 到 新的目标点 ) 这样之前的路点就不需要重新计算
- 寻路终点优化 对寻路节点附加偏移值 路点真实位置 = 路点中心位置 + 路点偏移
默认 路点偏移 x,y,z都是0 终点前的几个位置 通过鼠标对应地图的位置
做对应的插 值计算偏移
