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

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

开发微信小游戏5款

H5 小游戏多款

CSDN 博客:KUOKUO 众享

本篇承接上一集故事

《KUOKUO的趣味教程 | 小怪物的新思考(3)

KUOKUO的趣味教程 | 小怪物的视野(2)

KUOKUO的趣味教程 | 进击的小怪诞生(1)

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


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

这可难坏了小怪,哼!玩家一定是想消耗我的体力,让我像无头苍蝇般乱走,我才不上当呢!于是我拿出了 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 循环

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 列表里是很多发现的点,数组的最后一定是目标点。

在 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);
},

本文分享自微信公众号 - Creator星球游戏开发社区(creator-star)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券