文档章节

C++写的一个类似走迷宫算法

648789030
 648789030
发布于 2016/08/15 15:26
字数 1968
阅读 82
收藏 1

    一次和同事讨论如何在很多有效点中找到一条路径可以从指定有效点,走到方格最下面的点。此处介绍一下何为有效点,在一个有很多小方格组成的大方格中,每个小方格都有一个特有的属性,1表示白色,0表示黑色。黑色的小方格表示有效点,白色表示无效点。我们的目标就是从从指定位置的黑方格开始寻找一条路径,路径由黑方格组成,即有效点组成,直到到达大方格最下面的有效点。

    我们最初的讨论算法思想是最基本的办法,每个点都有8个位置可走(左,右,上,下,左上,右上,左下,右下,其中有一个方向是到达该点的方向,不做计算,所以实际上是7个位置可走),其中有一个路径可走的判定条件,即只能走8个位置点中的有效点。首先,给八个点增加一个优先级属性,如果同时存在多个可走的方向,则最先走优先级最高的点。依次找点,直到找到出口,如果发现已无路可走,则向上回溯,查找上一个节点是否有其他的路径可走,依次类推,直到找到可走的路径。基本上的路径寻找就是:寻找下一个节点,如果有,则继续寻找下一个节点,如果没有,则退回当前点为父节点,寻找其他没有走的子节点,如果所有的子节点都走完了,则继续寻找该节点的父节点,依次查找,知道查遍所有的点,如果当前点没有父节点,并且没有可走的子节点,则判定失败。

    此方法的好处是逻辑比较简单,但是计算量很大,代码量也很大,并且还要先去建立树,设置优先级,比较繁杂,实现起来不太高效。有没有可能不用回溯就可以完成呢,即不走回头路呢,一次性的找到可能的出路呢?答案是肯定的,通过网上搜索关键词“走迷宫算法”,终于找到了一个可以解决这个问题的算法,接下来我来分析一个实现起来比较简单的算法。

    从一个点出发,寻找8个方向的可能的路径,每个点都同时出发,将所有离初始点距离相等的点组成兄弟节点,依次遍历这些兄弟节点,再次寻找这些兄弟节点的下一个节点,判断是否满足特定的退出条件,直到找到一个出口。原始的算法思想是:要保证走的路最短,前进过程中到达每个点所走的步数都是最少的.怎样达成这个条件呢.两点,第一,要多条路同时试着走,不能一条路走了不通再返回走别的路;第二,走到一个点,这个点就被占用了,不能再通过别的路走到这个点了.

我们首先设计一个Path类,首先增加一个step,表示到这一点时一共走了几步.还有增加两个指针,一个指针把一条路上的所走过的点连接起来,另一个指针把花费步数相同的所有点连接起来,即将兄弟节点都连接起来,这样一来就可以同时走好多条路了.px,py表示点的坐标,flag表示当前点的状态,findDes表示当前点和父节点的关系。

    int px;
	int py;
	int flag;    //0:不通  1:通   2:走过该点
	Path *fp;   //父指针,这是以后找路劲用的,只输出步数的话它就没什么用
	Path *bp;   //兄弟指针,通过它连在一起的点所花费的步数都相同
	int step;    //表示来到这里花了多少步
	string findDes;

 接下来,就要处理当前节点和子节点的关系,及兄弟节点的子节点和当前节点的关系。首先,我们设置当前节点的子节点为下一个执行的节点,然后将其他的节点与该下一个执行节点通过兄弟指针连接,可以保证通过该节点找到他的兄弟节点。

//设置当前节点的子节点,及该子节点的兄弟节点
void Path::AddChildBroNode(Path* pCur, Path* pBr,string findDes)
{
	this->findDes = findDes;
	this->step = pCur->step + 1;
	this->fp = pCur;
	this->flag = 2;
	//如果不相等,则已经有兄弟节点了,将之前的兄弟节点组合一个链表
	//如果相等,则说明该节点为当前节点的第一个字节点
	if (pBr->bp != pCur)
	{
		this->bp = pBr->bp;
	}
	
	pBr->bp = this;
}

最后,我们需要执行的真正的算法过程了。首先我们先遍历一下当前节点的所有下一个节点,保存这些节点的相关信息,包括确定下一个节点和兄弟节点的连接。

if (curx > 0 && ce[cury][curx - 1].flag == 0)  //向左查找
		{
			ce[cury][curx - 1].AddChildBroNode(pCurr, pBr,"L");			
		}

		if (curx>0&& cury < (iLm - 1) && ce[cury + 1][curx - 1].flag == 0)    //左下查找
		{
			ce[cury + 1][curx - 1].AddChildBroNode(pCurr, pBr,"LD");
		}

		if (curx < (iRm - 1) && ce[cury][curx + 1].flag == 0)  //向右查找
		{
			ce[cury][curx + 1].AddChildBroNode(pCurr, pBr,"R");		
		}

		if (curx < (iRm - 1)&& cury < (iLm - 1) && ce[cury + 1][curx + 1].flag == 0)  //右下查找
		{
			ce[cury + 1][curx + 1].AddChildBroNode(pCurr, pBr,"RD");
		}

		if (cury > 0 && ce[cury - 1][curx].flag == 0)   //向上查找
			ce[cury - 1][curx].AddChildBroNode(pCurr, pBr,"U");
		

		if (cury > 0 && curx < (iRm - 1) && ce[cury - 1][curx + 1].flag == 0)  //右上角
			ce[cury - 1][curx + 1].AddChildBroNode(pCurr, pBr,"RU");

		if (curx > 0 && cury > 0&& ce[cury - 1][curx - 1].flag == 0)   //左上角()
			ce[cury - 1][curx - 1].AddChildBroNode(pCurr, pBr,"LU");

		if (cury < (iLm - 1) && ce[cury + 1][curx].flag == 0)   //向下查找
		{
			ce[cury + 1][curx].AddChildBroNode(pCurr, pBr,"D");
		}

现在已经将当前节点的所有子节点找到并且相连为兄弟节点。最后一步就是遍历所有的兄弟节点的下一个节点,使其相连,并且确定下一个节点。

//遍历当前指针的所有兄弟
		if (pCurr->bp)
		{
			pCurr = pCurr->bp;
			curx = pCurr->px;
			cury = pCurr->py;
		}
		else if (pBr->fp == pBr->bp)     //从长兄开始,如果兄弟都没有子节点,则判定已经没有出路了
		{
			cout << "无路可逃了,重新规划路线" << endl;
			break;
		}
		else if (pCurr != pBr->bp)  //当前节点不是兄弟节点,则查找子节点
		{
			pCurr = pBr->bp;		
			curx = pCurr->px;
			cury = pCurr->py;
			pBr->fp = pCurr;
		}
		else        //当前节点为叶子节点了,则退出
		{
			cout << "无法走出迷宫,请检查数值是否正确" << endl;
			break;
		}

此处需要指出的是,当前的节点有两个退出条件,一个是当前节点没有子节点,二是当前节点和兄弟节点都没有子节点,此时,可退出程序执行,此路是死路了。

ok,到目前为止,我们的迷宫寻路算法就出来了,我们也要转变一种思维,就是人为和机器为的的区别,如果是人为的话,肯定一次只能找一条路,不可能同时找很多条路,所以拿到问题先要去分析一下,不是盲目的先去实践,这样只会更多的浪费实践。机器的好处时,比人脑的执行速度快,但最基本的思想却是出自人脑,所以,尽可能的多去尝试几种不同的解决方案,或许就能节省很多的时间和功夫,也能是自己成长的更快。

最后附上代码:

http://www.oschina.net/code/snippet_2609705_58605

© 著作权归作者所有

共有 人打赏支持
648789030
粉丝 2
博文 16
码字总数 11678
作品 0
广州
程序员
私信 提问
那些书之《我的第一本C++书》

我的博客 清明放了三天假,上了三天自习,把《我的第一本C++书》看完了 虽然书名是第一本书,其实我觉得应该是第二,或者第三本书,如果没有一点基础来看这本书,肯定会云里雾里。放假前去的...

Geek_Hao
2012/04/04
0
0
这种情况到底该不该走,各位大神给点意见

本人是做c#的,9月份选了一家公司,做了大半个月想走,与期望差距太大了。 情况是这样的:公司是做监控软件,软件包括服务端和客户端,服务端非常复杂,用c++和java做的,十几个东西;客户端...

灰太狼它哥
2013/09/30
646
5
看完这 7 条,模拟 C++ 新功能只是一个小目标!

但是,即使你无法使用这些功能,也不一定要放弃它们的好处。至少不用放弃全部。 有一些方法可以使用代码中新功能的思路,更准确地传达你的意图。 当然,这些方法肯定不如使用新版本C++本身的...

CSDN资讯
2018/09/08
0
0
7-C++远征之封装篇[下]-学习笔记

C++远征之封装篇(下) c++封装概述 下半篇依然围绕类 & 对象进行展开 将原本学过的简单元素融合成复杂的新知识点。 对象 + 数据成员 = 对象成员(对象作为数据成员) 对象 + 数组 = 对象数组(...

天涯明月笙
2018/07/21
0
0
牛逼的C/C++程序员是如何练成的?

这个题目的噱头太大,要真的写起来, 足够写一本书了。 牛耳人分享一些经验,希望能让初学的小伙伴少走弯路。 每个人的情况不一样,所以下面的描述可能并不适合每一个看到这篇文章的人。 一、...

weixin_42743471
2018/12/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spark集群安装方式2

环境: jdk1.8、hadoop-2.7、spark-1.6、三台centos7(如下List-1所示) List-1 如下30上部署master;31上部署worker1;32上部署worker2 192.168.33.30 master192.168.33.31 worker1192.168.......

克虏伯
30分钟前
2
0
java File常用的方法

import java.io.File; public class a_22 { public static void main(String[] args) {File f= new File("D:\\tianya\\2019.3.14\\html");System.out.println(f.isDirectory());Syste......

南桥北木
38分钟前
1
0
equals()的重写规则

自反性。对于任何非null的引用值x,x.equals(x)应返回true。 对称性。对于任何非null的引用值x与y,当且仅当:y.equals(x)返回true时,x.equals(y)才返回true。 传递性。对于任何非null的引用...

无精疯
今天
2
0
Go基础系列:双层channel用法示例

双层通道的解释见Go的双层通道 以下是一个双层通道的使用示例。注意下面的示例中使用了"信号通道"(Signal channel),但这里的信号通道是多余的,仅仅只是为了介绍。 信号通道不用来传递数据,...

echojson
今天
2
0
PHP文件上传error的错误类型

PHP文件上传error的错误类型 - $_FILES['file']['error'] 有以下几种类型 1、UPLOAD_ERR_OK 其值为 0,没有错误发生,文件上传成功。 2、UPLOAD_ERR_INI_SIZE 其值为 1,上传的文件超过了 ph......

小良下山化了个缘
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部