魔方游戲的設計與實現
1.8萬字 45頁
包括開題報告和任務書，論文正文，VC程序代碼


摘 要

魔方是一種變化多端的智力玩具，又稱魯畢克方塊，1974年由匈牙利建筑學教授魯畢克發(fā)明。由于魔方的奧妙無窮，一直以來，不但有魔方游戲的大批愛好者，在學術界，對魔方也有著廣泛而深入的研究，包括數學、物理等各個方向，魔方的研究成果也在許多領域得到了應用。
本文基于在計算機上實現一個魔方游戲的需要，對目前復原魔方中最常用的按層求解思想進行了深入的解析，抽象出一個按層求解算法，并最終把它轉化為計算機上的算法實現。然后在此算法基礎上，利用OpenGL API強大的場景渲染和描繪功能，設計了一個基于OpenGL平臺的3D魔方游戲，通過對Windows輸入消息的處理，使用戶可以用鼠標和鍵盤手動操作玩魔方游戲，并且當求解有困難時，可以由計算機運用設計好的按層求解算法，進行魔方游戲的自動求解及其動畫演示。
整個游戲設計友好簡單，效果逼真，還具有自動求解演示功能，可以讓玩家同時得到游戲的樂趣和解魔方的一些啟迪。
論文最后對全文進行了總結，并對后續(xù)工作進行了展望。

關鍵字：魔方；魔方還原算法；求解效率；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 游戲狀態(tài)的加載保存 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 開發(fā)設計工作總結 25
4.2 魔方游戲的進一步研究 25
致謝 26
參考文獻 27
附錄 28


參考文獻
[1] 李世春編著.魔方的科學和計算機表現[M].石油大學出版社
[2] 楊迅文編著.魔方探勝[M].福州：福建人民出版社
[3] 申春雪.用全排列和遞歸求解“魔方" — C++程序設計[J].洛陽大學學報
[4] 白治江,楊振亞,王成道.正則搜索樹的分支因數[J].上海海運學院學報
[5 彭曉君.基于Turbo C 2．0的人工智能魔方模型方案[J].肇慶學院學報
[6] Jasmine. Beginner Solution to the Rubik's Cube[EB/OL]



附錄
按層求解算法的VC代碼：
//步驟一:頂層角塊還原
const string Solver::TopCorners()
{
string s = ""; //求解步驟存儲在串s中
if (!cubeinit) return s;
string a = ""; int b = 0, c, c1, f, f1, f2, m = 0;
//循環(huán)處理，直到頂層個角塊完全復原
while (!(FindCorn(1, 2, 5) == 2 && FindCorn(2, 1, 5) == -3 &&
FindCorn(1, 3, 2) == 2 && FindCorn(3, 1, 2) == -1 &&
FindCorn(1, 4, 3) == 2 && FindCorn(4, 1, 3) == 3 &&
FindCorn(1, 5, 4) == 2 && FindCorn(5, 1, 4) == 1)) {
for (int i = 2; i <= b; i++) CR();
if (b > 0) { s += "CR."; CR(); } //魔方整體左轉
......