A 星算法.docx
- 文档编号:18088106
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:14
- 大小:17.81KB
A 星算法.docx
《A 星算法.docx》由会员分享,可在线阅读,更多相关《A 星算法.docx(14页珍藏版)》请在冰点文库上搜索。
A星算法
传统A*算法有一个估价函数intjudge(intx,inty)
//估价函数,估价x,y到目的地的距离,估计值必须保证比实际值小
本程序算法假设估价函数估价值总为0,因而抛弃了函数intjudge(intx,inty)
只是简单的控制寻路方向优先向目的地靠近。
简单测试速度较快,但目前不能保证寻路的路径一定是最短的,也没有经过复杂路况测试保证能寻路成功(应该没问题^_^)
//find_path.h:
interfaceforthefind_pathclass.
//
//////////////////////////////////////////////////////////////////////
#if!
defined(AFX_FIND_PATH_H__6D68E153_6763_4EA4_81B7_8256024B5E23__INCLUDED_)
#defineAFX_FIND_PATH_H__6D68E153_6763_4EA4_81B7_8256024B5E23__INCLUDED_
#if_MSC_VER>1000
#pragmaonce
#endif//_MSC_VER>1000
#include
#include
//--寻路算法(最短路径?
?
?
)
//--从A*算法演变来的
//--就叫AB算法好了
typedefclassfind_pathfind_pathAB;
classfind_path
{
//--判断某点能否到达的函数指针定义
typedefbool(*pf_go_test)(int,int);
//--函数指针
pf_go_test _pf_go_test;
voidset_pf(pf_go_testpf){if(pf)_pf_go_test=pf;};
//--判断某点能否到达
//--需要用户提供该函数
inlineboolgo_test(intx,inty)
{
if(x<0||y<0
||x>=w||y>=h)returnfalse;
//--
if(_pf_go_test)return_pf_go_test(x,y);
//--默认都能到达
returntrue;
}
public:
voidinit(intwidth,intheight,pf_go_testpf=NULL);
voidreset();
//--返回找到的最短路径步数
//--并将找到的最短路径存储在path_p
intgo(intx0,inty0,intx1,inty1,pf_go_testpf=NULL);
public:
struct path_z{intx,y;};
int path_t; //--找到的最短路径步数
path_z*path_p; //--找到的最短路径
private:
enum
{
OPEN =0x01,
CLOSE =0x02,
OPEN_CLOSE = OPEN|CLOSE,
}__CONST;
structpath_node;
typedefstructpath_nodeT;
structpath_node
{
short x,y; //--节点坐标
short flag; //--Open/Close标志
T* parent;
T* next;
};
T*node_map; //--对应地图中每个节点
T*node_close; //--保存处理过的节点(node_map)
T*node_open; //--保存待处理的节点(node_map)
T*node_next; //--node_open链的最后一个
intw; //--地图的宽度
inth; //--地图的高度
intpath_max; //--w*h
public:
//--将节点加入OPEN表
//--先进先出(不排序)
inlinevoidAddToOpenQueue(T*node)
{
node->flag=OPEN; //记录Open标志
if(NULL==node_open)
{
node_open=node;
//node_next=node;
}
else
{
node_next->next=node;
//node_next=node;
}
node_next=node;
}
//--从OPEN表取节点并将节点加入CLOSE表
//--(取节点时负责处理周边节点)
inlineT*GetFromOpenQueue()
{
if(NULL==node_open
// ||node_open->flag&CLOSE //--不可能已经在Close中
)returnNULL;
T*it=node_open;
//--从OPEN表移走
//it->flag=0;
node_open=node_open->next;
//--加入CLOSE表
it->next=node_close;
it->flag=CLOSE;
node_close=it;
returnnode_close;
}
//--尝试下一步移动到x,y可行否
inlinevoidTryTile(intx,inty,T*parent)
{
T*it=node_map+w*y+x;
if(
//&&
//--速度比较快
0==(it->flag&OPEN_CLOSE)//--不在OPEN/CLOSE表中
&&
true==go_test(x,y) //--该点可以到达
)
{
it->parent=parent;
AddToOpenQueue(it); //--将节点加入Open队列
}
}
public:
find_path();
//virtual
~find_path();
};
#endif//!
defined(AFX_FIND_PATH_H__6D68E153_6763_4EA4_81B7_8256024B5E23__INCLUDED_)
//find_path.cpp:
implementationofthefind_pathclass.
//
//////////////////////////////////////////////////////////////////////
#include"stdafx.h"
#include"find_path.h"
//////////////////////////////////////////////////////////////////////
//Construction/Destruction
//////////////////////////////////////////////////////////////////////
find_path:
:
find_path()
{
_pf_go_test=NULL;
node_close=NULL;
node_open=NULL;
node_next=NULL;
path_p=NULL;
node_map=NULL;
}
find_path:
:
~find_path()
{
node_close=NULL;
node_open=NULL;
node_next=NULL;
if(NULL!
=path_p)
{
delete[]path_p;
path_p=NULL;
}
if(NULL!
=node_map)
{
delete[]node_map;
node_map=NULL;
}
}
voidfind_path:
:
reset()
{
path_t=0;
memset(path_p,0,path_max*sizeof(path_z));
memset(node_map,0,path_max*sizeof(path_node));
for(intj=0;j { for(inti=0;i { T*p=node_map+w*j+i; p->x=i; p->y=j; } } } voidfind_path: : init(intwidth,intheight,pf_go_testpf) { set_pf(pf); w=width; h=height; path_max=w*h; path_p=newpath_z[path_max]; node_map=newpath_node[path_max]; //reset(); } //--返回找到的最短路径步数 //--返回-1表示无法到达目的地 //--并将找到的最短路径存储在path_p intfind_path: : go(intx0,inty0,intx1,inty1,pf_go_testpf) { reset(); set_pf(pf); //reset(); node_open=(T*)(node_map)+w*y0+x0; T*root; //root=node_open; intxx,yy;//--决定x轴或y轴各自的优先寻路方向 intdx,dy;//--决定x轴与y轴的优先寻路方向 boolfind=false; while(NULL! =node_open) { root=GetFromOpenQueue(); if(NULL==root)break; T&t=*root; if(x1==t.x&&y1==t.y) { find=true; break;//达到目的地成功返回 } //--决定优先寻路方向 if(x1>t.x) { xx=1; dx=x1-t.x; } else { xx=0; dx=t.x-x1; } //-- if(y1>t.y) { yy=1; dy=y1-t.y; } else { yy=0; dy=t.y-y1; } //--后面的优先 //--y方向优先 if(0==dx ||(0! =dy&&dx>dy)) { //--x方向+优先 if(1==xx) { TryTile(t.x-1,t.y,root); TryTile(t.x+1,t.y,root); } //--x方向-优先 else { TryTile(t.x+1,t.y,root); TryTile(t.x-1,t.y,root); } //--y方向+优先 if(1==yy) { TryTile(t.x,t.y-1,root); TryTile(t.x,t.y+1,root); } //--y方向-优先 else { TryTile(t.x,t.y+1,root); TryTile(t.x,t.y-1,root); } } //--x方向优先 else { //--y方向+优先 if(1==yy) { TryTile(t.x,t.y-1,root); TryTile(t.x,t.y+1,root); } //--y方向-优先 else { TryTile(t.x,t.y+1,root); TryTile(t.x,t.y-1,root); } //--x方向+优先 if(1==xx) { TryTile(t.x-1,t.y,root); TryTile(t.x+1,t.y,root); } //--x方向-优先 else { TryTile(t.x+1,t.y,root); TryTile(t.x-1,t.y,root); } } }; if(false==find) { //--无法到达目的地 path_t=-1; returnpath_t; } //--回溯树 //--将求出的最佳路径(逆向)保存在path_p for(path_t=0;root;path_t++) { path_p[path_t].x=root->x; path_p[path_t].y=root->y; root=root->parent; } if(path_t>0) { path_t--; //--路径反转 intt=path_t/2; for(inti=0;i { path_zz=path_p[i]; path_p[i]=path_p[path_t-i]; path_p[path_t-i]=z; } } returnpath_t; } //myfindgo.cpp: Definestheentrypointfortheconsoleapplication. // #include"stdafx.h" #include #include"find_path.h" #include"windows.h" #include"mmsystem.h" #pragmacomment(lib,"winmm.lib") classtest_map { #define MAP_W_MAX 1000 #define MAP_H_MAX 1000 public: test_map() { memset(map,0,sizeof(map)); } staticboolgo_test(intx,inty) { if(x<0||y<0 ||x>=MAP_W_MAX ||y>=MAP_H_MAX )returnfalse; if(0! =map[x][y])returnfalse; returntrue; }; staticboolmap[MAP_W_MAX][MAP_H_MAX]; }; booltest_map: : map[MAP_W_MAX][MAP_H_MAX]; intx0=2; inty0=2; intx1=1; inty1=1; voidreadmap() { FILE*f; f=fopen("c: \\tmp\\map.txt","r"); if(NULL==f)return; intx=0; inty=0; fscanf(f,"%d,%d\n",&x,&y); for(intj=0;j { charline[1024]={0}; fgets(line,x+1,f); for(inti=0;i { if(''! =line[i])test_map: : map[i][j]=1; if('s'==line[i]) { x0=i; y0=j; test_map: : map[i][j]=0; } if('e'==line[i]) { x1=i; y1=j; test_map: : map[i][j]=0; } } } fclose(f); } intmain(intargc,char*argv[]) { test_mapmap; //--初始化地图 //--不可到达的点 //map.map[0][0]=1; map.map[2][1]=1; map.map[3][1]=1; map.map[1][2]=1; map.map[3][2]=1; map.map[0][2]=1; readmap(); find_pathABfp; fp.init(100,25,test_map: : go_test); intz; DWORDt1=timeGetTime(); //--寻路 { for(inti=0;i<1000;i++) z=fp.go(x0,y0,x1,y1); } DWORDt2=timeGetTime(); DWORDt=t2-t1; //--打印路径 for(inti=0;i<=fp.path_t;i++) { printf("x=%dy=%d\r\n" ,fp.path_p[i].x ,fp.path_p[i].y); } printf("path_t=%dtime_t=%d(ms)\r\n",fp.path_t,t); getch(); return0; } 使用到的文件c: \\tmp\\map.txt内容如下 80,24 ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo o o o o o s oooooooooooooo o o o o ooooooooooo o o o o ooooooo oooooooooooooo oooooooo o o oooooo o oooo o o o o o o ooo ooo o o oooo oooo o o oooooooooooooooooooooooooooooooooooooooooooooo o o o o o o oooooooooooooooooooooooooooooooooooooooooooo o o o ooooooooooo o o ooooooo oooooooo o o o o o o o o ooooooooooo oooooooooo o o o o oe ooo o o o o ooooo
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 星算法 算法