canvas——路径搜索

在前一篇博客中随机生成迷宫,现在就以随机生成的迷宫为地图,开始寻找路径。

迷宫寻路也可以使用DFS,BFS,但常见的是A*算法,它是启发式搜索算法的一种,效率相比前两者也更高。接下来以A*算法为例,迷宫是一个连通图,因此可以寻找到地图上可通行的任意两点间的路径。

A*算法

A*算法的目的是求出最低通过成本,利用它来寻找最优路径。

A*算法的核心在于它的估值函数:f(n)=g(n)+h(n);

  f(n)表示第n点的估值;

  g(n)表示起始点到顶点n的代价,这里代表起始点到顶点n距离;

  h(n)表示顶点n到终点的代价,这里代表顶点n到终点的距离。

对于h(n)采用曼哈顿距离计算。

|r1-r2| + |y1 - y2|

当然也可以使用其他的评估函数,如欧几里得距离、切比雪夫距离;

实现

每个顶点除了保存自身的坐标位置r、c和通行状态flag外,还需要保存各自的f、g、h值(初始化均为0,通过A*算法计算得出),parent指向经过顶点n的前一顶点,state表示顶点n的状态。

class Point {
    constructor(r, c, flag=1) {
        this.r = r;
        this.c = c;
        this.flag = flag;         // 0 可以通过 1不能通过
        this.state = -1;        // 0 在openList 1 在closeList -1 未处理

        this.f = 0;
        this.g = 0;
        this.h = 0;
        this.parent = null;
    }
}

需要两个数组,openList保存已计算 f 值得顶点,closeList保存最有路径的顶点。

(1)初始状态下,openList包含起点,closeList为空。

(2)从openList中取出第一个顶点curPoint,放入closeList中,将curPoint的state设置为1,表示该顶点在closeList数组中

(3)遍历curPoint上下左右的顶点tp,对tp做处理:

  tp没有超出边界,flag==0,且state!=1(不在closeList)的,判断tp是否为终点;

  是则将tp的parent指向curPoint,返回true,结束函数执行;

  如果不是,计算或更新tp的估值等。

(4)从openList中选择估值最小的顶点,循环步骤3。

/*
* start 起点
* end 终点
* distPoint() 计算两点间曼哈顿距离
* processPoint() 处理四周顶点
*/
findPath(start, end) { let curPoint
= start;
// 上下左右顶点偏移量 let near
= [{ r: -1, c: 0 }, { r: 1, c: 0 }, { r: 0, c: -1 }, { r: 0, c: 1 }]; let finded = false; start.f = start.h = this.distPoint(start, end); this.openList.push(start); while(this.openList.length > 0) { curPoint = this.openList.pop(); curPoint.state = 1; this.closeList.push(curPoint); finded = this.processPoint(near, curPoint, end); if(finded) { break; } } }
/*
* near 需要遍历的顶点偏移量
* curPoint 当前顶点
* pathArr 包含路和墙的二位数组
* end 终点
* between() 计算数值是否在所给范围内
* addArrSort() 添加顶点到指定数组并排序
* quickSort() 快速排序
* comPonitF() 指定排序方法 — — 比较 f 值
*/
processPoint(near, curPoint, end) { let len
= near.length, i = 0; while(i < len) { let tr = curPoint.r + near[i].r, tc = curPoint.c + near[i].c; if(this.between(tr, 0, this.r - 1) && this.between(tc, 0, this.c - 1)) { let tp = this.pathArr[tr][tc]; if(tp.flag === 0 && tp.state !== 1) {
// 判断 tp 是否为终点
if(this.isEqual(tp, end)) { tp.parent = curPoint; return true; }
// tp不在openList(估值未计算)
if(tp.state === -1) { tp.parent = curPoint; tp.g = curPoint.g + 1; tp.h = this.distPoint(tp, end); tp.f = tp.g + tp.h; this.addArrSort(this.openList, tp, this.comPonitF); }else { let g = curPoint + 1; if(g < tp.g) {
tp.parent =curPoint; tp.g
= g; tp.f = tp.g + tp.h; this.quickSort(this.openList, 0, this.openList.length, this.comPonitF); } } } } ++i; } return false; }

 最终,可以通过终点 parent 往回找到路径。

确定起点、终点

为了探寻任意两点间路径,这里为canvas添加了点击事件,以确定起点和终点,然后描绘出两点间的路线。

/*
* removeEvent() 移除点击事件
*/
addEvent(e) {
if(this.start && this.end) { this.removeEvent(); return; } let c = ~~(e.offsetX / 10), // 取整 r = ~~(e.offsetY / 10); if(this.pathArr[r][c].flag === 0) { if(!this.start) { this.start = this.pathArr[r][c]; this.renderPer(this.start, 'yellow'); }else { this.end = this.pathArr[r][c]; this.findPath(this.start, this.end); this.render(this.end); } } }

路径搜索就到这里啦。

效果

完整代码

赞 (0) 评论 分享 ()