久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

 找回密碼
 立即注冊(cè)

QQ登錄

只需一步，快速開始

搜索
查看: 3485|回復(fù): 0
打印 上一主題 下一主題
收起左側(cè)

A*尋路C++實(shí)現(xiàn)（可直接對(duì)數(shù)組上的兩點(diǎn)四方向?qū)ぢ罚?/span>

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
ID:108615 發(fā)表于 2016-3-13 00:19 | 只看該作者 回帖獎(jiǎng)勵(lì) |倒序?yàn)g覽 |閱讀模式
  1. #define DTY 20
  2. #define DTX 20

  4. struct point {
  5. int x, y;
  6. };

  8. struct A_node {
  9. // 路徑節(jié)點(diǎn)
  10. struct point pt; // 當(dāng)前節(jié)點(diǎn)坐標(biāo)
  11. int g, h, f; // 評(píng)估值
  12. struct point fpt; // 父節(jié)點(diǎn)坐標(biāo)
  13. struct A_node *next; // 鏈表下一個(gè)節(jié)點(diǎn)
  14. };

  16. struct bu_node {
  17. int fx; // 運(yùn)動(dòng)方向
  18. struct bu_node *next;
  19. };

  21. class Astar {
  22. public:
  23. struct A_node *openlist; // 開啟列表
  24. struct A_node *closelist; // 關(guān)閉列表
  25. struct bu_node *bulist; // 運(yùn)動(dòng)步序列表
  26. struct point spt; // 開始和目標(biāo)點(diǎn)坐標(biāo)
  27. struct point ept;
  28. int DT[DTY][DTX]; // 一張二維數(shù)組表示的地圖（根據(jù)實(shí)際需求設(shè)定大�。�

  30. Astar(); // 初始化
  31. void setspt(int y, int x); // 設(shè)置開始坐標(biāo)
  32. void setept(int y, int x); // 設(shè)置目標(biāo)坐標(biāo)
  33. void setdt(int dt[DTY][DTX]); // 設(shè)置地圖信息0為通路
  34. void addopennode(struct A_node *node); // 增加一個(gè)開啟節(jié)點(diǎn)
  35. void delopennode(struct A_node *node); // 刪除一個(gè)開啟節(jié)點(diǎn)
  36. void addclosenode(struct A_node *node); // 增加一個(gè)關(guān)閉節(jié)點(diǎn)
  37. int inopenlist(struct A_node *node); // 判斷節(jié)點(diǎn)是否已經(jīng)在開啟列表中
  38. int incloselist(struct A_node *node); // 判斷節(jié)點(diǎn)是否已經(jīng)在關(guān)閉列表中
  39. void pinggu(struct A_node *node, int G); // 對(duì)地圖上的一個(gè)節(jié)點(diǎn)進(jìn)行價(jià)值評(píng)估
  40. void axgo(); // 開始一步尋路
  41. int find(); // 是否找到路徑判定
  42. void gofind(); // 開始尋路
  43. void print();
  44. void addbu(int fx); // 往列表添加一步
  45. int delbu(); // 從列表刪除并返回一步
  46. };

  48. Astar::Astar() {
  49. openlist = NULL;
  50. closelist = NULL;
  51. bulist = NULL;
  52. }

  54. void Astar::setspt(int y, int x) {
  55. spt.y = y;
  56. spt.x = x;
  57. // 設(shè)置并把開始節(jié)點(diǎn)添加到開啟列表
  58. openlist = (A_node *) malloc(sizeof(A_node));
  59. if (openlist == NULL) {
  60. printf("開啟列表創(chuàng)建失敗！");
  61. }
  62. openlist->pt = spt;
  63. openlist->g = 1;
  64. openlist->next = NULL;
  65. }

  67. void Astar::setept(int y, int x) {
  68. ept.y = y;
  69. ept.x = x;
  70. }

  72. void Astar::setdt(int dt[DTY][DTX]) {
  73. for (int y = 0; y < 20; y++)
  74. for (int x = 0; x < 20; x++)
  75. DT[y][x] = dt[y][x];
  76. }

  78. void Astar::pinggu(struct A_node *node, int G) {
  79. if (inopenlist(node)) {
  80. node->f = 0;
  81. node->g = 0;
  82. node->h = 0;
  83. } else if (incloselist(node)) {
  84. node->f = 0;
  85. node->g = 0;
  86. node->h = 0;
  87. } else if (DT[node->pt.y][node->pt.x] == 8) {
  88. node->f = 0;
  89. node->g = 0; // 障礙標(biāo)記這里為貪吃蛇身標(biāo)記
  90. node->h = 0;
  91. } else {
  92. node->g = G + 10;

  94. int H, H1;
  95. H = node->pt.y - ept.y;
  96. if (H < 0)
  97. H = ept.y - node->pt.y;
  98. H1 = node->pt.x - ept.x;
  99. if (H1 < 0)
  100. H1 = ept.x - node->pt.x;
  101. node->h = (H + H1) * 10;

  103. node->f = node->h + node->g;
  104. }

  106. }

  108. void Astar::addopennode(struct A_node *node) {
  109. struct A_node *p;
  110. p = (A_node *) malloc(sizeof(A_node));
  111. *p = *node;
  112. p->next = openlist;
  113. openlist = p;
  114. }

  116. void Astar::delopennode(struct A_node *node) {
  117. struct A_node *p;
  118. p = openlist;
  119. if (openlist != NULL)
  120. openlist = openlist->next;
  121. if (p != NULL) {
  122. *node = *p;
  123. free(p);
  124. }
  125. }

  127. void Astar::addclosenode(struct A_node *node) {
  128. struct A_node *p;
  129. p = (A_node *) malloc(sizeof(A_node));
  130. *p = *node;
  131. p->next = closelist;
  132. closelist = p;
  133. }

  135. void Astar::addbu(int fx) {
  136. struct bu_node *p;
  137. p = (bu_node *) malloc(sizeof(bu_node));
  138. p->fx = fx;
  139. p->next = bulist;
  140. bulist = p;
  141. }

  143. int Astar::delbu() {
  144. struct bu_node *p;
  145. int fx = 0;
  146. p = bulist;
  147. if (bulist != NULL)
  148. bulist = bulist->next;
  149. if (p != NULL) {
  150. fx = p->fx;
  151. free(p);
  152. }
  153. return fx;
  154. }

  156. int Astar::inopenlist(struct A_node *node) {
  157. struct A_node *p;
  158. p = openlist;
  159. while (p != NULL) {
  160. if ((p->pt.y == node->pt.y) && (p->pt.x == node->pt.x))
  161. return 1;
  162. p = p->next;
  163. }
  164. return 0; // 在返回1不在返回0
  165. }

  167. int Astar::incloselist(struct A_node *node) {
  168. struct A_node *p;
  169. p = closelist;
  170. while (p != NULL) {
  171. if ((p->pt.y == node->pt.y) && (p->pt.x == node->pt.x))
  172. return 1;
  173. p = p->next;
  174. }
  175. return 0; // 在返回1不在返回0
  176. }

  178. int Astar::find() {
  179. struct A_node *p;
  180. p = closelist;
  181. while (p != NULL) {
  182. if ((p->pt.y == ept.y) && (p->pt.x == ept.x))
  183. return 1;
  184. p = p->next;
  185. }
  186. return 0; // 在返回1不在返回0
  187. }

  189. void Astar::axgo() {
  190. struct A_node p, p1, p2, p3, p4; // 不斜著走所以只對(duì)四個(gè)方向進(jìn)行評(píng)估
  191. delopennode(&p); // 從開啟列表取出最上層的節(jié)點(diǎn)
  192. addclosenode(&p); // 把這個(gè)節(jié)點(diǎn)加入到關(guān)閉列表
  193. p1.pt.y = p.pt.y + 1; // 上面的節(jié)點(diǎn)
  194. p1.pt.x = p.pt.x;
  195. p2.pt.y = p.pt.y - 1; // 下面的節(jié)點(diǎn)
  196. p2.pt.x = p.pt.x;
  197. p3.pt.y = p.pt.y; // 左面的節(jié)點(diǎn)
  198. p3.pt.x = p.pt.x - 1;
  199. p4.pt.y = p.pt.y; // 右面的節(jié)點(diǎn)
  200. p4.pt.x = p.pt.x + 1;
  201. p1.fpt = p.pt; // 設(shè)置父節(jié)點(diǎn)坐標(biāo)
  202. p2.fpt = p.pt;
  203. p3.fpt = p.pt;
  204. p4.fpt = p.pt;
  205. p1.g = p1.h = p1.f = 0;
  206. p2.g = p2.h = p2.f = 0;
  207. p3.g = p3.h = p3.f = 0;
  208. p4.g = p4.h = p4.f = 0;
  209. if ((p1.pt.y >= 0) && (p1.pt.y < DTY) && (p1.pt.x >= 0) && (p1.pt.x < DTX))
  210. pinggu(&p1, p.g); // 對(duì)當(dāng)前節(jié)點(diǎn)相鄰的節(jié)點(diǎn)進(jìn)行價(jià)值評(píng)估
  211. if ((p2.pt.y >= 0) && (p2.pt.y < DTY) && (p2.pt.x >= 0) && (p2.pt.x < DTX))
  212. pinggu(&p2, p.g);
  213. if ((p3.pt.y >= 0) && (p3.pt.y < DTY) && (p3.pt.x >= 0) && (p3.pt.x < DTX))
  214. pinggu(&p3, p.g);
  215. if ((p4.pt.y >= 0) && (p4.pt.y < DTY) && (p4.pt.x >= 0) && (p4.pt.x < DTX))
  216. pinggu(&p4, p.g);

  218. int bp1, bp2, bp3, bp4;
  219. bp1 = bp2 = bp3 = bp4 = 1; // 排序用入棧標(biāo)記
  220. // 4個(gè)待選節(jié)點(diǎn)排序后入棧
  221. for (int i = 0; i < 4; i++) {
  222. if ((p1.f >= p2.f * bp2) && (p1.f >= p3.f * bp3) && (p1.f >= p4.f * bp4)
  223. && (bp1 == 1)) {
  224. if ((p1.f + p1.g + p1.h) > 0)
  225. addopennode(&p1);
  226. bp1 = 0;
  227. }
  228. if ((p2.f >= p1.f * bp1) && (p2.f >= p3.f * bp3) && (p2.f >= p4.f * bp4)
  229. && (bp2 == 1)) {
  230. if ((p2.f + p2.g + p2.h) > 0)
  231. addopennode(&p2);
  232. bp2 = 0;
  233. }
  234. if ((p3.f >= p1.f * bp1) && (p3.f >= p2.f * bp2) && (p3.f >= p4.f * bp4)
  235. && (bp3 == 1)) {
  236. if ((p3.f + p3.g + p3.h) > 0)
  237. addopennode(&p3);
  238. bp3 = 0;
  239. }
  240. if ((p4.f >= p1.f * bp1) && (p4.f >= p2.f * bp2) && (p4.f >= p3.f * bp3)
  241. && (bp4 == 1)) {
  242. if ((p4.f + p4.g + p4.h) > 0)
  243. addopennode(&p4);
  244. bp4 = 0;
  245. }
  246. }
  247. }

  249. void Astar::gofind() {
  250. while ((openlist != NULL) && (!find()))
  251. axgo();
  252. if (openlist == NULL)
  253. printf("找不到可通行路徑！\n");

  255. if (find()) {
  256. // 生成運(yùn)動(dòng)方向列表
  257. struct A_node *p;
  258. int fx;
  259. p = closelist;
  260. while (p != NULL) {
  261. if (p->fpt.y > p->pt.y)
  262. fx = 1;
  263. else // 上
  264. if (p->fpt.y < p->pt.y)
  265. fx = 2;
  266. else // 下
  267. if (p->fpt.x > p->pt.x)
  268. fx = 3;
  269. else // 左
  270. if (p->fpt.x < p->pt.x)
  271. fx = 4; // 右
  272. addbu(fx);
  273. p = p->next;
  274. }
  275. }
  276. }

  278. void Astar::print() {
  279. printf("開始打印開啟列表：\n");
  280. struct A_node *p;
  281. p = openlist;
  282. while (p != NULL) {
  283. printf("節(jié)點(diǎn)坐標(biāo)：%d %d\n", p->pt.y, p->pt.x);
  284. printf("父節(jié)點(diǎn)坐標(biāo)：%d %d\n", p->fpt.y, p->fpt.x);
  285. printf("評(píng)估值：%d %d %d\n\n", p->g, p->h, p->f);
  286. p = p->next;
  287. }
  288. printf("\n開始打印關(guān)閉列表：\n");
  289. p = closelist;
  290. while (p != NULL) {
  291. printf("節(jié)點(diǎn)坐標(biāo)：%d %d\n", p->pt.y, p->pt.x);
  292. printf("父節(jié)點(diǎn)坐標(biāo)：%d %d\n", p->fpt.y, p->fpt.x);
  293. printf("評(píng)估值：%d %d %d\n\n", p->g, p->h, p->f);
  294. p = p->next;
  295. }
  296. }

  298. 用貪吃蛇測試：
  299. #include "ditu.h"
  300. #include "AX.h"
  301. #include "stdio.h"
  302. int main() {
  303. ditu T;
  304. while (1) {

  306. usleep(100000);
  307. clrscr();
  308. T.print();

  310. Astar A;
  311. // 初始化A星算法
  312. A.setspt(T.she_Y, T.she_X);
  313. A.setept(T.shiwu_Y, T.shiwu_X);
  314. A.setdt(T.dt);
  315. // 對(duì)蛇頭和食物開始尋路
  316. A.gofind();
  317. // A.print();//打印開啟和關(guān)閉列表信息

  319. A.delbu(); // 去掉起點(diǎn)信息
  320. int fx;
  321. do {
  322. fx = A.delbu(); // 輸出步序
  323. if (fx == 1)
  324. T.U();
  325. else if (fx == 2)
  326. T.D();
  327. else if (fx == 3)
  328. T.L();
  329. else if (fx == 4)
  330. T.R();

  332. usleep(100000);
  333. clrscr();
  334. T.print();
  335. } while (fx != 0);

  337. }
  338. return 0;
  339. }
復(fù)制代碼


分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏 分享淘帖 頂頂 踩踩
回復(fù)

使用道具 舉報(bào)

本版積分規(guī)則

手機(jī)版|小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表
主站蜘蛛池模板： 嫩草视频在线看 | 天天玩天天操天天干 | 日本又色又爽又黄的大片 | 高清人人天天夜夜曰狠狠狠狠 | 黄色日批视频 | 成人av电影网| 久久久久久综合 | 欧美又大粗又爽又黄大片视频 | 亚洲精品一区二区在线 | 久久久久久久久久久久久九 | 夜夜摸夜夜操 | 91嫩草精品 | 久久久久久蜜桃一区二区 | 久久精品国产一区 | 特级一级黄色片 | 最新中文字幕久久 | 成人在线观看网站 | 高清一区二区 | 一级毛片在线播放 | 99在线免费观看视频 | 99精品国产一区二区青青牛奶 | 黄色片在线免费看 | 香蕉视频1024| 日韩免费激情视频 | 中国一级特黄毛片大片 | 天天欧美| 一级欧美一级日韩片 | 亚洲男女视频在线观看 | 中文字幕一区二区三区四区 | 亚洲国产精品一区 | 日韩一区二区视频 | 婷婷狠狠| 毛片一级片 | 97超碰中文网 | 亚洲精选一区二区 | 黑人巨大精品 | 国产精品久久久久久中文字 | 中文成人无字幕乱码精品 | 国产1区2区 | 性天堂网 | 一区二区三区四区在线 |