maze.cpp

我们数据结构课的课程设计

///////////////////////////////////////////////////////////////
// 文件名：maze.cpp
// 作者：施自成，韩小龙，何键，陈文豪，陈卓
// 
// A*算法流程
// A*是启发试搜索加动态规划。
// 具体实现依靠两个队列Open队列和Close队列。从一点访问四周
// 相邻的格子如果可以移动且当前移动为起点到哪个格子的历史最
// 佳方法则把那个格子按照估价值从小到大插入Open队列里面，几
// 个方向试探结素后取出估价值最小的节点放入Close再从这里开
// 始试探几个相邻的方向同样放入Open队列里面，放入Open的条件
// 是:
// 1.这步在地图上面是可以移动的，
// 2.这步所在节点在Open里面并不存在，
// 3.从起点到这步的实际距离比这点的历史最小距离
//  还短满足这三个条件就把节点放入Open队列。
///////////////////////////////////////////////////////////////

// stdafx.h 包含一些常用的头文件，用于加快编译速度
// 
#include "stdafx.h"
#include "glval.h" 

char matrix[100][100];
char BufferMatrix[100][100];
list<node> open; // 链表，用来保存未扩展的节点
stack<node> close; // 栈，用来保存已扩展的节点
list<node> path; // 链表，用于保存找到的路径
list<node>::iterator iter; // 迭代器，用来对链表进行访问的指针 
// STL常用操作：
// 对象名.empty() // 判断链表是否为空
// 对象名.push(要保存的值)  // 入栈
// 对象名.pop() // 出栈
// 对象名.push_front(要保存的值), 对象名.push_back(要保存的值)// 保存到最前面或最后面
// 对象名.pop_front(), 对象名.pop_back()// 删除最前面或最后面的元素
// iter = 对象名.begin()  // 使iter指向数据结构中的第一个元素
// iter != 对象名.end()  // 比较 iter和数据结构中的最后一个元素

/////////////////////////////////////////////////////////////
// 根据matrix找到最短路径，并将结果保存在path链表中
// 返回 false 表示走不出
// 返回 true 表示已经找到路径
bool findpath()
{
    int i,j; 
	// 在迷宫的四周围填充1
	for (i=0; i<maze_width+2; i++)
	{
		BufferMatrix[0][i] = '1';  
		BufferMatrix[i][maze_width+1] = '1';  
	}
	for (i=0; i<maze_height+2; i++)
	{
		BufferMatrix[i][0] = '1';  
		BufferMatrix[maze_height+1][i] = '1';  
	}
	// 保存迷宫 
	for (i=1; i<maze_height+1; i++)
	{
		for (j=1; j<maze_width+1; j++)
		{
			BufferMatrix[i][j] =  matrix[i-1][j-1];  
		}
	}

	// 用来记录当前节点是否有扩展节点
	bool sign; 

	// tmp用来保存当前节点
	// tmp1用来保存扩展节点
	node tmp, tmp1;  
	tmp.x = 1; 
	tmp.y = 1; 
	tmp.gn = 1; 
	// ★ f(n) = g(n) + h(n) 
	// 其中f(n)为估价函数，表示从起点到终点的路径总长度 
	// ★ g(n)表示从起点到当前节点所走过的路 
	// ★ h(n)表示从当前节点到终点的最短路径 
	int hn = (maze_width-tmp.x)>(maze_height-tmp.y)?(maze_width-tmp.x):(maze_height-tmp.y); 
	tmp.fn = tmp.gn +  hn; 
	// 如果入口堵住，则走不出 
	if (BufferMatrix[1][1] != '0') 
	{
		return false; 
	} 
	// 保存进链表
	open.push_back(tmp); 
	while (!open.empty()) 
	{ 
		sign = false; 
		// 根据fn对open表进行排序
		open.sort(); 
		// 取链表中最后一个元素 
		// 即，fn最小的元素 
		tmp = open.back(); 
		open.pop_back(); 
		close.push(tmp); 
		// 找到出口
		if ((tmp.x == maze_width) && (tmp.y == maze_height))  
			break;
		// 加入8个方向的扩展节点 
		tmp.gn++; 
		// 向右走 
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y][tmp1.x+1] == '0') 
		{ 
			sign = true; 
			// 走过的地方置1
			BufferMatrix[tmp1.y][tmp1.x+1] = '1'; 
			tmp1.x++; 
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn; 
			open.push_back(tmp1); 
		} 
		// 向右下方走 
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y+1][tmp1.x+1] == '0')
		{
			sign = true; 
			BufferMatrix[tmp1.y+1][tmp1.x+1] = '1'; 
			tmp1.x++; 
			tmp1.y++; 
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn;  
			open.push_back(tmp1); 
		}
		// 向下走 
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y+1][tmp1.x] == '0')
		{
			sign = true; 
			BufferMatrix[tmp1.y+1][tmp1.x] = '1'; 
			tmp1.y++;
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn; 
			open.push_back(tmp1); 
		}
		// 向右上方走
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y-1][tmp1.x+1] == '0')
		{
			sign = true; 
			BufferMatrix[tmp1.y-1][tmp1.x+1] = '1'; 
			tmp1.x++; 
			tmp1.y--; 
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn; 
			open.push_back(tmp1); 
		}
		// 向左下方走
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y+1][tmp1.x-1] == '0')
		{
			sign = true; 
			BufferMatrix[tmp1.y+1][tmp1.x-1] = '1'; 
			tmp1.y++; 
			tmp1.x--; 
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn; 
			open.push_back(tmp1); 
		}
		// 向左边走
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y][tmp1.x-1] == '0')
		{
			sign = true; 
			BufferMatrix[tmp1.y][tmp1.x-1] = '1'; 
			tmp1.x--; 
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn; 
			open.push_back(tmp1); 
		}
		// 向左上方走
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y-1][tmp1.x-1] == '0')
		{
			sign = true; 
			BufferMatrix[tmp1.y-1][tmp1.x-1] = '1'; 
			tmp1.x--; 
			tmp1.y--; 
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn; 
			open.push_back(tmp1); 
		}
		// 向上走
		tmp1 = tmp; 
		if (BufferMatrix[tmp1.y-1][tmp1.x] == '0')
		{
			sign = true; 
			BufferMatrix[tmp1.y-1][tmp1.x] = '1'; 
			tmp1.y--; 
			hn = (maze_width-tmp1.x)>(maze_height-tmp1.y)?(maze_width-tmp1.x):(maze_height-tmp1.y); 
			tmp1.fn = tmp1.gn + hn; 
			open.push_back(tmp1); 
		}
		// 无路可走
		if (sign == false)
		{
			close.pop(); 
		}
	}
	if (open.empty())
	{
		return false; 
	}
	else
	{
		// 从出口回溯，找到路径
		tmp = close.top(); 
		close.pop(); 
		while (!close.empty())
		{
			tmp1 = close.top(); 
			close.pop(); 
			// 比较tmp1节点是不是tmp的前一个节点
			// 是前一个节点的条件是：
			// 两者的横纵坐标差不超过1，
			// tmp的gn即步数，等于tmp1的gn+1
			if (abs(tmp.x - tmp1.x) <= 1 &&
				abs(tmp.y - tmp1.y) <= 1 &&
				(tmp.gn == (tmp1.gn + 1)))
			{
				path.push_front(tmp); 
				tmp = tmp1; 
			}
		}
		path.push_front(tmp); 
	}
	open.clear(); 

	return true;
}