A star
a星自动寻路算法的实现
规则可以自己去找
根本原理就是建立一个树，遍历所有可以走的节点，最终找出f值最小的那一个
在bilibili上/video/BV1Cv411x76X?from=search&seid=8246083468330961939，学习这门课，后自己敲的，
手敲不易，点个赞呗
#include<stdio.h>#include<stdlib.h>#include<iostream>#include<vector>#include<string.h> using namespace std;//#include<pch.h>//竖着y轴的行数#define ROWS 9//横 x 列数#define COLS 11//输出#define ZXDJ 10//直线代价 #define XXDJ 14//斜线代价 struct MyPoint{int row;//行 int col;//列 int f;//总代价 int g;//移动代价，int h; //估算成本。void setF(){f=g+h;} };//树的节点类型 struct TreeNode{ MyPoint pos; //当前点坐标 vector<TreeNode*> childs;//存储当前点的子节点指针的 数组 动态数组容器 装下很多个指针 TreeNode* pParent; //存储当前点的父节点指针的 变量 };enum direct{p_up,p_down,p_left,p_right,p_lup,p_ldown,p_rup,p_rdown};//枚举类型 //辅助地图节点类型//struct PathNode{////bool//}; //输出地图 void printMap(int map[ROWS][COLS]);int getH(MyPoint endPos,MyPoint pos)//计算h值 {int x=(endPos.col>pos.col)?(endPos.col-pos.col):(pos.col-endPos.col);//取绝对值 int y=(endPos.row>pos.row)?(endPos.row-pos.row):(pos.row-endPos.row);return (x+y)*ZXDJ;} //判断是否需要统计 bool needAdd(MyPoint pos,int map[ROWS][COLS], bool pathMap[ROWS][COLS]){if(pos.row>=ROWS||pos.row<0||pos.col>=COLS||pos.col<0)//范围限制 return false;if(map[pos.row][pos.col])//不是墙 return false;if(pathMap[pos.row][pos.col])//是否走过 return false;return true;}int main(){//地图int map[ROWS][COLS] = {{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0}};//2 辅助地图 false 0；没有走过 true 1：走过bool pathMap[ROWS][COLS]={0};//3 起点 终点MyPoint begpos={2,2}; MyPoint endpos={4,8}; //4 标记起点走过pathMap[begpos.row][begpos.col]=true;//5 创建一棵树 起点是树的根节点//创建一个新的节点 TreeNode* pNew=new TreeNode;memset(pNew,0,sizeof (TreeNode)); //注意头文件 //新节点成为树根 // pRoot一直指向树的根节点 TreeNode* pRoot=pNew;//新节点是记录起点 pRoot->pos =begpos; //6 需要一个动态数组 存储用来比较的 节点 vector<TreeNode*>buff;//buff是数组名字 //7 寻路TreeNode* pCurrent=pRoot;//MyPoint currentPos=begPos;TreeNode* pChild=NULL;//迭代器 vector<TreeNode*>::iterator it;vector<TreeNode*>::iterator itMin;//最小的f值 bool isFindEnd=false;//用于储存是否找到的结果 while(1){//7.1找到当前点周围能走的点for(int i=0;i<8;i++){pChild=new TreeNode;memset(pChild,0,sizeof (TreeNode)); pChild->pos=pCurrent->pos; //pos是坐标 switch(i){case p_up:pChild->pos.row--;pChild->pos.g+=ZXDJ; break;case p_down:pChild->pos.row++;pChild->pos.g+=ZXDJ; break;case p_left:pChild->pos.col--;pChild->pos.g+=ZXDJ; break;case p_right:pChild->pos.col++;pChild->pos.g+=ZXDJ; break;case p_lup:pChild->pos.row--;pChild->pos.col--;pChild->pos.g+=XXDJ; break;case p_rup:pChild->pos.row--;pChild->pos.col++;pChild->pos.g+=XXDJ; break;case p_ldown:pChild->pos.row++;pChild->pos.col--;pChild->pos.g+=XXDJ; break; case p_rdown:pChild->pos.row++;pChild->pos.col++;pChild->pos.g+=XXDJ; break; default:break;}//printf("(%d,%d):%d\n",pChild->pos.row,pChild->pos.col,pChild->pos.g);//7.2计算ghf 值pChild->pos.h=getH(endpos, pChild->pos);pChild->pos.setF();//7.3 入树 ，入 buff数组if(needAdd(pChild->pos,map,pathMap)){//入树 pCurrent->childs.push_back(pChild);pChild->pParent=pCurrent; //入buff数组 buff.push_back(pChild);pathMap[pChild->pos.row][pChild->pos.col]=true;//标记走过 }else{delete pChild;}} //7.4 从buff数组中找到f最小的一个itMin=buff.begin();for(it=buff.begin();it!=buff.end();it++){itMin=(((*itMin)->pos.f>(*it)->pos.f)?it:itMin);} //7.5删掉，变化成当前点pCurrent=*itMin;buff.erase(itMin);//7.6判断是否寻路结束 if(pCurrent->pos.row==endpos.row&&pCurrent->pos.col==endpos.col){isFindEnd=true;break;}if(buff.empty())break; } if(isFindEnd){printf("找到终点了\n");while(pCurrent){printf("(%d,%d)",pCurrent->pos.row,pCurrent->pos.col);pCurrent=pCurrent->pParent;}printf("\n");}printMap(map);while (1);return 0;}void printMap(int map[ROWS][COLS]) {for (int i = 0; i < ROWS; i++){for (int j = 0; j < COLS;j++){if (map[i][j] == 0)printf("--");else if (map[i][j] == 1)printf("墙");}printf("\n");}}
