A*寻路算法详解
2024-08-31 07:45:34
以我个人的理解：
A*寻路算法是一种启发式算法，算法的核心是三个变量f,g,h的计算。g表示 从起点 沿正在搜索的路径 到 当前点的距离，h表示从当前点到终点的距离，而f=g+h，所以f越小，则经过当前点的最终路径长度也就越小。
算法当中，有两个辅助列表用来搜索路径。
搜索域（开启列表）和已搜索域（关闭列表）。其中搜索域用来存放待搜索的节点，已搜索域存放已经搜过的节点。
这两个列表的用法：
1、初始化：首先把起点放进搜索域。
2、从搜索域取出f最小的节点，分别遍历上下左右，左上，右下，左下，右上8个方向，并计算他们的f,g,h值，放进搜索域。
3、把当前节点从搜索域中删除，把当前节点放进已搜索域。进入第2步，循环。直到搜索域为空，或者找到终点。
那么重点的就是这个过程怎么实现。
用下面的图来做演示：
图1
图1中，绿色表示起点，红色表示终点，紫色表示墙。
1、计算起点的g,h,f，放进搜索域。
2、从搜索域取出f值最小的节点，8个方向搜索。（下 图2中蓝色部分）
3、从搜索域中删除当前节点，把当前节点放入已搜索域中。到第2步循环。
图2
图3
图3中橙黄色部分表示在 已搜索域 中。蓝色表示在 搜索域 中。
图4
图5
图6
........此处省略若干图。
最终图
过程大概就是这个过程。下面看代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <list>
#include <cmath>
#include <windows.h>
using namespace std; typedef struct node
{
node() //构造函数 初始化数据
{
x=y=0;
f=h=g=0;
parent=NULL;
}
int x,y; //坐标 这里的x对应下面的i，y对应j
double f,h,g; //g表示从原点到当前节点路线的长度，h表示当前节点到目标节点的长度，f=g+h表示从原点到目标点经过当前节点的路线长度
struct node *parent; //父节点
} Node; //节点结构体（每个节点表示一个正方形小格子） const int MAX=100;
const int LEN=10; //把地图分割成一个一个的正方形小格子，每个格子的长度为LEN
const char ROAD='*'; //最后输出的时候，'*'表示路线 char mmap[MAX][MAX]; //注意：'0'表示起点，'1'表示终点 int si,sj,ei,ej; //si,sj分别记录起点的x,y坐标，ei,ej分别记录终点的x,y坐标
int n,m;
int dx[8]= {-1,1,0,0,-1,1,-1,1}; //8个方向 上下左右，左上，右下，右上，左下
int dy[8]= {0,0,-1,1,-1,1,1,-1}; list<Node*> startList,endList; //startList表示搜索域，endList存储已搜索过的节点 Node *start=NULL; //起点指针 //判断节点指针node 是否 在列表mlist中
bool in_List(Node * node,list<Node*> mlist)
{
for(list<Node*>::iterator it=mlist.begin();it!=mlist.end();it++)
{
if((*it)->x==node->x&&(*it)->y==node->y)
{
return true;
}
}
return false;
} //从列表中获取f最小的节点指针
Node* getMinNode(list<Node*> mlist)
{
double mmin=1000000;
Node *pmmin=NULL;
for(list<Node*>::iterator it=mlist.begin(); it!=mlist.end(); it++)
{
if((*it)->f<mmin)
{
mmin=(*it)->f;
pmmin=(*it);
}
}
return pmmin;
} //从列表中删除节点指针
void del(Node *node,list<Node*> &mlist)
{
for(list<Node*>::iterator it=mlist.begin(); it!=mlist.end(); it++)
{
if((*it)==node)
{
mlist.erase(it);
return;
}
}
}
//向列表中添加节点指针
void add(Node *node,list<Node*> &mlist)
{
mlist.push_back(node);
return;
} //计算(x1,y1)到(x2,y2)的距离
double getDis(int x1,int y1,int x2,int y2)
{
double xx1=x1*LEN+LEN/2.0;
double yy1=y1*LEN+LEN/2.0;
double xx2=x2*LEN+LEN/2.0;
double yy2=y2*LEN+LEN/2.0;
return sqrt((xx1-xx2)*(xx1-xx2)+(yy1-yy2)*(yy1-yy2));
} //回溯寻找路径
void setRoad(Node *root)
{
while(root->parent!=NULL)
{
if(root->x==ei&&root->y==ej)
mmap[root->x][root->y]='1';
else
mmap[root->x][root->y]=ROAD;
root=root->parent;
}
} void work()
{
start=new Node;
start->parent=NULL;
start->f=0;
start->g=0;
start->h=0;
start->x=si;
start->y=sj;
add(start,startList);
while(!startList.empty())
{
Node *cur=getMinNode(startList); //从搜索列表中获取f最小的节点
if(cur==NULL)
{
cout<<"自动寻路失败"<<endl;
return;
}
add(cur,endList); //把当前节点放入已搜索过的列表中
del(cur,startList); //从搜索列表中删除当前节点
for(int k=0; k<8; k++) //8个方向搜索
{
int cx=cur->x+dx[k];
int cy=cur->y+dy[k]; if(cx<0||cy<0||cx>=n||cy>=m) //坐标越界
{
continue;
} else if(mmap[cx][cy]=='#') //是墙
continue; Node *now=new Node;
now->x=cx;
now->y=cy;
now->parent=cur;
now->g=cur->g+getDis(now->x,now->y,cur->x,cur->y);
now->h=getDis(now->x,now->y,ei,ej);
now->f=now->g+now->h; if(in_List(now,startList)||in_List(now,endList)) //是否在搜索列表或已搜索列表中
continue; add(now,startList); //添加到搜索列表中
if(cx==ei&&cy==ej) //如果当前节点是终点
{
setRoad(now); //回溯找路径 for(int i=0; i<n; i++) //输出地图
{
for(int j=0; j<m; j++)
{
if(mmap[i][j]==ROAD||mmap[i][j]=='0'||mmap[i][j]=='1') //如果是路径则输出颜色设置成绿色
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);
}
else //否则无色只以亮度显示
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY);
cout<<mmap[i][j]<<" ";
}
cout<<endl;
}
return;
}
} }
cout<<"自动寻路失败"<<endl;
return;
} int main()
{
while(cin>>n>>m)
{
si=sj=ei=ej=0;
startList.clear();
endList.clear(); for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin>>mmap[i][j];
if(mmap[i][j]=='0')
{
si=i;
sj=j;
}
else if(mmap[i][j]=='1')
{
ei=i;
ej=j;
}
}
}
work();
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY);
}
return 0;
}
程序测试：
输入：
8 8
````#```
````#```
````#```
`0``#``1
````#```
````#```
```##```
```#````
10 8
````#```
``#`#```
``#`#```
``#`````
``#`##``
``#`#``#
`##`#``#
`###`##1
`0##`##`
####`#``
输出结果：
绿色表示路径。
最新文章
- 案例借鉴 | 某通讯巨头的IT建设方案
- 帆软报表FineReport中数据连接之Tomcat配置JNDI连接
- es6 ajax
- winApi
- 【BZOJ-1492】货币兑换Cash DP + 斜率优化 + CDQ分治
- chrome升级54以后，显示Adobe Flash Player 因过期而遭到阻止
- 系统安全扫描工具（appscan）的扫描类型小记
- nrf51822-添加DFU服务
- JAVA常用运算符
- UVA 11636 - Hello World! 水
- 判断display为隐藏还是显示及获取css
- Android之Margin和Padding属性及支持的长度单位
- pdo的简单介绍和使用
- python textwrap的使用
- logistics回归简单应用（二）
- Struts的FormFile与Commons-FileUpload控件使用心得
- oracle表空间不足时如何处理
- Maven实战(插件管理)
- 【BZOJ】2502 清理雪道
- [转] domeOS 环境搭建 自动化构建部署