EEA阔宝：专注 CocosCreator 引擎小游戏开发两年
开发微信小游戏5款
H5 小游戏多款
本篇承接上一集故事
看一个小怪物是如何自我进化的！
在上一篇文章中，小怪采用了包围盒子边界检测的方法实现了寻路，但是狡猾的玩家对此采取了措施，他偷偷的加固了防线！
这可难坏了小怪，哼！玩家一定是想消耗我的体力，让我像无头苍蝇般乱走，我才不上当呢！于是我拿出了 KUOKUO 大人赏的纸和笔，开始思考！
我需要两个列表（数组）：一个记录下所有被考虑来寻找最近的点集合 一个记录下不会再被考虑的点集合
// 一个点上应该具有的属性
let obj = new Object();
obj.x = ...
obj.y = ...
// g 随着离开始点越来越远而增大
obj.g = ...
// h 当前点到目标点的移动量估算值
obj.h = ...
obj.f = ...
obj.parent = ...根据 f 值寻路后可依靠 parent 回溯
// ......
this.final = [];
while(p) {
this.final.push(p);
p = p.parent;
}
// 翻转
this.final.reverse();
// 沿着 final 走
// ......
这样虽然多思考了几个路径上的点，但是我思考后可直接行走，马上去试试？
哼哼！亲爱的玩家，我来了！！！
二、顿悟在一天天不断的思考如何能够打玩家，打玩家前如何找到玩家，小怪物的智力在不断上升，突然间开悟了，可以用接近人类的语言描述问题了。
首先，对前一篇小怪系列文章作详细分析，帮助大家理解我（小怪物）。
曼哈顿估价法
可以理解为直线的一段或者几段距离的累加和，直线距离，看下图：
曼哈顿估价法：传入当前点与目标点，返回估值，
// 曼哈顿估价法,传入当前点与目标点,返回估值
// abs 为取绝对值
manHattan (nowPoint, pIndex) {
let dx = Math.abs(nowPoint.x - pIndex.x);
let dy = Math.abs(nowPoint.y - pIndex.y);
return dx + dy;
}（小怪物你太...，好不习惯，一本正经的样子！）
然后，我们分析一下路径上点的对象应该具有的信息，看下图：
// new 一个空对象
let obj = new Object();
// 每个网格的点的行和列 对应 x 和 y
obj.x = v.x;
obj.y = v.y;
// g 为从起点，沿着路径，移动到当前点的移动耗费。
obj.g = this.manHattan(v, this.mIndex);
// h 为从当前点到终点的移动耗费。
obj.h = this.manHattan(v, this.pIndex);
obj.f = obj.g + obj.h;
// 起点无上级，然后搜索到目标点后可以轻易的靠着 parent 回溯到起点。
obj.parent = parent;上面代码不包括障碍计算，单纯的是曼哈顿距离，也就是直线距离，因为我们不知道什么时候有障碍，这叫启发式。
我们的路径是通过反复遍历 open 列表并且选择具有最低 f 值装入 close 列表，因为 f 是综合值，调整 g 和 h 的比例会起到不同寻路效果。
A*的实现
在 start 中声明数据，并开始A*寻路。
start () {
// 小怪的坐标，起点
this.mIndex = cc.v2(4, 0);
// 玩家坐标点，终点
this.pIndex = cc.v2(3, 9);
// 开始
this.aStar();
}
关键点就是aStar函数，A*算法的实现：
aStar () {
// 限制次数 500；
// 首先将小怪的位置装入 close 列表
let time = 500;
let obj = new Object();
obj.x = this.mIndex.x;
obj.y = this.mIndex.y;
obj.g = this.manHattan(this.mIndex, this.mIndex);
obj.h = this.manHattan(this.mIndex, this.pIndex);
obj.f = obj.g + obj.h;
obj.parent = null;
// 将起点放入
this.pushInClose(obj);
// ......
},
pushInClose (obj) {
this.close.push(obj);
},限制 500 次很好理解，每一次循环 time-- 这样可以防止找不到路径造成卡死。然后让我们为起点建立对象，然后放入 close 列表中。
close 列表装的是那些已经搜索过的点，open 列表中放入待选择的点，然后在 open 列表中选择 f 值较低的点，放入 close 中，完成一轮搜索，直到我们找到终点。
我们从起点开始，寻找当前点的周围一圈，然后计算 g h 得到 f 值。
-
while (true) { time--; // 周围一圈装入 open this.aroundPos(temp); // 在 open 中找到 f 最小的，装入 close 并返回该点； temp = this.findMinInOpen(); if (temp.x == this.pIndex.x && temp.y == this.pIndex.y) { // 到达目的地 break; } if (time <= 0) { console.log('寻找不到'); break; } }
向四周寻找
aroundPos (parent) {
// 上下左右四个方向
let dir = [[0,1],[1,0],[0,-1],[-1,0]];
for (let i = 0; i < 4;i++) {
let mx = parent.x + dir[i][0];
let my = parent.y + dir[i][1];
// 是否出界
if (mx < 0 || mx > 6 || my < 0 || my > 9) {
continue;
}
// 是否为墙
if (this.map[mx][my] == 1) {
continue;
}
// 是否已经在 close 中了
if (this.isInClose(mx, my)) {
continue;
}
// 是否已经在 close 中了
if (this.isInOpen(mx, my)) {
continue;
}
// 装入 open
this.pushInOpen(cc.v2(mx, my), parent);
}
},
findMinInOpen () {
let min = 999;
let index = null;
// 找到 open 中最小的 f 的点的下标
for (let i = 0; i < this.open.length; i++) {
if (this.open[i].f <= min) {
min = this.open[i].f;
index = i;
}
}
// 运用 splice 将 f 最小的点切出来
let obj = this.open.splice(index, 1);
// 放入 close 列表并返回
this.pushInClose(obj[0]);
return obj[0];
},放入 close 列表方法是直接放入 close 数组，而 open 列表需要我们创建点的信息，因为是新的点。
-
pushInOpen (v, parent) { let obj = new Object(); obj.x = v.x; obj.y = v.y; obj.g = this.manHattan(v, this.mIndex); obj.h = this.manHattan(v, this.pIndex); obj.f = obj.g + obj.h; obj.parent = parent; this.open.push(obj); },
判断是否在 open close 两个列表里就是 for 循环
最后我们发现，在 close 列表里是很多发现的点，数组的最后一定是目标点。
isInOpen (mx, my) {
for (let i = 0; i < this.open.length; i++) {
if (this.open[i].x == mx && this.open[i].y == my) {
return true;
}
}
return false;
},
isInClose (mx, my) {
for (let i = 0; i < this.close.length; i++) {
if (this.close[i].x == mx && this.close[i].y == my) {
return true;
}
}
return false;
},在 close 数组的最后就是目标点，我们只要根据目标点，进行不断的向上访问 parent 就能回溯到起点。
代码实现：
// 根据 parent 最终确认路线
let l = this.close.length - 1;
let p = this.close[l];
this.final = [];
while(p) {
this.final.push(p);
p = p.parent;
}
// 将 close 中的正确路线装入 final 后其实是反序的
// 翻转
this.final.reverse();
// 沿着 final 走
this.go(0);
沿着路径走就很简单了，利用 runAction不断的走，直到走完。
-
go (i) { this.me.runAction(cc.sequence( cc.moveTo(0.5,this.convertToPoints(this.final[i].x, this.final[i].y)), cc.callFunc(() => { if (i == this.final.length - 1) return; i++; this.go(i); },this) )); },
行列坐标与实际坐标转化
// 转化坐标
convertToPoints (dx, dy) {
let y = 300 - 100 * dx;
let x = 100 * dy - 450;
return cc.v2(x, y);
},
进入公众号后台回复：【小怪物A*寻路】获取源码
进击的小怪物【第一季】到此告一段落感谢 「EEA阔宝」有趣的教程，让学习也变如此乐趣！「奎特尔星球」欢迎大家投稿，有意的朋友可以加我微信，愿我们一起共同成长！
