魔方游戏的设计与实现

摘 要

魔方是一种变化多端的智力玩具，又称鲁毕克方块，1974年由匈牙利建筑学教授鲁毕克发明。由于魔方的奥妙无穷，一直以来，不但有魔方游戏的大批爱好者，在学术界，对魔方也有着广泛而深入的研究，包括数学、物理等各个方向，魔方的研究成果也在许多领域得到了应用。
本文基于在计算机上实现一个魔方游戏的需要，对目前复原魔方中最常用的按层求解思想进行了深入的解析，抽象出一个按层求解算法，并最终把它转化为计算机上的算法实现。然后在此算法基础上，利用OpenGL API强大的场景渲染和描绘功能，设计了一个基于OpenGL平台的3D魔方游戏，通过对Windows输入消息的处理，使用户可以用鼠标和键盘手动操作玩魔方游戏，并且当求解有困难时，可以由计算机运用设计好的按层求解算法，进行魔方游戏的自动求解及其动画演示。
整个游戏设计友好简单，效果逼真，还具有自动求解演示功能，可以让玩家同时得到游戏的乐趣和解魔方的一些启迪。
论文最后对全文进行了总结，并对后续工作进行了展望。 think58

关键字：魔方；魔方还原算法；求解效率；Windows 编程；OpenGL
2  自动求解算法分析
 目前对魔方的求解算法很多，有穷举法、全排列和递归求解法[3]、树搜索算法[4]等。这些算法，都有一些不足之处，如穷举法，它要计算魔方的所有状态，其数量巨大，效率低下；树搜索算法需要比较复杂的数据结构和算法技巧的运用。目前也有人针对魔方提出了一个人工智能的搜索算法，并建立了数学模型[5]。本章将对按层求解思想[6]在此进行详细的剖析，先说明在现实中手动还原魔方时，按层求解思想的具体应用，然后再抽象出一个按层求解算法，并把它在计算机中实现。按层求解算法将是本游戏中实现魔方自动求解演示所采用的算法。
2.1  按层求解方案的具体应用
 首先，先说明求解过程中要用到的一些术语。正如先前阐述魔方所说的，魔方单元块有3种，6个固定的中心块，只有一个颜色面，以自己为轴旋转，8个角块，有3个颜色面，12个边块，有2个颜色面，都是饶中心块旋转。由于中心块固定，它的颜色决定了魔方表面的颜色。对各个块，通过旋转能达到3种状态，即：归位、定向、还原[7]。块归位是指所需块已经正确的位置，但各面的方向不一定合适，需要通过旋转来调整。块定向是只所需块的各面的方向已经正确，但还未到达正确的位置。块还原是指块的位置和各个面的方向都已正确。 think58好，好think58 [版权所有：http://think58.com]
现在，我们分7步，开始对魔方进行按层求解[8]。
步骤一：复原魔方顶层，定位所有角块使该层各面颜色一致
当我们准备好一个魔方之后，就已经解决了顶层的一个角块，现在我们准备解决其余的三个。先整体向左旋转魔方，从而使原来的那个角块转到了魔方前面的左上方角块位置。在这个例子中，如图2.3所示，你能看到左上方角块现在是原来的那个蓝-红-白角块，其前面为红色(因为我们已经把整个魔方向左旋转了)。现在我们又需要解决转到右上方的那个角块了，所以需要先计算是哪个角块要放置到那。其实这个很容易。既然这个角块必须有一个蓝色面(否则的话，就不能和顶层颜色匹配了)，它还必须有一个红色面(否则的话，就没法让前面为红色了)，因此只需简单的找一个有蓝、红2种颜色的角块就行了，在此，我们假定找到的是一个蓝-红-黄角块。接下来的步骤是转动目标块到魔方的右下角块位置(我们用黑色标记来帮助确认目标位置)。这个魔方单元的蓝、红、黄色面可以是任意的顺序，并在任何的一个面，只要这个方块在正确的位置就行了。通过旋转底层，顶层不动，直到目标块归位。一旦目标块已经到了前面的右下角块位置，根据顶层色面(蓝色)所在的位置，我选择如下的方案(图2.4)来把它转到右上角块位置。
举例说，如果所需的蓝-红-黄角块碰巧它的蓝色面在魔方的右边(图2.3的位置1)，我们就可以使用算法1，如果是在前面(图2.3的位置2)，就可以使用第二种算法。最后，如果蓝色面是在底部(图2.3的位置3，图中手所指示的底部)，那么就可以使用算法3了。也有可能目标蓝-红-黄角块已经在顶层位归位了(同样用黑色来表示目标)，但是还没有定向(红色面没有和初始块的红色面一致)。如果蓝色面在前面(图2.3的位置4)，使用算法4，若在方块的右边(图2.3的位置5)，当然就使用算法5了。如果愿意，也可以从其他的方向开始，只要牢记实现所有顶层角块的上面颜色和顶层颜色匹配的目标就行了。如果所需的立方块转到了中间层，就跳过去处理另一个角块，一旦完成，目标块就会转到顶层或底层。当把这些角块都完成后，魔方就应当看起来像一个图2.5所显示的一个迷你小魔方，魔方的上部就是一个蓝色的“X”，并且其所有角块的颜色和其他角块颜色水平匹配。接下来，我们就可以完成边块来复原顶层了。

内容来自think58 [资料来源：THINK58.com]

2.2  按层求解算法在计算机中的实现
对上面按层求解的思想，把它转化为计算机语言，就能在计算机上通过一定的算法把它给表示出来了。算法分为7个步骤，如下：
步骤一：上层四个角块还原。
步骤二：上层四个边块还原。
步骤三：中间四个边块还原。
步骤四：下层四个角块归位。
步骤五：下层四个角块定向。
步骤六：下层四个边块归位。
步骤七：下层四个边块定向。
对具体每步的算法实现，可见附录，每个步骤对应了一个实现的函数体。
现就7个按层求解的函数体中所调用的其他的一些函数的功能做以下说明：
FindCen(int a)，返回所给颜色的中心块位置。
FindEdge(int a, int b) ，返回所给颜色的边块位置。
FindCorn(int a, int b, int c) ，返回所给颜色的角块位置。
UL()，顶层向左转。
UR()，顶层向右转。
DL()，底层向左转。
DR()，底层向右转。
LU()，左层向上转。
LD()，左层向下转。
RU()，右层向上转。
RD()，右层向下转。
FC()，前层顺时针。
FA()，前层逆时针。
BC()，后层顺时针转 (从前面看) 。
BA()，后层逆时针转 (从前面看) 。
ML()，中间层左转。
MR()，中间层右转。
MU()，中间层上转。 [资料来源：http://think58.com]
MD()，中间层下转。 本文来自think58
MC()，中间层顺时针转。
MA()，中间层逆时针转。
CL()，魔方整体左转。
CR()，魔方整体右转。
CU()，魔方整体上转。
CD()，魔方整体下转。
CC()，魔方整体顺时针转。
CA()，魔方整体逆时针转。
XCL()，魔方整体左转，中间层不转。
copyright think58