最简A星思想寻路算法

A星寻路大名鼎鼎,大多数人提到寻路都会想到他,然后去研究,然后理论懂了,代码也看懂了,但是能不能独自写出来适合自己的,并且修改优化,答案是不能,我虽然已经用了好久的这个算法,但是天下代码抄抄抄,使用的别人的代码,能简单修改,然而最终自己并不是特别理解,所以自己无事写了一个最简单的实现寻路的一段代码,不管所有优化之类东西,直接弄最基本的一些东西。

在此再整理一下A星思路,设定起点和终点,查看起点附近的可移动点,放入开放列表,然后找到一个最近的,放入闭合列表,从开放列表移除,然后从下一个点继续寻找,如此循环,为避免回头路走过的点是不能回头再走的,寻到终点之后我们的闭合列表会得到带着冤枉路的一段路径,然后反向寻路,这次是从你上次的到的路径里边回寻,如此便能得到一个基本唯一的一条通路。

原理明白了之后就可以写了,首先用0,1绘制一张二维地图。

var temarr:any[] = [];
for(var i=0;i<20;i++){
    var temarr1:any[] = [];
    for(var j=0;j<20;j++){
        var t=0;
        (Math.random()<0.4)?t=0:t=1;
        temarr1.push(t);
    }
    temarr.push(temarr1);
}

然后取随机点sp,ep为起始点和终点

//获取单条路径
public getOC(sp,ep,tarr,bol = false):any[]{
    var tp = sp;
    var openarr:any[] = [];
    var closearr:any[] = [];
    //tt为防止死循环变量
    var tt = 0;
    //遍历
    while(this.getDistance(tp,ep)>1&&tt<100){
        //获取附近可取点
        var adjarr:any[] = this.getAdjacent(tp,tarr,bol);
        // console.log(adjarr);
        for(var tem in adjarr){
            //如果不再任何列表中插入open表
            if(!this.isHave(adjarr[tem],closearr)&&!this.isHave(adjarr[tem],openarr)){
                openarr.push(adjarr[tem]);
            }
        }
        //选取一个点插入闭合列表,从开放列表移除
        var cp = this.getPointDistance(ep,openarr);
        closearr.push(cp[1]);
        openarr.splice(openarr.indexOf(cp[1]),1);
        //重置新的起点
        tp = cp[1];
        tt++;
    }
    return closearr;
}

其中有几个函数一个为取得附近可取点,一个是选取其中一个可选择点,还有判断是否在列表中。都简单

private isHave(arr1,arr2):boolean{
    var bo:boolean = false;
    for(var i=0;i<arr2[0].length;i++){
        for(var j=0;j<arr2.length;j++){
            if(arr1[0]==i&&arr1[1]==j){
                bo = true;
            }
        }
    }
    return bo;
}

//获取最近
public getPointDistance(p,arr):any{
    var tp:any[]=[];
    var tl:number=9999;
    var ts:string="";
    for(var tem in arr){
        var jl = this.getDistance(p,arr[tem]);
        if(tl > jl){
            ts = tem;
            tp = arr[tem];
            tl = jl;
        }
    }
    return [ts,tp];
}
//获取格子距离  这里用最简单的横竖距离
public getDistance(p1,p2):number{
    var t1 = Math.abs(p1[0] - p2[0]);
    var t2 = Math.abs(p1[1] - p2[1]);
    var distance = t1+t2;
    return distance;
}
//获取相邻的格子
public getAdjacent(arr,toarr,bol = false):any[]{
    var adjarr:any[] = [];

        if(this.isHave1([arr[0]+1,arr[1]],toarr)&&toarr[arr[0]+1][arr[1]]==0)
            adjarr.push([arr[0]+1,arr[1]]);
        if(this.isHave1([arr[0]-1,arr[1]],toarr)&&toarr[arr[0]-1][arr[1]]==0)
            adjarr.push([arr[0]-1,arr[1]]);
        if(this.isHave1([arr[0],arr[1]+1],toarr)&&toarr[arr[0]][arr[1]+1]==0)
            adjarr.push([arr[0],arr[1]+1]);
        if(this.isHave1([arr[0],arr[1]-1],toarr)&&toarr[arr[0]][arr[1]-1]==0)
            adjarr.push([arr[0],arr[1]-1]);
   
    return adjarr;
}

getOc已经取得了一条路,然后反序再来一遍

//返回距离
public getPath(sp,ep):any[]{
    //获取正序寻路路径关闭列表
    var tclist:any = this.getOC(sp,ep,this.tarr);
    tclist = tclist.reverse();
    //反向获取第二次寻回路径转换起点与终点
    var clolist:any[] = this.getOC(ep,sp,tclist,true);
    return clolist;
}

至此简单寻路完成。自己取写一个吧!

本文作者:依十七  本文链接:http://www.is17.com/423/

本站文章若无特别说明,皆为原创,如需转载,请以超链接形式注明作者和原始出处及本声明

发布者

依十七

风逝难依,陌归十七。

发表评论

电子邮件地址不会被公开。 必填项已用*标注