做做AI，造造人 - 动力老男孩的博客

话说萝卜头完工以后，我经常想一个问题：接下来做点啥？

其实这期间有过很多想法，例如乐高打印机，写毛笔字，下五子棋以及等等等等。
面临的问题是，萝卜头就像是家庭的一个成员，实在不忍心拆掉。但是横不能每做一样东西就买一套NXT吧，毕竟咱的钱也不是大风刮来的。

有一天我家娘子说：“我给你出道题吧，给咱们家圈圈做一个小摇篮，如果半夜圈圈哭闹的话，就自动的摇啊摇，这样咱们就不用起来哄了。。”
看，这世界还真是由懒人推动的。我飞快的想了一下，可以用一个亮度传感器判断是白天还是晚上，再用一个声音传感器判断有没有哭闹，最后带动电机来摇动小摇篮，用LabelView就可以实现了。

想到这里，我又回到了那个老问题，有没有必要为这样特定的功能单独用一套NXT，能不能做一个通用的机械结构，既可以下棋，还可以照顾小孩呢？毫无疑问，这就需要一个真正的机器人了。所以我们决定做一个跟大孩子差不多高的小机器人，如果能够制作成功的话，就可以通过软件的更新来实现各种不同的功能。这个小家伙看来是不能用乐高实现了，我准备向那位俄罗斯的手工狂人学习。

这个小家伙的名字叫“小爱”，来源于AI的意思，顺便也沾点爱迪生，爱因斯坦等同学的光。小爱还没诞生，我们就给她安排了很多工作，比如端茶倒水，揉肩捶背，铲冰除雪，溜门撬锁等等（简直就是无良父母啊 ）

YY了半天，赶紧回到现实。我暂时还是电子技术的门外汉，甚至还没有设计过一块电路板。可能有些高手看到这个帖子，会带着鄙夷的酱油飘过“俺们这些专业人士也不见得能做好啊”。嗯，对于困难我早有心理准备，小爱的诞生也许是一个非常漫长的过程，但是年轻啥都不怕，我们都充满信心！

孔子曰：三人行必有我师，n人行必有我n师。希望有更多的朋友光临小站和论坛，分享经验，互相学习，共同进步。

我们的快速魔方算法要隆重登场了，在此缺席感谢一下来自Netherlands的Jaap Scherphuis同学。看前面这个页面的第三名。

魔方表示法
咱们先看一串天书般的字母：UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
这种表示法是由一个叫Mike Reid的兄弟首先使用的，它表示一个已经被解好的魔方。
先不要被这串字母吓倒，看算法就像追mm一样，要迎难而上。仔细观察，你会发现其中只有六种字母：
U: Up
F: Front
R: Right
L: Left
D: Down
B: Back
其实这就是代表了空间坐标系的六个方向，就是传说中的“眼观六路”的那六路。
表示法中包含了12组双字母的组合，分别代表了魔方的12个棱，第一组UF就表示Up和Front之间夹角的棱。
另外还包含了8组三字母的组合，分别代表了魔方的8个角，每个角由三块颜色组成。看下面的示意图：

魔方坐标系

等等，细心的朋友至少会想到两个问题：
1，为什么没有中心的数据？
因为魔方的六个心在任何旋转过程中，相对位置都是不会变的，这点拆过魔方的人应该比较容易理解。
2，如果是一个打乱的魔方，棱和边的颜色已经和中心不一样了，这时候怎么表示？
读取方法是：按照刚才那个天书字符串的顺序，先找到UF位置所对应的棱，假设现在U是红色，F是黄色；
那么对照图里的中心，红色的中心是R，黄色的中心是U，所以这时候的第一组棱字母是 RU
嗯，希望你看到这里还没有晕车的感觉。

输出表示法
这个程序的输出是这个样子：F- U+ F- D- L- D- F- U- L2 D-
FRL之类的字母依然表示六个面，F-表示前层逆时针转90度，U+表示上层顺时针转90度，L2表示左边层转180度。
如果你是魔友的话，会经常看到这样的字符串：F’UF’D'L’F'U’L2D’
这是魔方论坛上比较常见的“黑话”，其实就是默认顺时针不加符号，逆时针的加一个单引号，180度的加2。
请注意这里的顺时针和逆时针使用的是“观察者迎着某个面看”的参照系，例如B’是从下往上看的逆时针，如果你没有把脑袋钻到桌子下，你事实上看到的是顺时针旋转。

改写到C#
这段程序是用C写的，说实话它的原理还比较复杂，有兴趣的同学可以搜索“Thistlethwaite’s algorithm”
我直接依葫芦画瓢用C#把它重写了一遍，请点击这里下载源代码。请主要要安装VS2008或更高版本。

http://www.diy-robots.com/RubikSolver/RubikSolverSample.zip

补充：如何使用这个程序

鉴于很多朋友询问如何运行这个程序，下载这段代码，用C语言的编译器编译成Jaap.exe。然后在命令行输入：
Jaap.exe UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

输出结果就是类似 F- U+ F- D- L- D- F- U- L2 D- 这样的步骤。
注意这段程序没有验证功能，如果你输入的颜色表达式错误，会导致程序死循环或者错误。以我的经验看，普通电脑都能在1秒以内算完，如果你一秒钟还没有看到结果，就检查检查输入吧。

应一些网友的建议，添加了一个论坛，链接在右上角头像的上面
欢迎大家在这里讨论问题，或者没事过来踩踩

本来我想把这个攻略做成一个NXT开发的教程，把传感器，电机，发声等部分都介绍一遍。不过现在看来有些同学很心急，希望早点看到“核心代码”，所以我提前把解魔方的算法写出来。其实魔方的算法网上有很多，只要你耐心并且有效的使用搜索引擎，会发现上个世纪就已经有人公布算法或源代码了，例如
算法：http://www.zunny.com/RUBIK.HTM
代码：http://tomas.rokicki.com/cubecontest/

不过我做第一版的时候，还是决定自己动手写算法。原因很简单：我玩魔方很多年了，把玩法转成算法也是我的目标之一。在写程序之前，我画了以下的几张草图：

魔方算法的草稿

 话说曾经有位同事本打算和我一起做萝卜头的，看了这些草图以后，决定还是继续打游戏更靠谱。这不禁让我想起一首歌“1979年，那是一个春天，有一位老人在中国的南海边画了一个圈…” 这位老同志一定是资深软件架构师，改革开放这么宏伟的事情，画个圈就搞定了。
这样说来我这个草图是太复杂了，难怪把人吓跑了。今天特地又重画了些好看的图，以便大家理解。

魔方表示法
算法的第一个问题就是，怎么用数学方式描述一个魔方状态。我的做法是把魔方想象成一个纸盒子，沿边缝剪开铺平，就形成了六个面，我按照图里的顺序给它们编了号。
每个面又包含了9个颜色小方块，我也按照图中的顺序给它们编了号。

魔方的数组表示法

这样一来，立体的魔方就变成了一个 6*9 的数组。例如下面是一个普通的被打乱的魔方：

static String SideColors[] = {
  "orgorwwoo",
  "oyggbobrg",
  "yyrgowwbw",
  "yrybgybbo",
  "gwwyybror",
  "bgrwwrbgy"

魔方坐标系：
啥？怎么又有坐标系，刚才的表示法不就完全描述了一个魔方吗？没错，但是咱们的萝卜头每次只能旋转魔方的最下面一层，假设我们需要旋转最上面一层，就必须先把它翻到下面。
请注意在翻跟头的过程中，魔方本身并没有变化，只是坐标系变了。所以还需要一个坐标系来对应萝卜头的空间：

魔方坐标系

状态变化：
正如刚才所说，魔方在萝卜头的数字世界里有两种变化形式：1，翻跟头；2，旋转某一面。
每次状态变化都会造成SideColors数组发生变化，这种转换用最简单的查表法就可以搞定：

坐标变化的大概示意图，坐标变化没啥难度，主要看耐心

例如，这是一段旋转底面后状态转换的代码：

public static void RotateBottomSide(boolean ClockWise) throws Exception
{
 int temp=0;
 int i;

 CopyMatrics(2,6,ClockWise?2:1); //Bottom ClockWise = Top Anti-ClockWise
 CopyMatrics(6,2,0);
 if(ClockWise)
 {
  for(i=0;i<3;i++)
  {
   temp=Sides[5][0][i];
   Sides[5][0][i]=Sides[3][2-i][0];
   Sides[3][2-i][0]=Sides[4][2][2-i];
   Sides[4][2][2-i]=Sides[1][i][2];
   Sides[1][i][2]=temp;
  }
 }
 else
 {
  for(i=0;i<3;i++)
  {
   temp=Sides[5][0][i];
   Sides[5][0][i]=Sides[1][i][2];
   Sides[1][i][2]=Sides[4][2][2-i];
   Sides[4][2][2-i]=Sides[3][2-i][0];
   Sides[3][2-i][0]=temp;
  }
 }
}

CFOP解法：
这是由一位叫Jessica Fridrich女士发明的一种速解法，是目前世界上最流行的方块解法。
CROSS：字面上的意思为“十字”，是Fridrich Method中的第一步骤。
F2L：是“First 2 Layer”的缩写，意思为“一、二层”，是Fridrich Method中的第二步骤。
OLL：是“Orientation of Last Layer”的缩写，意思为“最后一层的角块排序”，这是Fridrich Method中的第三个步骤。
PLL：是“Permutation of Last Layer”的缩写，意思为“最后一层的排序”，这是Fridrich Method中的第四步骤。
CFOP：是Fridrich Method的的别称，就是四个步骤“Cross、F2L、OLL、PLL”原文的第一个字母合起来而成的。

上面这些文字比较费解，看下面的图就比较清楚了：

魔方的CFOP入门解法

或者你可以去魔方小站或者魔方吧看更详细的教程。

CFOP解法的实现：
这一部分比较繁琐，输入玩法公式的输入，按照上面的步骤实现以下函数：

TopCross();
TopCorner();
SecondLayer();
BottomCross();
BottomCorner();
ThirdLayerCorner();
ThirdLayerCornerSnap();
ThirdLayerBorderSnap();

CFOP算法的源代码可以点这里下载
通过这个CFOP算法，萝卜头完成了第一版：http://v.youku.com/v_show/id_XNDcwMDQ3NDQ=.html

这个算法的最大问题就是步骤太多，一般来说要120步左右，平均时间12分钟，大多数观众等不到转完就睡着了……
因为这个原因，我改用了一个更快的算法。写博客真是挺累啊，这个算法下次再介绍，心急的同学请看下面这个链接：
http://tomas.rokicki.com/cubecontest/ 点最上面的Winners，我用的是第二名的算法。

今天已经是2010年了，祝大家新年快乐，新的一年学习好，工作好，身体好，感情好。。。总之一切都好！新年的第一天继续发攻略，希望是一个好的开始

兵法说“代码未动，调试先行”。对于刚接触嵌入式开发的同学来说，把代码写进NXT简直就是杯具，没有断点，不能跟踪，程序挂掉了都不知道是哪里的问题。难怪有些公司招聘程序员的时候，提的要求是“能摸黑写代码”。。。

下面是一个简单的例子，它实现的功能是：每按一次Enter按钮，就显示当前的距离读数，按Escape按钮时退出程序。通过这个例子，你可以知道如何用NXT的面板按钮或传感器来做断点工具，用LCD显示屏来跟踪数据。因为不舍得把萝卜头全拆了，所以用好拆的部分来做例子，先凑合看看:)

import lejos.nxt.*;
import lejos.nxt.comm.*;

/**
 * First Sample: Read distance by the control of buttons
 * @author ChenWu
 * @see LCD
 * @see UltrasonicSensor
 * @see Button
 */
public class DebugSample
{
 static UltrasonicSensor distance=new UltrasonicSensor(SensorPort.S1);

 public static void main (String[] aArg) throws Exception
 {
  while(!Button.ESCAPE.isPressed())
  {
   LCD.drawString("Distance=" + distance.getDistance()+"  ",0,3);

   //Remove this while condition if you want to get dynamic value
   while(!Button.ESCAPE.isPressed() && !Button.ENTER.isPressed())
   {
    Thread.sleep(100);
   }
  }
 }
}

把文件保存为 DebugSample.java，在命令提示符中运行下面的命令，把程序写入NXT：
nxjc DebugSample.java
nxj -r DebugSample

把程序写入NXT，这个步骤也可以在Eclipse中完成

这段程序很短，有经验的老鸟们应该一目了然了。新同学请看下面的说明，没Java基础的请自己先补习一下吧

1.  头两行import是导入Lejos的函数库，导入之后才能调用lejos的各种API。

2.  NXT的显示屏幕是一个分辨率为100×64的LCD屏幕，LCD屏幕一共可以显示8行16列ASCII字符，可以用内置的LCD对象来控制显示内容。例如显示一串字符的命令是：
LCD.drawString(“string”,x,y);
这个命令表示显示string的开始位置坐标是(x,y)，下标从0开始。例如(0,3)表示从第4行的第1列开始显示。

显示的时候如果原来的位置有文字，会被覆盖掉，但是不会清除其他地方的文字。（我的程序里面distance后面加了两个空格，理由请自己思考一下）另外几个常用的方法是 drawInt 和 clear，更多的方法可以参考相应的API文档。

如果你想显示非标准的字体，甚至是一副图片，可以使用Image类，通过二进制数组进行像素级别的控制

3.  UltrasonicSensor 也是Lejos的内置对象，封装了超声波测距传感器的各种方法和属性。用distance.getDistance()函数就可以返回一个整数，这个数表示眼睛到物体之间的厘米，理论上范围是1到255。如果我们把眼睛捂上，或者距离超过255cm，它的读数都是255。

4.  SensorPort.S1表示该传感器是接在1号接口上（看NXT主机下面1~4的编号）

5.  Button用来响应面板上各按键的交互事件，button的对应关系看下面这个图

Button的对应关系

Button.ESCAPE.isPressed() 用来判断按键是否被按下了。另外一个常用的方式是 Button.ESCAPE.waitForPress(); 程序运行到这句函数时会被挂起，直到按钮按下时才会继续执行后面的语句。

6. 如果你觉得每次都按一下Enter键很烦，可以把中间的那个while条件注释掉（当然对应的一对大括号也要去掉）。这样一来屏幕就会动态显示当前的实时距离，按下Escape键时退出。

7. Thread.sleep(100)表示程序运行到这里时，会暂停100毫秒然后继续执行后面的代码。它的作用是让你有读数的时间，否则屏幕上的读数会飞快的变换，根本看不清。

看看效果如何：

按下Enter时，刷新距离读数，按下Escape时，程序退出

cnBeta有位网友认为这个距离传感器是冗余设计，正好我在这里介绍一下这个“眼睛”的作用：

1. 用来判断转台上有没有魔方，放了魔方的时候测量的距离是14~15，没有魔方的时候是18~20。通过这个值先变大，然后再变小，就可以知道是有人先把魔方拿走，然后再放回来，于是激活下一轮扫描颜色

2. 用来做断点调试使用。在搭建萝卜头的初期，它的胳膊经常骨折，颜色也经常读错。为了便于调试，我把眼睛设置成了一个中断开关。当我需要它暂停的时候，就用手捂住它的眼睛，它就会停下来，把手移开，它又可以继续工作。使用的代码如下：

public static void WaitForNextAction()throws Exception
{
 while(distance.getDistance()>150)
 {
  Thread.sleep(100);
 }
 return;
}

通过这个例子，你可以了解如何在制作乐高机器人的过程中进行单步调试。如果你有其他的好方法，请一定在这里留言，让大家一起分享，多谢多谢！

今天就先介绍这些，感谢新年第一天还来光临小站的热心朋友，祝大家新年好！