魔方游戏的设计与实现

论文字数:18591,页数:45  有开题报告，任务书

摘 要

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

关键字：魔方；魔方还原算法；求解效率；Windows 编程；OpenGL
Design and Implementation of Cube Game
 
 
 Abstract
 
 Magic cube is an intellectual toy with great variety; also know as Rubik’s cube, which was invented by the Hungarian architectural professor Rubik in 1974. Due to its endless profound, not only there are a number of fans to the magic cube game, also there are many wide and deep studies about magic cube in academia, including Math, Physics and so on, and the research can be applied to various fields.
 The dissertation based on the need of implementing Rubik’s cube on the computer, giving an in-depth analysis to the “by layer solution” which is in common use in the cube’s recovery at present and abstracting a “by layer algorithm”, then realize the algorithm on computer at last. Next based on the algorithm, use the powerful scene rendering and depicting function of the OpenGL API, design a 3D cube game based on the OpenGL platform. By dealing with the input message, the user can play the game by mouse or keyboard. When the manual recovery is in trouble, the player can make the computer solve the cube by the designed algorithm automatically and offer a dynamic revolving effect.
 The whole game has a friendly user interface and a vivid effect, along with a automatic solving function, making the players have both the game joy and the cube solving hint.
 Finally, the conclusion of this dissertation has been given and the development trend has been predicted.
 
 Key Words: magic cube; magic cube solve algorithm; solve efficiency; Windows Programming; OpenGL
 
目录
1 绪论 1
1.1 魔方的起源 1
1.2 魔方的构造 1
1.2.1 力学构造 1
1.2.2 数学构造 2
1.2.3 心理学构造 2
1.3 魔方研究概况 3
1.3.1 70年代 3
1.3.2 80年代 4
1.3.3 90年代 5
1.4 论文组织结构 5
2 自动求解算法分析 7
2.1 按层求解方案的具体应用 7
2.2 按层求解算法在计算机中的实现 15
2.3 本章小结 17
3 游戏的设计目标及实现 18
3.1 游戏设计目标及要求 18
3.2 游戏的功能点及其难点分析 18
3.2.1 魔方在计算机上的存储问题 18
3.2.2 魔方在计算机上的3D效果显示 18
3.2.3 魔方的旋转问题 19
3.2.4 游戏状态的加载保存 19
3.2.5 魔方的置乱和自动求解演示 19
3.2.6 魔方的自动求解算法 19
3.3 魔方游戏基本功能的实现 19
3.3.1 Cube类的设计 19
3.3.2 cube Handle 类的设计 21
3.4 游戏的程序框架 23
3.4.1 程序主体的实现 23
3.4.2 OpenGL场景渲染 23
3.5 本章小结 24
4 总结与展望 25
4.1 开发设计工作总结 25
4.2 魔方游戏的进一步研究 25
致谢 26
参考文献 27
附录 28