资源描述：
《C++八方向Astar寻路算法大作业.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、111111111122222222212345678901234567890123456782T34567891011121314151617181920212223242526272S8编程实现从S到T的最短路径算法，运动方向为上下左右。在图上给出最终的路径，以及搜索的过程。算法建议使用A*。作业上交时间：最后一节课前发送到课程邮箱。包括源代码，以及运行出来的效果图。第1页，共9页Homework3：Solution:1、算法分析：地图的构建，需要定义一个整型二维数组，障碍位置为1，可通过点为0；同样定义坐标点结构体，以存放每个点的行列GHF父结点等信息。As
2、tar算法要用到两个表来存放将要搜索的结点和还未搜索的结点，分别是开放列表openList和封闭列表openList，Astar算法的计算步骤如下：①S→openList②S邻居→openListopenList→S→closeList③S邻居有8个如何确定先检查哪个？G移动成本(10/14)HManhattan距离H=(
3、e_r-r
4、+
5、e_c-c
6、)*10F=G+HS=F最小的点④重复②③，openList=NULL未到终点，说明无通路。当endPoint在开放表中的时候，说明已经找到通路，根据每个结点的父结点信息，通过回溯可以找出通路。NOTE:在第②步中检
7、查邻居时，以下几点需要注意：①若邻居结点已经在封闭表closeList中，可以直接忽略。②若邻居结点不在开放表openList和封闭表closeList中，计算GHF的值，并设置该结点的父亲结点③若邻居结点已经在开放表openList中，若能得到更小的G值则重新计算GHF的值并更新父结点第2页，共9页2、程序实现：/*************************************************************************>FileName:Astar.cpp>Author:lx>CreatedTime:Sat15Apr201
8、705:30:12PMCST************************************************************************/#include#include#include#include#definerow27#definecol27usingnamespacestd;constintdirection[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//方向enum{
9、virable,wall,inOpen,inClose,start,goal};//定义方格点structpoint{intflag;//标志位0为可走，1为墙壁2在penlist3在closelist中4为起点5为终点unsignedintr;unsignedintc;unsignedinth;unsignedintg;unsignedintf;point*parent;point(){r=0;c=0;h=0;g=0;h=0;parent=NULL;}};//定义开放表OpenListstructOpenList{point*openPoint;OpenList
10、*next;OpenList(){next=NULL;};};//定义封闭表structCloseList{point*closePoint;CloseList*next;CloseList(){next=NULL;}};//往开放表中添加坐标点的函数voidaddPointToOpenList(OpenList*openList,point*point){if(openList==NULL){cout<<"NodataintheOpenList!";return;}if(point->flag!=start){point->flag=inOpen;}Open
11、List*temp=newOpenList;temp->openPoint=point;while(openList->next!=NULL)//按从小到大的顺序存储openList;{if(point->fnext->openPoint->f){OpenList*tempadd=openList->next;temp->next=tempadd;break;第3页，共9页}elseopenList=openList->next;}openList->next=temp;}//往封闭表中添加元素voidaddPointToCloseList(
12、Close
