-
-
[作品提交]人工智能走高级迷宫
-
发表于: 2008-6-27 19:41
-
这是我参加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. 传送到出口
下面是一副地图，可以看出地图虽然很小，但加上门，开关等元素后还是比较复杂的。更复杂的是算法不能得到地图全貌，只能知道自己前后左右四个方向的信息，如 是门还是墙。
也有是说：有可能某开关不控制任何门，也有可能某门不能被任何开关所控制。但我所给出我参赛时候的地图是那种怎末走都能走出去的地图，不会出现死胡同的。
图中绿色的带箭头的线表示灰色的开关所能的打开红色的门。算法要经过若干个门后才能进去左上角的终点。
如下是算法在走迷宫，如开门等活动（浅红色代表算法所走过的路径。算法本身也为红色）
程序用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. 传送到出口
下面是一副地图，可以看出地图虽然很小，但加上门，开关等元素后还是比较复杂的。更复杂的是算法不能得到地图全貌，只能知道自己前后左右四个方向的信息，如 是门还是墙。
也有是说：有可能某开关不控制任何门，也有可能某门不能被任何开关所控制。但我所给出我参赛时候的地图是那种怎末走都能走出去的地图，不会出现死胡同的。
图中绿色的带箭头的线表示灰色的开关所能的打开红色的门。算法要经过若干个门后才能进去左上角的终点。
如下是算法在走迷宫，如开门等活动（浅红色代表算法所走过的路径。算法本身也为红色）
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
看似很深奥啊,我也沙发一会
|
|
|
|
|
|
|
|
|
好文。
不过题目看的有点糊涂： 注释：不但一个开关可以连接不止一扇门，而且一扇门可以被不同的开关控制。最关键的是，迷宫不会告诉你这个开关连着哪扇门，或者告诉你这扇门有哪几个开关。 这是不是就意味着，有可能某开关不控制任何门，也有可能某门不能被任何开关所控制。在这种情况下，想要走过迷宫，需要考虑最坏情况即：任何门都永远关闭的情况，那么此时这个问题与普通迷宫无异同。 我继续啃题目~~  另外MazeClient.exe是个快捷方式，这个？？？ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
牛，签名留念！
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
果然是个牛人！顶了学习下！
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
跑了几遍啊
强大~
|
|
|
|
