最简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/

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

发布者

依十七

风逝难依,陌归十七。

发表评论

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