首页 / 算法 / 通过A*算法实现多节点的寻径
通过A*算法实现多节点的寻径
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了通过A*算法实现多节点的寻径,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含9583字,纯文字阅读大概需要14分钟。
内容图文
1 /* 2 A star 算法的基础处理 3 */ 4 #ifndef _A_STAR_BASE_H_ 5 #define _A_STAR_BASE_H_ 6 #include "windows.h" 7 8 typedef struct _APoint{ 9int x; // x 坐标 10int y; // y 坐标 11int type; // 类型 12int f; // f = g + h 13int g; 14int h; 15 } APoint, *PAPoint; 1617enum APointType{ 18 APT_UNKNOWN, // 未知状态 19 APT_OPENED, // 开放列表中 20 APT_CLOSED, // 关闭列表中 21 APT_STARTPOINT, // 起始点 22 APT_ENDPOINT // 结束点 23}; 242526class CAStarBase{ 27public: 28 CAStarBase(); 29 ~CAStarBase(); 30private: 31 PAPoint m_pAPointArr; 32int m_nAPointArrWidth; 33int m_nAPointArrHeight; 3435 PAPoint m_pStartPoint, m_pEndPoint, m_pCurPoint; 36char* m_pOldArr; 37public: 38 BOOL Create(char* pDateArr, int nWidth, int nHeight); 39void SetStartPoint(int x, int y); 40void SetEndPoint(int x, int y); 41void SetOpened(int x, int y); 42void SetClosed(int x, int y); 43void SetCurrent(int x, int y); 44void PrintCharArr(); 4546 PAPoint CalcNextPoint(PAPoint ptCalc); // 应用迭代的办法进行查询 47}; 4849#endif
1 #include "A_Star.h" 2 #include <cstdio> 3 4CAStarBase::CAStarBase() 5{ 6 m_pAPointArr = NULL; 7 m_nAPointArrWidth = 0; 8 m_nAPointArrHeight = 0; 9 10 m_pStartPoint = NULL; 11 m_pEndPoint = NULL; 12 m_pCurPoint = NULL; 13 14} 15 16 CAStarBase::~CAStarBase() 17{ 18 19} 20 21 BOOL CAStarBase::Create(char* pDateArr, int nWidth, int nHeight) 22{ 23if (!pDateArr) return FALSE; //数组地址是否存在 24if (nWidth<1 || nHeight<1) return FALSE; //判断数组的长宽是否大于一 25 m_pAPointArr = new APoint[nWidth*nHeight]; 26if (!m_pAPointArr) return FALSE; 27 m_pOldArr = pDateArr; //父节点9指针形式) 28 m_nAPointArrWidth = nWidth; //数组的宽度 29 m_nAPointArrHeight = nHeight; //数组的高度 30// 初始化数组内容 31for (int y = 0; y<m_nAPointArrHeight; y++) 32 { 33for (int x = 0; x<m_nAPointArrWidth; x++) 34 { 35 m_pAPointArr[y*m_nAPointArrWidth + x].x = x; //赋值形式?! 36 m_pAPointArr[y*m_nAPointArrWidth + x].y = y; 37 m_pAPointArr[y*m_nAPointArrWidth + x].g = 0; 38 m_pAPointArr[y*m_nAPointArrWidth + x].f = 0; 39 m_pAPointArr[y*m_nAPointArrWidth + x].h = 0; 40 41if (pDateArr[y*m_nAPointArrWidth + x] == ‘0‘) 42 { 43 m_pAPointArr[y*m_nAPointArrWidth + x].type = APT_OPENED; 44 } 45elseif (pDateArr[y*m_nAPointArrWidth + x] == ‘1‘) 46 { 47 m_pAPointArr[y*m_nAPointArrWidth + x].type = APT_CLOSED; 48 } 49elseif (pDateArr[y*m_nAPointArrWidth + x] == ‘S‘) 50 { 51 m_pAPointArr[y*m_nAPointArrWidth + x].type = APT_STARTPOINT; 52 m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth + x; //赋值形式?! 53 m_pCurPoint = m_pStartPoint; 54 } 55elseif (pDateArr[y*m_nAPointArrWidth + x] == ‘E‘) 56 { 57 m_pAPointArr[y*m_nAPointArrWidth + x].type = APT_ENDPOINT; 58 m_pEndPoint = m_pAPointArr + y*m_nAPointArrWidth + x; 59 } 60else{ 61 m_pAPointArr[y*m_nAPointArrWidth + x].type = APT_UNKNOWN; 62 } 63 64 } 65 } 66return TRUE; //初始化返回为真 67} 68 69void CAStarBase::SetStartPoint(int x, int y) 70{ 71if (m_pStartPoint && m_pAPointArr[y*m_nAPointArrWidth + x].type != APT_CLOSED) 72 { 73 m_pStartPoint->type = APT_OPENED; 74// 设置新的值 75 m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth + x; 76 m_pStartPoint->type = APT_STARTPOINT; 77 m_pCurPoint = m_pStartPoint; 78 } 79} 80 81void CAStarBase::SetEndPoint(int x, int y) 82{ 83if (m_pStartPoint && m_pAPointArr[y*m_nAPointArrWidth + x].type != APT_CLOSED) 84 { 85 m_pStartPoint->type = APT_OPENED; 86// 设置新的值 87 m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth + x; 88 m_pStartPoint->type = APT_ENDPOINT; 89 } 90} 91 92void CAStarBase::SetCurrent(int x, int y) 93{ 94// if ( m_pAPointArr[y*m_nAPointArrWidth+x].type==APT_OPENED ) 95 { 96 m_pCurPoint = m_pAPointArr + y*m_nAPointArrWidth + x; 97 } 98} 99100void CAStarBase::SetOpened(int x, int y) //建立“开启列表”101{ 102if (m_pAPointArr[y*m_nAPointArrWidth + x].type != APT_OPENED) 103 { 104 m_pAPointArr[y*m_nAPointArrWidth + x].type = APT_OPENED; 105 } 106} 107108void CAStarBase::SetClosed(int x, int y) //建立“关闭列表”109{ 110if (m_pAPointArr[y*m_nAPointArrWidth + x].type != APT_CLOSED) 111 { 112 m_pAPointArr[y*m_nAPointArrWidth + x].type = APT_CLOSED; 113 } 114} 115116void CAStarBase::PrintCharArr() //打印终点117{ 118if (m_pOldArr) //是否有父节点119 { 120for (int y = 0; y<m_nAPointArrHeight; y++) 121 { 122for (int x = 0; x<m_nAPointArrWidth; x++) 123 { 124 printf("%c ", m_pOldArr[x + m_nAPointArrWidth*y]); 125 } 126 printf("\r\n"); 127 } 128 printf("\r\n"); 129 } 130} 131132PAPoint CAStarBase::CalcNextPoint(PAPoint ptCalc) 133{ 134if (ptCalc == NULL) 135 { 136 ptCalc = m_pStartPoint; 137 } 138int x = ptCalc->x; 139int y = ptCalc->y; 140int dx = m_pEndPoint->x; 141int dy = m_pEndPoint->y; 142int xmin = x, ymin = y, vmin = 0; // 最优步骤的坐标和值 143// 判断是否已经到了最终的位置 144if ((x == dx && abs(y - dy) == 1) || (y == dy && abs(x - dx) == 1)) //是否在重点的周围145 { 146 printf("\r\n\n"); 147 PrintCharArr(); 148return m_pEndPoint; 149 } 150// 上 151if (m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].type == APT_OPENED && y>0) 152 { 153 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].g = 10; 154 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].h = 15510 * (abs(x - dx) + abs(y - 1 - dy)); 156 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].f = 157 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].g + m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].h; 158if (vmin == 0) 159 { 160 xmin = x; 161 ymin = y - 1; 162 vmin = m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].f; 163 } 164else{ 165if (vmin > m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].f) 166 { 167 xmin = x; 168 ymin = y - 1; 169 vmin = m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y - 1)].f; 170 } 171 } 172 } 173// 下 174if (m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].type == APT_OPENED && y<m_nAPointArrHeight) 175 { 176 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].g = 10; 177 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].h = 17810 * (abs(x - dx) + abs(y + 1 - dy)); 179 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].f = 180 m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].g + m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].h; 181if (vmin == 0) 182 { 183 xmin = x; 184 ymin = y + 1; 185 vmin = m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].f; 186 } 187else{ 188if (vmin > m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].f) 189 { 190 xmin = x; 191 ymin = y + 1; 192 vmin = m_pAPointArr[(x + 0) + m_nAPointArrWidth*(y + 1)].f; 193 } 194 } 195 } 196// 左 197if (m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].type == APT_OPENED && x>0) 198 { 199 m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].g = 10; 200 m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].h = 20110 * (abs(x - 1 - dx) + abs(y - dy)); 202 m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].f = 203 m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].g + m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].h; 204if (vmin == 0) 205 { 206 xmin = x - 1; 207 ymin = y; 208 vmin = m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].f; 209 } 210else{ 211if (vmin > m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].f) 212 { 213 xmin = x - 1; 214 ymin = y; 215 vmin = m_pAPointArr[(x - 1) + m_nAPointArrWidth*y].f; 216 } 217 } 218 } 219// 右 220if (m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].type == APT_OPENED && x<m_nAPointArrWidth) 221 { 222 m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].g = 10; 223 m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].h = 22410 * (abs(x + 1 - dx) + abs(y - dy)); 225 m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].f = 226 m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].g + m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].h; 227if (vmin == 0) 228 { 229 xmin = x + 1; 230 ymin = y; 231 vmin = m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].f; 232 } 233else{ 234if (vmin > m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].f) 235 { 236 xmin = x + 1; 237 ymin = y; 238 vmin = m_pAPointArr[(x + 1) + m_nAPointArrWidth*y].f; 239 } 240 } 241 } 242243244if (vmin) 245 { 246 SetCurrent(xmin, ymin); 247 SetClosed(xmin, ymin); 248 printf("(%d,%d)->", xmin, ymin); 249 *(m_pOldArr + xmin + m_nAPointArrWidth*ymin) = ‘-‘; //走过的路径用‘-’表示 250//PrintCharArr(); //每在关闭列表中加入一个值,就输出一遍251 PAPoint pApoint = CalcNextPoint(m_pCurPoint); // 如果有最优点则迭代,则否就返回NULL 252if (pApoint == NULL) 253 { 254 SetCurrent(x, y); 255 SetClosed(xmin, ymin); 256 *(m_pOldArr + xmin + m_nAPointArrWidth*ymin) = ‘0‘; //不做改变257return CalcNextPoint(m_pCurPoint); 258 } 259return pApoint; 260 } 261else{ 262return NULL; 263 } 264265 }
1 // AStarMath.cpp : 定义控制台应用程序的入口点。 2 // 3 4 // #include <stdafx.h> 5 #include "A_Star.h" 6 #include <stdio.h> 7 8CAStarBase Astarbase; 910int main() 11{ 12char pBuff[][12] = { 13‘S‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 14‘0‘, ‘1‘, ‘1‘, ‘0‘, ‘0‘, ‘1‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 15‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘1‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 16‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 17‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 18‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 19‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 20‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 21‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 22‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘E‘, 23‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, 24‘0‘, ‘0‘, ‘0‘, ‘1‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘, ‘0‘25 }; 26 Astarbase.Create(&pBuff[0][0], 12, 12); 27 Astarbase.PrintCharArr(); 28 PAPoint pPoint = Astarbase.CalcNextPoint(NULL); 29if (pPoint == NULL) 30 { 31 printf("no path can arrive!\r\n"); 32 } 33else{ 34 printf("success arrived!\r\n"); 35 } 36 getchar(); 37return0; 38 }
原文:http://www.cnblogs.com/ingslh/p/4995087.html
内容总结
以上是互联网集市为您收集整理的通过A*算法实现多节点的寻径全部内容,希望文章能够帮你解决通过A*算法实现多节点的寻径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。