KUOKUO的趣味教程 | 小怪物的奇迹顿悟(4)

EEA阔宝：专注 CocosCreator 引擎小游戏开发两年

开发微信小游戏5款

 H5 小游戏多款

CSDN 博客：KUOKUO 众享

本篇承接上一集故事

看一个小怪物是如何自我进化的！

---

在上一篇文章中，小怪采用了包围盒子边界检测的方法实现了寻路，但是狡猾的玩家对此采取了措施，他偷偷的加固了防线！

这可难坏了小怪，哼！玩家一定是想消耗我的体力，让我像无头苍蝇般乱走，我才不上当呢！于是我拿出了 KUOKUO 大人赏的纸和笔，开始思考！

我需要两个列表（数组）：一个记录下所有被考虑来寻找最近的点集合 一个记录下不会再被考虑的点集合

1. // 一个点上应该具有的属性

2. let obj = new Object();

3. obj.x = ...

4. obj.y = ...

5. // g 随着离开始点越来越远而增大

6. obj.g = ...

7. // h 当前点到目标点的移动量估算值

8. obj.h = ...

9. obj.f = ...

10. obj.parent = ...

根据 f 值寻路后可依靠 parent 回溯

1. // ......

2. this.final = [];

3. while(p) {

4. this.final.push(p);

5. p = p.parent;

6. }

7. // 翻转

8. this.final.reverse();

9. // 沿着 final 走

10. // ......

这样虽然多思考了几个路径上的点，但是我思考后可直接行走，马上去试试？

哼哼！亲爱的玩家，我来了！！！

二、顿悟

在一天天不断的思考如何能够打玩家，打玩家前如何找到玩家，小怪物的智力在不断上升，突然间开悟了，可以用接近人类的语言描述问题了。

首先，对前一篇小怪系列文章作详细分析，帮助大家理解我（小怪物）。

曼哈顿估价法

可以理解为直线的一段或者几段距离的累加和，直线距离，看下图：

曼哈顿估价法：传入当前点与目标点，返回估值，

1. // 曼哈顿估价法,传入当前点与目标点,返回估值

2. // abs 为取绝对值

3. manHattan (nowPoint, pIndex) {

4. let dx = Math.abs(nowPoint.x - pIndex.x);

5. let dy = Math.abs(nowPoint.y - pIndex.y);

6. return dx + dy;

7. }

（小怪物你太...，好不习惯，一本正经的样子！）

然后，我们分析一下路径上点的对象应该具有的信息，看下图：

1. // new 一个空对象

2. let obj = new Object();

3. // 每个网格的点的行和列 对应 x 和 y

4. obj.x = v.x;

5. obj.y = v.y;

6. // g 为从起点，沿着路径，移动到当前点的移动耗费。

7. obj.g = this.manHattan(v, this.mIndex);

8. // h 为从当前点到终点的移动耗费。

9. obj.h = this.manHattan(v, this.pIndex);

10. obj.f = obj.g + obj.h;

11. // 起点无上级，然后搜索到目标点后可以轻易的靠着 parent 回溯到起点。

12. obj.parent = parent;

上面代码不包括障碍计算，单纯的是曼哈顿距离，也就是直线距离，因为我们不知道什么时候有障碍，这叫启发式。

我们的路径是通过反复遍历 open 列表并且选择具有最低 f 值装入 close 列表，因为 f 是综合值，调整 g 和 h 的比例会起到不同寻路效果。

A*的实现

在 start 中声明数据，并开始A*寻路。

1. start () {

2. // 小怪的坐标，起点

3. this.mIndex = cc.v2(4, 0);

4. // 玩家坐标点，终点

5. this.pIndex = cc.v2(3, 9);

6. // 开始

7. this.aStar();

8. }

关键点就是aStar函数，A*算法的实现：

1. aStar () {

2. // 限制次数 500；

3. // 首先将小怪的位置装入 close 列表

4. let time = 500;

5. let obj = new Object();

6. obj.x = this.mIndex.x;

7. obj.y = this.mIndex.y;

8. obj.g = this.manHattan(this.mIndex, this.mIndex);

9. obj.h = this.manHattan(this.mIndex, this.pIndex);

10. obj.f = obj.g + obj.h;

11. obj.parent = null;

12. // 将起点放入

13. this.pushInClose(obj);

14. // ......

15. },

16. pushInClose (obj) {

17. this.close.push(obj);

18. },

限制 500 次很好理解，每一次循环 time-- 这样可以防止找不到路径造成卡死。然后让我们为起点建立对象，然后放入 close 列表中。

close 列表装的是那些已经搜索过的点，open 列表中放入待选择的点，然后在 open 列表中选择 f 值较低的点，放入 close 中，完成一轮搜索，直到我们找到终点。

我们从起点开始，寻找当前点的周围一圈，然后计算 g h 得到 f 值。

1. while (true) {

2. time--;

3. // 周围一圈装入 open

4. this.aroundPos(temp);

5. // 在 open 中找到 f 最小的，装入 close 并返回该点；

6. temp = this.findMinInOpen();

7. if (temp.x == this.pIndex.x && temp.y == this.pIndex.y) {

8. // 到达目的地

9. break;

10. }

11. if (time <= 0) {

12. console.log('寻找不到');

13. break;

14. }

15. }

向四周寻找

1. aroundPos (parent) {

2. // 上下左右四个方向

3. let dir = [[0,1],[1,0],[0,-1],[-1,0]];

4. for (let i = 0; i < 4;i++) {

5. let mx = parent.x + dir[i][0];

6. let my = parent.y + dir[i][1];

7. // 是否出界

8. if (mx < 0 || mx > 6 || my < 0 || my > 9) {

9. continue;

10. }

11. // 是否为墙

12. if (this.map[mx][my] == 1) {

13. continue;

14. }

15. // 是否已经在 close 中了

16. if (this.isInClose(mx, my)) {

17. continue;

18. }

19. // 是否已经在 close 中了

20. if (this.isInOpen(mx, my)) {

21. continue;

22. }

23. // 装入 open

24. this.pushInOpen(cc.v2(mx, my), parent);

25. }

26. },

27. findMinInOpen () {

28. let min = 999;

29. let index = null;

30. // 找到 open 中最小的 f 的点的下标

31. for (let i = 0; i < this.open.length; i++) {

32. if (this.open[i].f <= min) {

33. min = this.open[i].f;

34. index = i;

35. }

36. }

37. // 运用 splice 将 f 最小的点切出来

38. let obj = this.open.splice(index, 1);

39. // 放入 close 列表并返回

40. this.pushInClose(obj[0]);

41. return obj[0];

42. },

放入 close 列表方法是直接放入 close 数组，而 open 列表需要我们创建点的信息，因为是新的点。

1. pushInOpen (v, parent) {

2. let obj = new Object();

3. obj.x = v.x;

4. obj.y = v.y;

5. obj.g = this.manHattan(v, this.mIndex);

6. obj.h = this.manHattan(v, this.pIndex);

7. obj.f = obj.g + obj.h;

8. obj.parent = parent;

9. this.open.push(obj);

10. },

判断是否在 open close 两个列表里就是 for 循环

1. isInOpen (mx, my) {

2. for (let i = 0; i < this.open.length; i++) {

3. if (this.open[i].x == mx && this.open[i].y == my) {

4. return true;

5. }

6. }

7. return false;

8. },

9. isInClose (mx, my) {

10. for (let i = 0; i < this.close.length; i++) {

11. if (this.close[i].x == mx && this.close[i].y == my) {

12. return true;

13. }

14. }

15. return false;

16. },

最后我们发现，在 close 列表里是很多发现的点，数组的最后一定是目标点。

在 close 数组的最后就是目标点，我们只要根据目标点，进行不断的向上访问 parent 就能回溯到起点。

代码实现：

1. // 根据 parent 最终确认路线

2. let l = this.close.length - 1;

3. let p = this.close[l];

4. this.final = [];

5. while(p) {

6. this.final.push(p);

7. p = p.parent;

8. }

9. // 将 close 中的正确路线装入 final 后其实是反序的

10. // 翻转

11. this.final.reverse();

12. // 沿着 final 走

13. this.go(0);

沿着路径走就很简单了，利用 runAction不断的走，直到走完。

1. go (i) {

2. this.me.runAction(cc.sequence(

3. cc.moveTo(0.5,this.convertToPoints(this.final[i].x, this.final[i].y)),

4. cc.callFunc(() => {

5. if (i == this.final.length - 1) return;

6. i++;

7. this.go(i);

8. },this)

9. ));

10. },

行列坐标与实际坐标转化

1. // 转化坐标

2. convertToPoints (dx, dy) {

3. let y = 300 - 100 * dx;

4. let x = 100 * dy - 450;

5. return cc.v2(x, y);

6. },

进入公众号后台回复：【小怪物A*寻路】获取源码

进击的小怪物【第一季】到此告一段落感谢 「EEA阔宝」有趣的教程，让学习也变如此乐趣！「奎特尔星球」欢迎大家投稿，有意的朋友可以加我微信，愿我们一起共同成长！