算法课程设计
1.算法课设题目LOL峡谷地图最优路径规划
以下问题的计算，按照该地图的基本规则来进行在该地图中分布着各种形状不规则的障碍区域环境。整个地图模型，可以根据需求进行自行简化。
问题一：在任意起点与终点之间，规划一条最短路径。
问题二：当你拥有一个闪现的情况下（只能用一次），规划出从起点到终点的一条最短路径。
题目要求：1.生成障碍环境数据，提取障碍物区域。2.实现上述情况下，指定任意起始点到目标点下的最优路径规划算法。3.实现结果的可视化展示。
2.解决问题思路 2.1地图的简化和数据导入此题的要求区分障碍物和非障碍物部分，可以将地图转化为由0和1（1表示障碍物部分）组成的像素图，精度要求因人而异，我这里是在piskel在线网站上创建了100×100的像素图（太大精度的绘图容易丢失文件，建议下载该应用离线使用），并用黑色像素格绘画障碍物部分，最后导出为png文件，如下图：
那么如何将此图转化成由0和1组成的二值图呢，我这里使用的是c++中stb_image.h头文件中的函数处理，代码如下
intwidth,height,channels;unsignedchar*image=stbi_load("C:\Users\M\Downloads\NewPiskel2.png",&width,&height,&channels,STBI_grey);vectormap(height,vector(width));intthreshold=128;//阈值for(inty=0;yx][Point->y]==0)onechance=false;以下是具体的函数功能的实现：
访问私有类型将地图数据导入
voidAstar::InitAstar(vector&_map){map=_map;}计算f
intAstar::calf(point*p){returnp->g+p->h;}计算g
intAstar::calg(point*startp,point*np){intparentg=np->parent==NULL?0:np->parent->g;intng=(startp->x-np->x)*(startp->x-np->x)+(startp->y-np->y)*(startp->y-np->y);returnparentg+ng;}计算h
intAstar::calh(point*endp,point*np){return(endp->x-np->x)*(endp->x-np->x)+(endp->y-np->y)*(endp->y-np->y);}得到open列表中f值最小的点
point*Astar::getpoint(){if(!openList.empty()){autoPoint=openList.front();for(auto&p:openList)//遍历open表if(p->ff)Point=p;returnPoint;}returnNULL;}
通过坐标点判断点是否在表中
point*Astar::isInList(list&l,point*P){for(autop:l)if(p->x==P->x&&p->y==P->y)//通过坐标点判断点是否在表中returnp;returnNULL;}判断点是否可到达
boolAstar::isCanReach(point*p,point*target){if(target->xx>map.size()-1||target->yy>map[0].size()-1||(map[target->x][target->y]==1&&onechance==false)||target->x==p->x&&target->y==p->y||isInList(closeList,target))//如果点与当前节点重合、超出地图、是障碍物、或者在关闭列表中，返回falsereturnfalse;elseif(map[target->x][target->y]==1&&onechance==true)//为障碍物但是有闪现的条件下可到达{returntrue;}else{if(abs(p->x-target->x)+abs(p->y-target->y)==1)//非斜角可以到达returntrue;else{//斜对角要判断是否绊住if(map[p->x][target->y]==0&&map[target->x][p->y]==0)returntrue;elsereturnfalse;}}}访问周围可到达的点
vectorAstar::getSurroundPoints(point*p){vectorsurroundpoints;for(intx=p->x-1;xx+1;x++)for(inty=p->y-1;yy+1;y++)if(isCanReach(p,newpoint(x,y)))surroundpoints.push_back(newpoint(x,y));returnsurroundpoints;}求最短路径
listAstar::getpath(point&startpoint,point&endpoint){listpath;if(map[startpoint.x][startpoint.y]==1||map[endpoint.x][endpoint.y]==1)//防止起点终点设置到障碍物中returnpath;openList.push_back(newpoint(startpoint.x,startpoint.y));//置入起点onechance=false;//是否可以闪现judge=0;//判断数while(!openList.empty()){autoPoint=getpoint();//找到F值最小的点openList.remove(Point);closeList.push_back(Point);//判断闪现有无结束if(judge==0&&map[Point->x][Point->y]==1){judge=1;}if(judge==1&&map[Point->x][Point->y]==0)onechance=false;//1.找到当前周围8个格中可以通过的格子autosurroundPoints=getSurroundPoints(Point);for(auto&target:surroundPoints){//2.对某一个格子，如果它不在开启列表中，加入到开启列表，设置当前格为其父节点，计算FGHif(!isInList(openList,target)){target->parent=Point;target->g=calg(Point,target);target->h=calh(&endpoint,target);target->f=calf(target);openList.push_back(target);}//3.对某一格子，它在开启列表中，计算G值，如果比原来的大，就什么都不做，否则设置它的父节点为当前点，并更新G和Felse{inttempg=calg(Point,target);if(tempgg){target->parent=Point;target->g=tempg;target->f=calf(target);}}point*lastPoint=isInList(openList,&endpoint);//终点在open表就将该路径存到一个列中if(lastPoint){point*ep=lastPoint;while(ep){path.push_front(ep);ep=ep->parent;}openList.clear();closeList.clear();returnpath;}}}returnpath;}2.3可视化展示使用c++语言下的QT项目进行实现
相关代码如下：
鼠标点击事件
voidLOLDREWING::mousePressEvent(QMouseEvent*event){//获取鼠标坐标QPointpos=event->pos();//更新状态if(!start_pressed_){start=pos;start_pressed_=true;}else{end=pos;update();start_pressed_=false;}}绘图事件
voidLOLDREWING::paintEvent(QPaintEvent*event){QWidget::paintEvent(event);intwidth,height,channels;unsignedchar*image=stbi_load("C:\Users\M\Downloads\NewPiskel2.png",&width,&height,&channels,STBI_grey);//转化为二维数组vectormap(height,vector(width));intthreshold=128;//阈值for(inty=0;y