机械迷城，第8关
您好，不知道您想问什么， 以下是攻略，不过建议您自己琢磨，这才是游戏的乐趣。
08 上楼来和乐队的几个机器人对话在，得知鼓手机器人的鼓被坏蛋弄坏了，萨克斯风前面的按钮也没了，另一个家伙像炮筒的东西里藏着不知道什么动物.只能看到眼睛，向右边的门走，是一个酒（油）店。想找老板拿点油，结果老板要钱，里面一个桌子那坐着一个机器人，坐到他对面再点桌子，和他玩五子棋.我下棋水平太烂，下了N次不是输就平手，随便在网上找了个五子棋程序照着电脑的走法终于走赢...
下赢后，电脑大怒，把棋子摔了一地，捡起电脑摔掉的五个棋子，看这形状和数量，估计正好可以安在萨克斯风上面，里面还有个房间有三个人在打牌，难道是在斗地主？先不管他们，门附近处捡到一个类似皮带的道具，不知道什么用。先把棋子交给萨克斯风机器人手里，当场演奏一番，结果被楼上的人大骂，还扔了个花盆下来.下面的门原来就是最先开始的出口，这里有一处在滴油，估计有用处.把类似皮带的道具放在苍蝇乱飞的污水处可以粘到苍蝇，原来这个是个粘苍蝇的东西，把苍蝇带到酒店里对着酒店老板用，趁机偷走油筒，再把油筒交给鼓手机器人，鼓手敲了一通鼓，楼上的大妈又怒了，这次把另一个有植物的花盆扔下来了.
上楼梯向上走，走到一个广场，果然右边的坐轮椅的机器人想要油，把油壶拿到那里装满油出来给那人.终于轮椅可以转了，没想到那人又要我去找葵花油？左边的大妈机器人似乎在算某个难题还是什么，门上有两个标签，表示的含义暂时还不知道什么意思，从大妈旁边的楼梯上去，这里有个长腿梯子机器人在检修线路，顺着他的梯子爬上去抓猫，可惜够不着，把检修线路机器人的那个电源插头拔了，然后下来，等机器人回去插插头的时候，把红线扯一下，于是检修线路的机器会移动到另一边清理线路，再上去可以够到猫，不过还是抓不住，右边的路灯那好像是个拼图的游戏，还没玩呢，一块拼图就掉下来了，结果路灯上面的鸟一下把拼图抢跑了，走到路灯前的桥上，结果上面的鸟模仿你，你可以把机器人拉长再变矮，注意时机和节奏，几个回合后电线断了，鸟儿掉下来了，得到掉了的拼图.将断了的电线系在铁拉杆上，再把拼图完成，这时候铁栏杆就带电了，上梯子抓猫，猫跳到栏杆后被电到，再去把拼图的一块取下来，就能抓到猫了，抓到猫就能去解决第三个乐队机器人的麻烦了，把猫放进去，老鼠就跑出来了，乐队又是一番演奏，楼上的大妈这次把收音机给摔下来了.拿起收音机，再一次来到广场，画面下方正中间有个摇杆，把它拿出来，插到钟楼下面的洞里面，可以转动时针了.照墙上的提示把红色指针指向VII，把黑色指针指向∽符号，这时候门就开了，大妈进了门，可以看到大妈背后的纸片了，再照提示把指针指向6和VI，大妈出来了，对面的大叔从那边跑过来进了门，我们就溜上去拿到类似喇叭的道具，可以和收音机组合起来.再来到轮椅大叔面前，拉开下水道的盖子下去.下到下水道里，走到右边，桌子里有本工作手册.手册可以翻页，最后一页里面藏着一把扳手，那一排的管道也有一把扳手和一个铁钩子，下楼梯来，出水口处用铁钩子又可勾到一把扳手，拿到三个扳手回到管道处，要把管道的出水口关住，让水不再留，很简单，把几个阀门用扳手关死就行了，如图所示.
这时再上去广场就可以看到水已经停了.下到下水道里把组合好的收音机放在桌子上插上电，然后点一下扳手机器人，就可以把水箱里的水放掉了，这下可害苦了下面斗地主的三个人，哈哈.再上到广场去，跳进空了的水箱里，就到了一个新地方.
求走迷宫问题的算法，要求用Java写的？
public class Maze { private int[][] maze = null;
private int[] xx = { 1, 0, -1, 0 };
private int[] yy = { 0, 1, 0, -1 };
private Queue queue = null; public Maze(int[][] maze) {
this.maze = maze;
queue = new Queue(maze.length * maze.length);
} public void go() {
Point outPt = new Point(maze.length - 1, maze[0].length - 1);
Point curPt = new Point(0, 0);
Node curNode = new Node(curPt, null);
maze[curPt.x][curPt.y] = 2;
queue.entryQ(curNode); while (!queue.isEmpty()) {
curNode = queue.outQ();
for (int i = 0; i < xx.length; ++i) {
Point nextPt = new Point();
nextPt.x = (curNode.point).x + xx[i];
nextPt.y = (curNode.point).y + yy[i];
if (check(nextPt)) {
Node nextNode = new Node(nextPt, curNode);
queue.entryQ(nextNode);
maze[nextPt.x][nextPt.y] = 2;
if (nextPt.equals(outPt)) {
java.util.Stack stack = new java.util.Stack();
stack.push(nextNode);
while ((curNode = nextNode.previous) != null) {
nextNode = curNode;
stack.push(curNode);
}
System.out.println("A Path is:");
while (!stack.isEmpty()) {
curNode = stack.pop();
System.out.println(curNode.point);
}
return;
}
}
}
}
System.out.println("Non solution!");
} private boolean check(Point p) {
if (p.x = maze.length || p.y = maze[0].length) {
return false;
}
if (maze[p.x][p.y] != 0) {
return false;
}
return true;
} public static void main(String[] args) {
int[][] maze = {
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 }
};
new Maze(maze).go();
} private class Queue { Node[] array = null;
int size = 0;
int len = 0;
int head = 0;
int tail = 0; public Queue(int n) {
array = new Node[n + 1];
size = n + 1;
} public boolean entryQ(Node node) {
if (isFull()) {
return false;
}
tail = (tail + 1) % size;
array[tail] = node;
len++;
return true;
} public Node outQ() {
if (isEmpty()) {
return null;
}
head = (head + 1) % size;
len--;
return array[head];
} public boolean isEmpty() {
return (len == 0 || head == tail) ? true : false;
} public boolean isFull() {
return ((tail + 1) % size == head) ? true : false;
}
} private class Node { Point point = null;
Node previous = null; public Node() {
this(null,null);
} public Node(Point point, Node node) {
this.point = point;
this.previous = node;
}
} private class Point { int x = 0;
int y = 0; public Point() {
this(0, 0);
} public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Point p) {
return (x == p.x) && (y == p.y);
} @Override
public String toString() {
return "(" + x + "," + y + ")";
}
}
}
迷宫问题求解的实现算法
源程序：
//base.h
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
//stack.h
#include "base.h"
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef struct{ //迷宫中r行c列的位置
int r;
int c;
}PostType;
typedef struct{
int ord; //当前位置在路径上的序号
PostType seat;//当前坐标
int di; //往下一坐标的方向
}SElemType; //栈元素类型
typedef struct{
SElemType* base;//栈基址,构造前销毁后为空
SElemType* top;//栈顶
int stackSize; //栈容量
}Stack; //栈类型
Status InitStack(Stack &S){ //构造空栈s
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stackSize=INIT_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack S){
//若s为空返回TRUE,否则返回FALSE
if(S.top==S.base)
return TRUE;
return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >=S.stackSize){//栈满，加空间
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S){//销毁栈S,
free(S.base);
S.top=S.base;
return OK;
机器人是如何走出迷宫的
首先，我们要了解，机器人领域的视觉（Machine Vision）跟计算机领域（Computer Vision）的视觉有一些不同：机器视觉的目的是给机器人提供操作物体的信息。所以，机器视觉的研究大概有这几块： 物体识别（Object Recognition）：在图像中检测到物体类型等，这跟 CV 的研究有很大一部分交叉； 位姿估计（Pose Estimation）：计算出物体在摄像机坐标系下的位置和姿态，对于机器人而言，需要抓取东西，不仅要知道这是什么，也需要知道它具体在哪里； 相机标定（Camera Calibration）：因为上面做的只是计算了物体在相机坐标系下的坐标，我们还需要确定相机跟机器人的相对位置和姿态，这样才可以将物体位姿转换到机器人位姿。 当然，我这里主要是讲物体定位领域的机器视觉；SLAM 等其他领域的就先不讲了。 算法肯定也是有的。 由于视觉是机器人感知的一块很重要内容，所以研究也非常多了，我就我了解的一些，按照由简入繁的顺序介绍吧： 1. 相机标定 这其实属于比较成熟的领域。由于我们所有物体识别都只是计算物体在相机坐标系下的位姿，但是，机器人操作物体需要知道物体在机器人坐标系下的位姿。所以，我们先需要对相机的位姿进行标定。 内参标定就不说了，参照张正友的论文，或者各种标定工具箱； 外参标定的话，根据相机安装位置，有两种方式： Eye to Hand：相机与机器人极坐标系固连，不随机械臂运动而运动Eye in Hand：相机固连在机械臂上，随机械臂运动而运动 两种方式的求解思路都类似，首先是眼在手外（Eye to Hand） 只需在机械臂末端固定一个棋盘格，在相机视野内运动几个姿态。由于相机可以计算出棋盘格相对于相机坐标系的位姿 、机器人运动学正解可以计算出机器人底座到末端抓手之间的位姿变化 、而末端爪手与棋盘格的位姿相对固定不变。 而对于眼在手上（Eye in Hand）的情况，也类似，在地上随便放一个棋盘格（与机器人基座固连），然后让机械臂带着相机走几个位姿，然后也可以形成一个 的坐标环。 2 平面物体检测 这是目前工业流水线上最常见的场景。目前来看，这一领域对视觉的要求是：快速、精确、稳定。所以，一般是采用最简单的边缘提取+边缘匹配/形状匹配的方法；而且，为了提高稳定性、一般会通过主要打光源、采用反差大的背景等手段，减少系统变量。目前，很多智能相机（如 cognex）都直接内嵌了这些功能；而且，物体一般都是放置在一个平面上，相机只需计算物体的 三自由度位姿即可。 另外，这种应用场景一般都是用于处理一种特定工件，相当于只有位姿估计，而没有物体识别。 当然，工业上追求稳定性无可厚非，但是随着生产自动化的要求越来越高，以及服务类机器人的兴起。对更复杂物体的完整位姿 估计也就成了机器视觉的研究热点。 3. 有纹理的物体 机器人视觉领域是最早开始研究有纹理的物体的，如饮料瓶、零食盒等表面带有丰富纹理的都属于这一类。 当然，这些物体也还是可以用类似边缘提取+模板匹配的方法。但是，实际机器人操作过程中，环境会更加复杂：光照条件不确定（光照）、物体距离相机距离不确定（尺度）、相机看物体的角度不确定（旋转、仿射）、甚至是被其他物体遮挡（遮挡）。幸好有一位叫做 Lowe 的大神，提出了一个叫做 SIFT （Scale-invariant feature transform）的超强局部特征点： Lowe, David G. "Distinctive image features from scale-invariant keypoints."International journal of computer vision 60.2 (2004): 91-110. 具体原理可以看上面这篇被引用 4万+ 的论文或各种博客，简单地说，这个方法提取的特征点只跟物体表面的某部分纹理有关，与光照变化、尺度变化、仿射变换、整个物体无关。 因此，利用 SIFT 特征点，可以直接在相机图像中寻找到与数据库中相同的特征点，这样，就可以确定相机中的物体是什么东西（物体识别）。对于不会变形的物体，特征点在物体坐标系下的位置是固定的。所以，我们在获取若干点对之后，就可以直接求解出相机中物体与数据库中物体之间的单应性矩阵。 如果我们用深度相机（如Kinect）或者双目视觉方法，确定出每个特征点的 3D 位置。那么，直接求解这个 PnP 问题，就可以计算出物体在当前相机坐标系下的位姿。 4. 无纹理的物体 好了，有问题的物体容易解决，那么生活中或者工业里还有很多物体是没有纹理的我们最容易想到的就是：是否有一种特征点，可以描述物体形状，同时具有跟 SIFT 相似的不变性？ 不幸的是，据我了解，目前没有这种特征点。 所以，之前一大类方法还是采用基于模板匹配的办法，但是，对匹配的特征进行了专门选择（不只是边缘等简单特征）。 这里，我介绍一个我们实验室之前使用和重现过的算法 LineMod： Hinterstoisser, Stefan, et al. "Multimodal templates for real-time detection of texture-less objects in heavily cluttered scenes." Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011. 简单而言，这篇论文同时利用了彩色图像的图像梯度和深度图像的表面法向作为特征，与数据库中的模板进行匹配。 由于数据库中的模板是从一个物体的多个视角拍摄后生成的，所以这样匹配得到的物体位姿只能算是初步估计，并不精确。 但是，只要有了这个初步估计的物体位姿，我们就可以直接采用 ICP 算法（Iterative closest point）匹配物体模型与 3D 点云，从而得到物体在相机坐标系下的精确位姿。当然，这个算法在具体实施过程中还是有很多细节的：如何建立模板、颜色梯度的表示等。另外，这种方法无法应对物体被遮挡的情况。（当然，通过降低匹配阈值，可以应对部分遮挡，但是会造成误识别）。 针对部分遮挡的情况，我们实验室的张博士去年对 LineMod 进行了改进，但由于论文尚未发表，所以就先不过多涉及了。 5. 深度学习 由于深度学习在计算机视觉领域得到了非常好的效果，我们做机器人的自然也会尝试把 DL 用到机器人的物体识别中。 首先，对于物体识别，这个就可以照搬 DL 的研究成果了，各种 CNN 拿过来用就好了。有没有将深度学习融入机器人领域的尝试？有哪些难点？ - 知乎 这个回答中，我提到 2016 年的『亚马逊抓取大赛』中，很多队伍都采用了 DL 作为物体识别算法。 然而， 在这个比赛中，虽然很多人采用 DL 进行物体识别，但在物体位姿估计方面都还是使用比较简单、或者传统的算法。似乎并未广泛采用 DL。 如 @周博磊 所说，一般是采用 semantic segmentation network 在彩色图像上进行物体分割，之后，将分割出的部分点云与物体 3D 模型进行 ICP 匹配。 当然，直接用神经网络做位姿估计的工作也是有的，如这篇： Doumanoglou, Andreas, et al. "Recovering 6d object pose and predicting next-best-view in the crowd." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.它的方法大概是这样：对于一个物体，取很多小块 RGB-D 数据（只关心一个patch，用局部特征可以应对遮挡）；每小块有一个坐标（相对于物体坐标系）；然后，首先用一个自编码器对数据进行降维；之后，用将降维后的特征用于训练Hough Forest。 6. 与任务/运动规划结合 这部分也是比较有意思的研究内容，由于机器视觉的目的是给机器人操作物体提供信息，所以，并不限于相机中的物体识别与定位，往往需要跟机器人的其他模块相结合。我们让机器人从冰箱中拿一瓶『雪碧』，但是这个 『雪碧』 被『美年达』挡住了。 我们人类的做法是这样的：先把 『美年达』 移开，再去取 『雪碧』 。 所以，对于机器人来说，它需要先通过视觉确定雪碧在『美年达』后面，同时，还需要确定『美年达』这个东西是可以移开的，而不是冰箱门之类固定不可拿开的物体。 当然，将视觉跟机器人结合后，会引出其他很多好玩的新东西。由于不是我自己的研究方向，所以也就不再班门弄斧了。 更详细的图文解析可以到机器人家上去看，我这边就不贴出来了，希望对你有用