devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】A*最优寻路算法（附加迷宫障碍自动生成）_迷宫寻路c++

作者：凡人多烦事01 | 2024-05-02 21:31:58

赞

踩

迷宫寻路c++

目录

一、前言

二、关于迷宫（障碍）的生成

1.简单解释

 2.代码

三、A*算法

1.简单解释

 2.效果演示

3.代码

四、总代码

五、总结

一、前言

        最近上了人工智能的课程，学了A*算法，就尝试使用C++来实现这个算法。

        为了更方便的体现寻路过程，这里使用了easyx图像库来实时展示运动的过程。可以去easyx的官网下载这个库。easyx官网

        easyx库在使用中最好在：调试——调试属性——配置属性——高级——字符集        设置使用多字节字符集，否则有些函数可能会报错。

二、关于迷宫（障碍）的生成

1.简单解释

        首先我们可以用一个二维数组来存放迷宫，其大小由用户输入。用1表示墙壁，0表示路。

        开始初始化迷宫数组应该初始化为下面的状态。

        

         数组（1，1）为开始点，然后开始寻找旁边是否有通路，如果有，则随机打通一路，然后记录下当前的坐标，进行递归。函数出口就是没有找到可以打通的地方，则直接return。走过的路需要标记为走过，否则可能会出现死循环导致程序不正确。这里标记走过的路为5。

        进行完这一步后，需要将之前数组中所有的5改为0，即改为通路。

        最后将其显示，大概就是下面这个效果，当然这种算法生成的迷宫质量不是很好，不过现在也足够使用了。

           

        当然我们使用A*算法不需要迷宫，只需要一些障碍就行，我们再写一个函数，随机删除上面迷宫的一些墙，就完成生成障碍的这一步了。

         

 2.代码

存放迷宫的结构体

  1. struct AStar {
  2. 	int M;						//M*M map
  3. 	int** maze;					//map迷宫
  4. 	//int* close;					//close表
  5. 	//int* open;					//open表
  6. 	int O_row;					//开始的行
  7. 	int O_col;					//开始的列	
  8. 	int E_row;					//终点行
  9. 	int E_col;					//终点列
  10. }Astar{ 0,NULL,1,1,0,0 };

初始化迷宫

  1. int main()
  2. {
  3. 	Astar.M = 0;
  4. 	cout << "请输入迷宫是几乘几的" << endl;
  5. 	cin >> Astar.M;
  6. 	if (Astar.M % 2 == 0)//如果输入不为奇数变为奇数
  7. 		Astar.M++;
  8.  
  9. 	Astar.E_col = Astar.M;
  10. 	Astar.E_row = Astar.M;
  11.     Astar.maze = new int* [Astar.M + 2];//动态创建二维数组
  12. 	for (int i = 0; i < Astar.M + 2; i++)
  13. 		Astar.maze[i] = new int[Astar.M + 2];//每一行申请一个int空间的M+2列空间
  14. }
  15.  
  16. //初始化迷宫
  17. void Init_Maze(AStar& Astar)
  18. {
  19. 	for (int i = 0; i < Astar.M + 2; i++)//动态创建迷宫
  20. 		for (int j = 0; j < Astar.M + 2; j++)
  21. 		{
  22. 			if (i == 0 || i == Astar.M + 1)//1为墙壁
  23. 				Astar.maze[i][j] = 1;
  24. 			if ((i % 2 == 1) && (j % 2 == 1))
  25. 				Astar.maze[i][j] = 0;
  26. 			else Astar.maze[i][j] = 1;
  27. 		}
  28. }

寻找邻居

  1. bool findneighbor(AStar& Astar, int x_index, int y_index)
  2. {
  3. 	if ((x_index >= 3 && Astar.maze[x_index - 2][y_index] == 0) || (x_index <= Astar.M - 1 && Astar.maze[x_index + 2][y_index] == 0)
  4. 		|| (y_index >= 3 && Astar.maze[x_index][y_index - 2] == 0) || (y_index <= Astar.M - 1 && Astar.maze[x_index][y_index + 2] == 0))
  5. 		return 1;
  6. 	else
  7. 		return 0;
  8. }

创建迷宫

  1. //随机创建迷宫
  2. void creatMaze(AStar& Astar, int x_index, int y_index)
  3. {
  4. 	int pos, x, y, flag = 0;
  5. 	x = x_index;
  6. 	y = y_index;
  7.  
  8. 	while (1)
  9. 	{
  10. 		flag = 0;
  11. 		flag = findneighbor(Astar, x, y);
  12. 		if (!flag)
  13. 			return;
  14. 		else {
  15. 			Astar.maze[x_index][y_index] = 5;
  16. 			x = x_index;
  17. 			y = y_index;
  18. 			while (1)
  19. 			{
  20. 				pos = rand() % (4 - 1 + 1) + 1;
  21. 				if (pos == 1 && x_index >= 3 && Astar.maze[x_index - 2][y_index] == 0)//上
  22. 				{
  23. 					x_index -= 2;
  24. 				}
  25. 				else if (pos == 2 && x_index <= Astar.M - 1 && Astar.maze[x_index + 2][y_index] == 0)//下
  26. 				{
  27. 					x_index += 2;
  28. 				}
  29. 				else if (pos == 3 && y_index <= Astar.M - 1 && Astar.maze[x_index][y_index + 2] == 0)
  30. 				{
  31. 					y_index += 2;
  32. 				}
  33. 				else if (pos == 4 && y_index >= 3 && Astar.maze[x_index][y_index - 2] == 0)
  34. 				{
  35. 					y_index -= 2;
  36. 				}
  37. 				Astar.maze[(x + x_index) / 2][(y + y_index) / 2] = 5;
  38. 				Astar.maze[x_index][y_index] = 5;
  39.  
  40. 				//	showmaze(maze, M);
  41.  
  42. 				creatMaze(Astar, x_index, y_index);
  43. 				break;
  44. 			}
  45. 		}
  46. 	}
  47. }

 改变数组中的通路，标识入口和出口

  1. //给创建的迷宫创建标识
  2. void makeMaze(AStar& Astar)
  3. {
  4. 	for (int i = 0; i < Astar.M + 2; i++)
  5. 		for (int j = 0; j < Astar.M + 2; j++)
  6. 		{
  7. 			if (Astar.maze[i][j] == 5)
  8. 			{
  9. 				Astar.maze[i][j] = 0;
  10. 			}
  11. 		}
  12. 	Astar.maze[1][1] = 8;
  13. 	Astar.maze[Astar.M][Astar.M] = 2;
  14. }

 改变地形

  1. //改变地形，出现更多通路
  2. void MakeDifficult(AStar& Astar)
  3. {
  4. 	if (Astar.M > 5)
  5. 	{
  6. 		int half = (int)((0.4 * Astar.M) * (0.5 * Astar.M));
  7. 		int x_c, y_c = 0;
  8. 		for (int i = 0; i < half;)
  9. 		{
  10. 			x_c = rand() % (Astar.M - 1 + 1) + 1;
  11. 			y_c = rand() % (Astar.M - 1 + 1) + 1;
  12. 			if (Astar.maze[x_c][y_c] == 1)
  13. 			{
  14. 				Astar.maze[x_c][y_c] = 0;
  15. 				i++;
  16. 			}
  17. 		}
  18. 	}
  19. }

显示迷宫

  1. //图像显示迷宫
  2. //3为路，4为搜寻的路，1为墙，2为终点，8为开始
  3. void show(AStar& Astar)
  4. {
  5. 	IMAGE star, wall, ball ,ly;
  6. 	loadimage(&star, "./五角星.png", SIZE, SIZE);
  7. 	loadimage(&wall, "./墙.png", SIZE, SIZE);
  8. 	loadimage(&ball, "./球.png", SIZE, SIZE);
  9. 	loadimage(&ly, "./兰音.png", SIZE, SIZE);
  10. 	for (int i = 0; i < Astar.M + 2; i++)
  11. 	{
  12. 		for (int j = 0; j < Astar.M + 2; j++)
  13. 		{
  14. 			if (Astar.maze[i][j] == 1)
  15. 			{
  16. 				putimage((j + Astar.M + 2 + 1) * SIZE, (i)*SIZE, &wall);
  17. 				putimage(j * SIZE, i * SIZE, &wall);
  18. 			}
  19. 			else if (Astar.maze[i][j] == 4)
  20. 			{
  21. 				putimage((j + Astar.M + 2 + 1) * SIZE, (i)*SIZE, &ball);
  22. 			}
  23. 			else if (Astar.maze[i][j] == 3)
  24. 			{
  25. 				putimage(j * SIZE, (i)*SIZE, &ly);
  26. 			}
  27. 		}
  28. 	}
  29. 	putimage((Astar.M + 2 + 1 + 1) * SIZE, (SIZE), &star);
  30. 	putimage((Astar.M + Astar.M + 2 + 1) * SIZE, (Astar.M) * SIZE, &star);
  31. 	putimage(SIZE, SIZE, &star);
  32. 	putimage(Astar.M * SIZE, Astar.M * SIZE, &star);
  33. }

至此，迷宫或者障碍的创建就完成了，此时的迷宫保存在maze这个二维数组中。

三、A*算法

1.简单解释

        我们假设一开始是下面这幅图，起点为左上角，终点为右下角。A*算法的重点就是我们设置估价函数F的过程。

        F=G+H。其中G是起始节点到当前节点的代价，H是当前节点到目标节点的代价。A*算法就是在A算法上的改进，也就是要求G必须大于0，H必须不大于实际代价这两个条件。

        我们假设G为从开始移动到现在这个节点的步数，H为曼哈顿距离（即|xe-xi|+|ye-yi|，其中xe，ye是终点坐标，xi，yi是当前点坐标），为了方便起见，我们假设只能左右上下行走，不能斜着走，那么上面的F就为下面这样。起点的F值要给最大。

 

         那么A*算法就是会找到最小的那个F然后走上去，并且记录下父节点。专业的来讲就是把当前节点所有可以走的节点的F值算出来，把节点放入open表中，然后找到最小的F值的节点，放入close表中。这里我们可以将open表化为一个树，close表化为一个数组。

         当然我们前提是行走的四个方向都要提前做好确定，然后每次都寻找最后入树且代价最小的那一个节点，走上去，继续寻找后续节点。人工智能书上也给出了相应的参考框图。

 

 2.效果演示

3.代码

  1. int main()
  2. {
  3. 	treeNode* pRoot = NULL;	 //准备一棵树
  4. 	vector<treeNode*> open;  //准备一个数组
  5.  
  6. 	vector<treeNode*>::iterator it;	//迭代器
  7. 	vector<treeNode*>::iterator itmin;	//迭代器
  8.     pRoot = creatTreeNode(Astar.O_row, Astar.O_col); //起点入树
  9.     treeNode* Now = pRoot;
  10. 	pRoot->pos.F = Astar.M * Astar.M;
  11. 	open.push_back(pRoot);
  12. 	while (1)
  13. 	{
  14. 		//1.把当前能走的点找出来
  15. 		for (int i = 0; i < 4; i++)
  16. 		{
  17. 			treeNode* pChild = creatTreeNode(Now->pos.row, Now->pos.col);
  18. 			switch (i)
  19. 			{
  20. 			case Up:
  21. 				pChild->pos.row--;
  22. 				pChild->pos.g = Now->pos.g + 1;
  23. 				break;
  24. 			case Down:
  25. 				pChild->pos.row++;
  26. 				pChild->pos.g = Now->pos.g + 1;
  27. 				break;
  28. 			case Left:
  29. 				pChild->pos.col--;
  30. 				pChild->pos.g = Now->pos.g + 1;
  31. 				break;
  32. 			case Right:
  33. 				pChild->pos.col++;
  34. 				pChild->pos.g = Now->pos.g + 1;
  35. 				break;
  36. 			default:
  37. 				break;
  38. 			}
  39. 			//2.判断能不能走
  40. 			if (Astar.maze[pChild->pos.row][pChild->pos.col] == 0 || Astar.maze[pChild->pos.row][pChild->pos.col] == 8
  41. 				|| Astar.maze[pChild->pos.row][pChild->pos.col] == 2)	//如果是路则计算F
  42. 			{
  43. 				//标记走过
  44. 				Astar.maze[pChild->pos.row][pChild->pos.col] = 4;
  45. 				pChild->pos.h = getH(pChild->pos, Astar);//计算H
  46. 				pChild->pos.F = pChild->pos.g + pChild->pos.h;//计算F
  47.  
  48. 				//入树
  49. 				Now->child.push_back(pChild);
  50. 				pChild->parent = Now;
  51.  
  52. 				//存入数组
  53. 				open.push_back(pChild);
  54. 			}
  55. 			else {
  56. 				delete pChild;
  57. 			}
  58. 		}
  59. 		
  60. 		//3.找出数组最小的点，走上去
  61. 		//cout << open.size() << endl;
  62. 		itmin = open.begin();//假设第一个F最小	时间复杂度O(n)
  63. 		for (it = open.begin(); it != open.end(); it++)
  64. 		{
  65. 			itmin = ((*it)->pos.F <= (*itmin)->pos.F) ? it : itmin;	//细节 加上等于
  66. 		}
  67. 		//sort(open.begin(), open.end(),cmp);
  68. 		//itmin = open.begin();
  69. 		Now = *itmin;
  70. 		//标记走过
  71. 		//Astar.maze[Now->pos.row][Now->pos.col] = -1;
  72. 		show(Astar);
  73. 		//删除
  74. 		open.erase(itmin);
  75.  
  76. 		//4.判断是否找到终点
  77. 		if (Now->pos.row == Astar.E_row && Now->pos.col == Astar.E_col)
  78. 		{
  79. 			flag = 1;
  80. 			break;
  81. 		}
  82.  
  83. 		//5.如果为数组为空也退出
  84. 		if (0 == open.size()) break;
  85. 	}
  86.  
  87. 	//成功则打印
  88. 	if (flag)
  89. 	{
  90. 		cout << "success" << endl;
  91. 		while (Now)
  92. 		{
  93. 			cout << "(" << Now->pos.row << "," << Now->pos.col << ")";
  94. 			printf("(g:%d,h:%d,f:%d)\n", Now->pos.g, Now->pos.h, Now->pos.F);
  95. 			Astar.maze[Now->pos.row][Now->pos.col] = 3;
  96. 			Now = Now->parent;
  97. 		}
  98. 	}
  99. 	else
  100. 	{
  101. 		cout << "not found" << endl;
  102. 	}
  103.  
  104. 	while (1)
  105. 	{
  106. 		BeginBatchDraw();
  107.  
  108. 		show(Astar);
  109.  
  110. 		FlushBatchDraw();
  111. 	}//循环绘图防止BUG
  112. 	closegraph();
  113. }

四、总代码

  1. #include<iostream>
  2. #include<iomanip>
  3. #include<graphics.h>
  4. #include<time.h>
  5. #include<easyx.h>
  6. #include<algorithm>
  7. #include<vector>
  8. using namespace std;
  9.  
  10. //1为墙壁，0为路
  11. #define SIZE 10
  12.  
  13. bool flag = 0;
  14.  
  15. enum dirct {
  16. 	Up,
  17. 	Down,
  18. 	Left,
  19. 	Right,
  20. };
  21.  
  22. struct AStar {
  23. 	int M;						//M*M map
  24. 	int** maze;					//map迷宫
  25. 	//int* close;					//close表
  26. 	//int* open;					//open表
  27. 	int O_row;					//开始的行
  28. 	int O_col;					//开始的列	
  29. 	int E_row;					//终点行
  30. 	int E_col;					//终点列
  31. }Astar{ 0,NULL,1,1,0,0 };
  32.  
  33. struct position {
  34. 	int row, col;
  35. 	int g;						//路径代价 行走的步数
  36. 	int h;						//启发函数 曼哈顿距离
  37. 	int F = h + g;				//估价函数
  38. };
  39.  
  40. struct treeNode {	//close类似
  41. 	position pos;
  42. 	vector<treeNode*> child;
  43. 	treeNode* parent;
  44. };
  45.  
  46. treeNode* creatTreeNode(int row, int col);						//创建树节点
  47. int getH(position pos, AStar a);								//计算H
  48.  
  49. void Init_Maze(AStar& Astar);									//初始化迷宫
  50. void show(AStar& Astar);										//图像显示迷宫
  51. void creatMaze(AStar& Astar, int x_index, int y_index);			//随机创建迷宫
  52. void makeMaze(AStar& Astar);									//给创建的迷宫创建标识
  53. bool findneighbor(AStar& Astar, int x_index, int y_index);		//寻找邻居
  54. void MakeDifficult(AStar& Astar);								//改变地形，出现更多通路
  55. void ConsoleShow(AStar& Astar);									//控制台显示迷宫
  56.  
  57. ///*排序方式*/
  58. //bool cmp(treeNode* m1, treeNode* m2)
  59. //{
  60. //	return m1->pos.F < m2->pos.F;
  61. //}
  62.  
  63. int main()
  64. {
  65. 	treeNode* pRoot = NULL;	 //准备一棵树
  66. 	vector<treeNode*> open;  //准备一个数组
  67.  
  68. 	vector<treeNode*>::iterator it;	//迭代器
  69. 	vector<treeNode*>::iterator itmin;	//迭代器
  70.  
  71. 	Astar.M = 0;
  72. 	cout << "请输入迷宫是几乘几的" << endl;
  73. 	cin >> Astar.M;
  74. 	if (Astar.M % 2 == 0)//如果输入不为奇数变为奇数
  75. 		Astar.M++;
  76.  
  77. 	Astar.E_col = Astar.M;
  78. 	Astar.E_row = Astar.M;
  79.  
  80. 	pRoot = creatTreeNode(Astar.O_row, Astar.O_col); //起点入树
  81.  
  82. 	srand((unsigned)time(0));//随机播种
  83.  
  84. 	initgraph(((Astar.M + 2) * 2 + 1) * SIZE, (Astar.M + 2) * SIZE, SHOWCONSOLE);//打开绘图
  85.  
  86. 	Astar.maze = new int* [Astar.M + 2];//动态创建二维数组
  87. 	for (int i = 0; i < Astar.M + 2; i++)
  88. 		Astar.maze[i] = new int[Astar.M + 2];//每一行申请一个int空间的M+2列空间
  89.  
  90. 	Init_Maze(Astar);
  91. 	creatMaze(Astar, 1, 1);
  92. 	makeMaze(Astar);
  93. 	MakeDifficult(Astar);
  94. 	//show(Astar);
  95.  
  96. 	treeNode* Now = pRoot;
  97. 	pRoot->pos.F = Astar.M * Astar.M;
  98. 	open.push_back(pRoot);
  99. 	while (1)
  100. 	{
  101. 		//1.把当前能走的点找出来
  102. 		for (int i = 0; i < 4; i++)
  103. 		{
  104. 			treeNode* pChild = creatTreeNode(Now->pos.row, Now->pos.col);
  105. 			switch (i)
  106. 			{
  107. 			case Up:
  108. 				pChild->pos.row--;
  109. 				pChild->pos.g = Now->pos.g + 1;
  110. 				break;
  111. 			case Down:
  112. 				pChild->pos.row++;
  113. 				pChild->pos.g = Now->pos.g + 1;
  114. 				break;
  115. 			case Left:
  116. 				pChild->pos.col--;
  117. 				pChild->pos.g = Now->pos.g + 1;
  118. 				break;
  119. 			case Right:
  120. 				pChild->pos.col++;
  121. 				pChild->pos.g = Now->pos.g + 1;
  122. 				break;
  123. 			default:
  124. 				break;
  125. 			}
  126. 			//2.判断能不能走
  127. 			if (Astar.maze[pChild->pos.row][pChild->pos.col] == 0 || Astar.maze[pChild->pos.row][pChild->pos.col] == 8
  128. 				|| Astar.maze[pChild->pos.row][pChild->pos.col] == 2)	//如果是路则计算F
  129. 			{
  130. 				//标记走过
  131. 				Astar.maze[pChild->pos.row][pChild->pos.col] = 4;
  132. 				pChild->pos.h = getH(pChild->pos, Astar);//计算H
  133. 				pChild->pos.F = pChild->pos.g + pChild->pos.h;//计算F
  134.  
  135. 				//入树
  136. 				Now->child.push_back(pChild);
  137. 				pChild->parent = Now;
  138.  
  139. 				//存入数组
  140. 				open.push_back(pChild);
  141. 			}
  142. 			else {
  143. 				delete pChild;
  144. 			}
  145. 		}
  146. 		
  147. 		//3.找出数组最小的点，走上去
  148. 		//cout << open.size() << endl;
  149. 		itmin = open.begin();//假设第一个F最小	时间复杂度O(n)
  150. 		for (it = open.begin(); it != open.end(); it++)
  151. 		{
  152. 			itmin = ((*it)->pos.F <= (*itmin)->pos.F) ? it : itmin;	//细节 加上等于
  153. 		}
  154. 		//sort(open.begin(), open.end(),cmp);
  155. 		//itmin = open.begin();
  156. 		Now = *itmin;
  157. 		//标记走过
  158. 		//Astar.maze[Now->pos.row][Now->pos.col] = -1;
  159. 		show(Astar);
  160. 		//删除
  161. 		open.erase(itmin);
  162.  
  163. 		//4.判断是否找到终点
  164. 		if (Now->pos.row == Astar.E_row && Now->pos.col == Astar.E_col)
  165. 		{
  166. 			flag = 1;
  167. 			break;
  168. 		}
  169.  
  170. 		//5.如果为数组为空也退出
  171. 		if (0 == open.size()) break;
  172. 	}
  173.  
  174. 	//成功则打印
  175. 	if (flag)
  176. 	{
  177. 		cout << "success" << endl;
  178. 		while (Now)
  179. 		{
  180. 			cout << "(" << Now->pos.row << "," << Now->pos.col << ")";
  181. 			printf("(g:%d,h:%d,f:%d)\n", Now->pos.g, Now->pos.h, Now->pos.F);
  182. 			Astar.maze[Now->pos.row][Now->pos.col] = 3;
  183. 			Now = Now->parent;
  184. 		}
  185. 	}
  186. 	else
  187. 	{
  188. 		cout << "not found" << endl;
  189. 	}
  190.  
  191. 	while (1)
  192. 	{
  193. 		BeginBatchDraw();
  194.  
  195. 		show(Astar);
  196.  
  197. 		FlushBatchDraw();
  198. 	}//循环绘图防止BUG
  199. 	closegraph();
  200. }
  201.  
  202. //初始化迷宫
  203. void Init_Maze(AStar& Astar)
  204. {
  205. 	for (int i = 0; i < Astar.M + 2; i++)//动态创建迷宫
  206. 		for (int j = 0; j < Astar.M + 2; j++)
  207. 		{
  208. 			if (i == 0 || i == Astar.M + 1)//1为墙壁
  209. 				Astar.maze[i][j] = 1;
  210. 			if ((i % 2 == 1) && (j % 2 == 1))
  211. 				Astar.maze[i][j] = 0;
  212. 			else Astar.maze[i][j] = 1;
  213. 		}
  214. }
  215.  
  216. //图像显示迷宫
  217. //3为路，4为搜寻的路，1为墙，2为终点，8为开始
  218. void show(AStar& Astar)
  219. {
  220. 	IMAGE star, wall, ball ,ly;
  221. 	loadimage(&star, "./五角星.png", SIZE, SIZE);
  222. 	loadimage(&wall, "./墙.png", SIZE, SIZE);
  223. 	loadimage(&ball, "./球.png", SIZE, SIZE);
  224. 	loadimage(&ly, "./兰音.png", SIZE, SIZE);
  225. 	for (int i = 0; i < Astar.M + 2; i++)
  226. 	{
  227. 		for (int j = 0; j < Astar.M + 2; j++)
  228. 		{
  229. 			if (Astar.maze[i][j] == 1)
  230. 			{
  231. 				putimage((j + Astar.M + 2 + 1) * SIZE, (i)*SIZE, &wall);
  232. 				putimage(j * SIZE, i * SIZE, &wall);
  233. 			}
  234. 			else if (Astar.maze[i][j] == 4)
  235. 			{
  236. 				putimage((j + Astar.M + 2 + 1) * SIZE, (i)*SIZE, &ball);
  237. 			}
  238. 			else if (Astar.maze[i][j] == 3)
  239. 			{
  240. 				putimage(j * SIZE, (i)*SIZE, &ly);
  241. 			}
  242. 		}
  243. 	}
  244. 	putimage((Astar.M + 2 + 1 + 1) * SIZE, (SIZE), &star);
  245. 	putimage((Astar.M + Astar.M + 2 + 1) * SIZE, (Astar.M) * SIZE, &star);
  246. 	putimage(SIZE, SIZE, &star);
  247. 	putimage(Astar.M * SIZE, Astar.M * SIZE, &star);
  248. }
  249.  
  250. //寻找邻居
  251. bool findneighbor(AStar& Astar, int x_index, int y_index)
  252. {
  253. 	if ((x_index >= 3 && Astar.maze[x_index - 2][y_index] == 0) || (x_index <= Astar.M - 1 && Astar.maze[x_index + 2][y_index] == 0)
  254. 		|| (y_index >= 3 && Astar.maze[x_index][y_index - 2] == 0) || (y_index <= Astar.M - 1 && Astar.maze[x_index][y_index + 2] == 0))
  255. 		return 1;
  256. 	else
  257. 		return 0;
  258. }
  259.  
  260. //随机创建迷宫
  261. void creatMaze(AStar& Astar, int x_index, int y_index)
  262. {
  263. 	int pos, x, y, flag = 0;
  264. 	x = x_index;
  265. 	y = y_index;
  266.  
  267. 	while (1)
  268. 	{
  269. 		flag = 0;
  270. 		flag = findneighbor(Astar, x, y);
  271. 		if (!flag)
  272. 			return;
  273. 		else {
  274. 			Astar.maze[x_index][y_index] = 5;
  275. 			x = x_index;
  276. 			y = y_index;
  277. 			while (1)
  278. 			{
  279. 				pos = rand() % (4 - 1 + 1) + 1;
  280. 				if (pos == 1 && x_index >= 3 && Astar.maze[x_index - 2][y_index] == 0)//上
  281. 				{
  282. 					x_index -= 2;
  283. 				}
  284. 				else if (pos == 2 && x_index <= Astar.M - 1 && Astar.maze[x_index + 2][y_index] == 0)//下
  285. 				{
  286. 					x_index += 2;
  287. 				}
  288. 				else if (pos == 3 && y_index <= Astar.M - 1 && Astar.maze[x_index][y_index + 2] == 0)
  289. 				{
  290. 					y_index += 2;
  291. 				}
  292. 				else if (pos == 4 && y_index >= 3 && Astar.maze[x_index][y_index - 2] == 0)
  293. 				{
  294. 					y_index -= 2;
  295. 				}
  296. 				Astar.maze[(x + x_index) / 2][(y + y_index) / 2] = 5;
  297. 				Astar.maze[x_index][y_index] = 5;
  298.  
  299. 				//	showmaze(maze, M);
  300.  
  301. 				creatMaze(Astar, x_index, y_index);
  302. 				break;
  303. 			}
  304. 		}
  305. 	}
  306. }
  307.  
  308. //给创建的迷宫创建标识
  309. void makeMaze(AStar& Astar)
  310. {
  311. 	for (int i = 0; i < Astar.M + 2; i++)
  312. 		for (int j = 0; j < Astar.M + 2; j++)
  313. 		{
  314. 			if (Astar.maze[i][j] == 5)
  315. 			{
  316. 				Astar.maze[i][j] = 0;
  317. 			}
  318. 		}
  319. 	Astar.maze[1][1] = 8;
  320. 	Astar.maze[Astar.M][Astar.M] = 2;
  321. }
  322.  
  323. //改变地形，出现更多通路
  324. void MakeDifficult(AStar& Astar)
  325. {
  326. 	if (Astar.M > 5)
  327. 	{
  328. 		int half = (int)((0.4 * Astar.M) * (0.5 * Astar.M));
  329. 		int x_c, y_c = 0;
  330. 		for (int i = 0; i < half;)
  331. 		{
  332. 			x_c = rand() % (Astar.M - 1 + 1) + 1;
  333. 			y_c = rand() % (Astar.M - 1 + 1) + 1;
  334. 			if (Astar.maze[x_c][y_c] == 1)
  335. 			{
  336. 				Astar.maze[x_c][y_c] = 0;
  337. 				i++;
  338. 			}
  339. 		}
  340. 	}
  341. }
  342.  
  343. //计算H
  344. int getH(position pos, AStar a) {
  345. 	return (a.E_row - pos.row) + (a.E_col - pos.col);
  346. }
  347.  
  348. //创建树节点
  349. treeNode* creatTreeNode(int row, int col)
  350. {
  351. 	treeNode* pNew = new treeNode;//开内存
  352. 	memset(pNew, 0, sizeof(treeNode)); //全部赋值为0
  353. 	pNew->pos.col = col;
  354. 	pNew->pos.row = row;
  355. 	return pNew;
  356. }
  357.  
  358. //控制台显示迷宫
  359. void ConsoleShow(AStar& Astar)
  360. {
  361. 	cout << endl << "3为走出迷宫的路,1为墙壁，2为出口" << endl;;
  362. 	for (int i = 0; i < Astar.M + 2; i++)
  363. 	{
  364. 		for (int j = 0; j < Astar.M + 2; j++)
  365. 		{
  366. 			cout << setw(3) << Astar.maze[i][j];
  367. 		}
  368. 		cout << endl;
  369. 	}
  370. }

五、总结

        这份代码还有一些莫名其妙的bug，但已经改不动了。希望可以帮助到大家。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/526219
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号