首页
论坛
课程
招聘
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝

[作品提交]人工智能走高级迷宫

2008-6-27 19:41 15878

[作品提交]人工智能走高级迷宫

2008-6-27 19:41
15878
这是我参加gpct程序大赛2等奖的作品,可以用来走比较高级的迷宫。
程序用c#写成,vs2005编译。
这种迷宫不是普通的迷宫,而是带有复杂元素的迷宫,如门,传送点等等。

迷宫分7个等级:

1  "迷宫有多条通路,这个等级主要是用来检测算法是否具备走出迷宫的能力"

2  "迷宫有较少的岔路,这个等级主要是用来检测算法是否具备探路的能力"

3  "迷宫有最多的分支,这个等级主要是用来检测算法是否具备回溯的能力"

4  "拥有传送点的迷宫,需要算法能够记住这些传送点并且能够分析这些传送点","传送点类型为:会被传送至地图上的某个固定位置"

5  考察算法是否能够记忆并分析门和开关的能力,初始状态为关,"开关的类型为:1
将开着的门关闭,将关闭的门打开,如此反复"  

6  比4和5更复杂  初始状态为关  "开关的类型为:1
将开着的门关闭,将关闭的门打开,如此反复"  "传送点类型为:1
会被传送至地图上的某个固定位置"

由于第七级需要两个算法配合,我就没放上dll了。(就是说附件里只能走前六级)
另外我的dll里面有三个探险家,分别是“superman!_v6”,“woman_v6”,“只会左和上的算法”,大家测试的时候用双击superman!_v6
就行了,另两个是多出来没用的,可以不必理会。
客户端有三中速度选择,要看清怎末走的话用slow那个速度(就是三角按钮的下拉框里)
以下是这次比赛题目的介绍:

编写一个探索并寻找二维迷宫出口的人工智能算法(以下简称算法),这个算法会帮助那些身陷迷宫的探险家走出迷宫。
算法能够获取的信息有
  迷宫的大小和出口的坐标。
  探险家当前的坐标以及周围一个格子的情况。
  在同一个迷宫中其他探险家的喊话内容。

算法能够控制的内容有:
  控制当前探险家向前走一格,向后走一格,向左走一格,向右走一格或者停留在原地。
  控制当前的探险家在迷宫中喊话。
要求:
1、  迷宫是随机生成的,算法需要能够动态适应不同的迷宫。
2、  迷宫中会有路、墙之外的其他元素,比如:门和开关。因此需要算法能够在遇到这些元素的时候自动判断,使算法能够走出迷宫。
3、  根据迷宫的元素类型,迷宫也分为不同的类型,不同类型的迷宫有着截然不同的难度,尽可能的让你的算法能够识别和解决更多的迷宫类型。
4、  算法可以控制探险家说话,以便能够和作品中其他的算法交流,以便能够更快走出迷宫。
迷宫介绍
  算法所需要解决的迷宫为一个矩形迷宫(Width与Height均可以在算法中获得)。迷宫左上角的坐标为(0,0),右下角的坐标为(Width-1,Height-1),并且迷宫只有一个出口,这个出口的坐标也可以在算法中获得,算法将探险家移动到迷宫出口坐标既算成功。
  每一个迷宫坐标都会有一种迷宫元素,最常见的两种元素就是:墙(Wall)和路(Path),很明显,如果一个探险家的左边是一个墙,那么这个探险家如果向左移动,是不会成功的。相反,如果这个探险家的右边是一个路,那么这个探险家则可以向右移动。但也有一些元素需要尝试移动一次才能知道是否可以通行,比如一个门(Door)。每当探险家成功移动之后,他所看到的四周都会根据他所移动到的位置发生改变,算法应该及时记录下这些变化,以便分析和寻找出路。

探险家介绍
由于算法不能直接获得迷宫的信息,迷宫的信息必须由探险家四处探索获得,因此算法需要通过控制探险家来探索迷宫并最终找到出口,具体就是算法控制探险家进行前后左右的移动(每次只能移动一格),以便来获取探险家四周的迷宫信息。
除此之外,探险家还可以通过说话引起附近的算法的注意,以实现两个算法之间的相互协作与配合。

算法介绍
迷宫算法最终目的就是将探险家移动到迷宫的出口位置(既IExplorer对象的Current属性值为PositionInfo.Exit),并且退出算法。
 
 迷宫中的元素
入口(Entrance)
这个元素说明这是一个入口,也是每个探险家的初始位置。可以通行。
出口(Exit)
这个元素说明这是一个出口,将探险家成功移动到这个位置并且算法返回true值既算完成。可以通行。
路(Path)
这个元素说明这个位置是路,可以通行。
墙(Wall)
这个元素说明这个位置是墙,不允许通行,如果向这里移动将不会成功。
门(Door)
这个元素说明这是一个门,门有两种状态,既开和关,门处于开的状态时可以通行,门处于关闭状态时不允许通行,门不会自己开关,门状态的改变是靠迷宫中的开关元素来控制。门的开关状态必须试移动一次才能知道,如果试移动成功,则说明门是开的,如果试移动失败,则说明门是关着的。
开关(Trigger)
这个元素说明这是一个开关,可以通行,每当探险家移动(Move)到或者停留(Stay)在这个开关上的时候,与这个开关相连接的门的状态会发生一次转变。转变的类型有:
1.  将开着的门关闭,将关闭的门打开,如此反复
2.  始终将门关闭
3.  始终将门打开
注释:不但一个开关可以连接不止一扇门,而且一扇门可以被不同的开关控制。最关键的是,迷宫不会告诉你这个开关连着哪扇门,或者告诉你这扇门有哪几个开关。
传送点(Transport)
这个元素说明这个位置一个传送点,如果探险家移动到这里,可能会被传送到一个迷宫中的一个固定位置,也有可能被传送到一个随机的位置。但肯定都是可以移动的位置。
传送点类型有:
1.  传送到一个固定坐标
2.  传送到之前的某个时刻所处的位置。
3.  传送到入口
4.  传送到出口

下面是一副地图,可以看出地图虽然很小,但加上门,开关等元素后还是比较复杂的。更复杂的是算法不能得到地图全貌,只能知道自己前后左右四个方向的信息,如 是门还是墙。
也有是说:有可能某开关不控制任何门,也有可能某门不能被任何开关所控制。但我所给出我参赛时候的地图是那种怎末走都能走出去的地图,不会出现死胡同的。

图中绿色的带箭头的线表示灰色的开关所能的打开红色的门。算法要经过若干个门后才能进去左上角的终点。




如下是算法在走迷宫,如开门等活动(浅红色代表算法所走过的路径。算法本身也为红色)



HWS计划·2020安全精英夏令营来了!我们在华为松山湖欧洲小镇等你

上传的附件:
最新回复 (44)
雪    币: 240
活跃值: 活跃值 (10)
能力值: ( LV10,RANK:170 )
在线值:
发帖
回帖
粉丝
三根火柴 活跃值 4 2008-6-27 20:26
2
0
看似很深奥啊,我也沙发一会
雪    币: 126
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
niuhacker 活跃值 2008-6-27 20:40
3
0
顶一个,这学期人工智能学的头都大了
雪    币: 210
活跃值: 活跃值 (10)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
usufu 活跃值 2 2008-6-27 20:53
4
0
牛人。。。。
雪    币: 1613
活跃值: 活跃值 (15)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
北极星2003 活跃值 25 2008-6-27 20:59
5
0
好文。
不过题目看的有点糊涂:
注释:不但一个开关可以连接不止一扇门,而且一扇门可以被不同的开关控制。最关键的是,迷宫不会告诉你这个开关连着哪扇门,或者告诉你这扇门有哪几个开关。


这是不是就意味着,有可能某开关不控制任何门,也有可能某门不能被任何开关所控制。在这种情况下,想要走过迷宫,需要考虑最坏情况即:任何门都永远关闭的情况,那么此时这个问题与普通迷宫无异同。

我继续啃题目~~

另外MazeClient.exe是个快捷方式,这个???
雪    币: 504
活跃值: 活跃值 (19)
能力值: (RANK:570 )
在线值:
发帖
回帖
粉丝
笨笨雄 活跃值 14 2008-6-27 22:40
6
0
很好,学习一下
雪    币: 5535
能力值: (RANK:1060 )
在线值:
发帖
回帖
粉丝
forgot 活跃值 26 2008-6-27 22:43
7
0
高级crackme要出现了
雪    币: 207
活跃值: 活跃值 (15)
能力值: ( LV9,RANK:290 )
在线值:
发帖
回帖
粉丝
sislcb 活跃值 7 2008-6-27 22:49
8
0
厉害,支持啊
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-6-27 23:03
9
0
啊哈……不好意思啊,我上传的时候看错了,把快捷方式发上来了,呵呵,让大家失望了,现在更正!!
另外北极星大哥说的没错,有可能某开关不控制任何门,也有可能某门不能被任何开关所控制。但我给的迷宫地图是这样一种地图:即无论你怎末走,都能走出这个迷宫。这样就不用担心会走到死胡同里面了。
还有,我给的迷宫客户端还可以自己画地图的,大家可以自行绘制地图,可以当成一个游戏来玩,很有意思的
雪    币: 79
活跃值: 活跃值 (31)
能力值: ( LV6,RANK:80 )
在线值:
发帖
回帖
粉丝
frozenrain 活跃值 2008-6-27 23:44
10
0
牛,签名留念!
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
pack三九 活跃值 2008-6-28 06:47
11
0
这个要学习了,可能涉及的算法很复杂,下载看看。
雪    币: 212
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
xxyyzasabc 活跃值 2008-6-28 12:55
12
0
牛人 膜拜......
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
roofers 活跃值 2008-6-28 12:59
13
0
厉害不是一般人能掌握的了的。。。。。。拍手
雪    币: 190
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
cscncllf 活跃值 2008-6-28 13:04
14
0
牛人。。。。这个要学习
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-6-28 18:15
15
0
呵呵,不知道大家有谁运行了程序?看一看怎末走迷宫的,还可以自己画迷宫,让算法走,绝对很刺激的
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
漂魂 活跃值 2008-6-28 22:20
16
0
牛B,学习!!!
雪    币: 215
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
萝卜 活跃值 1 2008-6-29 18:35
17
0
也学习一下人工智能
雪    币: 212
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
huangflong 活跃值 2008-7-1 20:50
18
0
學習、學習~~~
雪    币: 241
活跃值: 活跃值 (10)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
xiaojiam 活跃值 2 2008-7-1 22:53
19
0
果然是个牛人!顶了学习下!
雪    币: 564
活跃值: 活跃值 (12)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
lixupeng 活跃值 2008-7-1 23:49
20
0
好东西值得研究
雪    币: 2224
活跃值: 活跃值 (60)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
ldljlzw 活跃值 2008-7-2 10:36
21
0
怎么都是E文的,有点看不懂!
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
pupie 活跃值 2008-7-2 12:22
22
0
很好的东西,下载下来看看
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-3 17:46
23
0
里面有e文????
那是源代码吧……我的文档都是汉语写的
雪    币: 101
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
perspect 活跃值 2008-7-3 20:44
24
0
跑了几遍啊
  强大~
雪    币: 101
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
perspect 活跃值 2008-7-3 20:45
25
0
有时后会有异常出现,程序就直接关掉了,是配置的原因还是?
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zywen 活跃值 2008-7-4 19:21
26
0
喔,对一个新手来说太深了,不过写的很好~!支持,这个东西我看在机器人大赛上可以用这种思路~!
雪    币: 234
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
梦魇颖雨 活跃值 2008-7-4 22:49
27
0
谢谢 分享 下来一定好好的看卡
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-6 19:04
28
0
有异常?
不会吧……可能我提交的版本是以前那个没修补过的、每次跑完一张地图都要重启的那个。这样吧,你在Thinking函数开头把我前面声明的那几个动态数组用clean()清除一下。当时这个缺陷害的大赛的组委会不得不手工验证我的程序,气的想k我,呵呵
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-6 19:09
29
0
另外大家可以用那个客户端画出更多的地图来,可以有门有开关,更可以有传输点(我这个算法比较怕开关,但不怎末怕传输点),欢迎大家和我交流是否更先进的算法。我这个算法感觉地图大了效率就不高了。也欢迎大家把画出来较难的地图给我跑跑,让我进一步改进。
雪    币: 213
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
ganmao 活跃值 2008-7-9 10:30
30
0
还得准备运行环境啊?我装的是VS2003,结果你的又不是release版本。。。
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-10 19:21
31
0
所有的代码都在里面了,你新建个项目再重新编译吧。
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-8-5 16:31
32
0
哎哎,没人玩这个有趣的游戏了,其实很想和大家交流跑地图的心得
雪    币: 1034
活跃值: 活跃值 (21)
能力值: ( LV12,RANK:750 )
在线值:
发帖
回帖
粉丝
boywhp 活跃值 12 2008-8-5 17:19
33
0
有意思,算法!看看
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hackyong 活跃值 2008-8-5 22:36
34
0
看不明白,但是还要研究。
雪    币: 2362
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zapline 活跃值 2008-8-6 09:00
35
0
呵呵···膜拜!
雪    币: 237
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
雲飛揚 活跃值 2008-8-9 09:47
36
0
下载学习了~~~
雪    币: 250
活跃值: 活跃值 (20)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-12-30 22:38
37
0
偶然路过自己这个东东,怀恋啊
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
孤风残影 活跃值 2008-12-31 15:45
38
0
看的头都晕了 汗
雪    币: 6510
活跃值: 活跃值 (73)
能力值: ( LV7,RANK:102 )
在线值:
发帖
回帖
粉丝
SnowFox 活跃值 2008-12-31 22:40
39
0
下载了, 楼主大牛
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Jakin 活跃值 2009-1-2 01:51
40
0
爆汗,太牛了,光题目就看晕了
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
xray 活跃值 2009-1-6 21:36
41
0
人工智能的算法很复杂,下载看看。
雪    币: 3921
活跃值: 活跃值 (45)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
scientist 活跃值 2009-1-7 14:14
42
0
[QUOTE=;]...[/QUOTE]
Get a copy to study it.  Hope I can understand the tricks inside.
雪    币: 203
活跃值: 活跃值 (10)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
SafeNdis 活跃值 3 2009-1-15 02:39
43
0
人工智能我有热情!!!
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
shen申 活跃值 2009-4-11 22:06
44
0
啊!这个看起来好复杂哦!膜拜下啊!楼主真强悍!
雪    币: 924
活跃值: 活跃值 (12)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
lynxtang 活跃值 2009-4-11 23:27
45
0
强悍,学习了,谢谢楼主的分享精神
游客
登录 | 注册 方可回帖
返回