基于C++語言的2048算法設(shè)計(jì)

顏冠鵬 顏?zhàn)砍?/p>

（1 山東財(cái)經(jīng)大學(xué)國際貿(mào)易學(xué)院山東濟(jì)南 250014）

（2 電子科技大學(xué)微電子與固體電子學(xué)院四川成都 610054）

基于C++語言的2048算法設(shè)計(jì)

顏冠鵬1顏?zhàn)砍?

（1 山東財(cái)經(jīng)大學(xué)國際貿(mào)易學(xué)院山東濟(jì)南 250014）

（2 電子科技大學(xué)微電子與固體電子學(xué)院四川成都 610054）

針對(duì)2048的游戲規(guī)則，分析了該游戲的算法特點(diǎn)，對(duì)其相關(guān)的功能需求和算法設(shè)計(jì)進(jìn)行了簡單介紹，提出了一種新的設(shè)計(jì)方案。解決了該設(shè)計(jì)在方陣數(shù)據(jù)結(jié)構(gòu)、運(yùn)動(dòng)算法和游戲結(jié)束判斷方面的問題，并闡述了以隊(duì)列方式進(jìn)行坐標(biāo)運(yùn)算和操作擴(kuò)展的關(guān)鍵技術(shù)。軟件測(cè)試表明，該設(shè)計(jì)的方塊數(shù)值最大值受方陣階數(shù)和操作次數(shù)的限制，四階方陣的理論最大值為65 536，智力極高的人可達(dá)16 384，而一般人僅能達(dá)到2 048左右。

2048 算法設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu) 坐標(biāo)運(yùn)算 隊(duì)列

1 引言

2048 游戲是一款簡單而流行的數(shù)字游戲，屬于益智游戲。每次控制所有方塊向同一個(gè)方向運(yùn)動(dòng)，2個(gè)相同數(shù)字方塊撞在一起之后合并成為他們的和，每次操作之后會(huì)在空白的方格處隨機(jī)生成一個(gè)2或者4(其他模式會(huì)有所改變)，最終得到一個(gè)“2048”的方塊就算勝利了。由于規(guī)則簡單，各種版本和平臺(tái)上均有該款游戲。因此對(duì)該游戲的主要的算法[1-5]進(jìn)行了分析，并用C++語言實(shí)現(xiàn)。

2 總體設(shè)計(jì)

2.1 功能需求

2048游戲一般由以下幾個(gè)模塊來構(gòu)成：①矩陣方塊；②控制模塊；③計(jì)算模塊；④輸出模塊。每個(gè)模塊來實(shí)現(xiàn)2048游戲的各項(xiàng)功能，具體如下：方向移動(dòng)、方塊合并、記錄當(dāng)前數(shù)據(jù)和輸出計(jì)分結(jié)果等。

2.2 算法設(shè)計(jì)

根據(jù)2048游戲算法的功能需求和功能模塊，具體的算法設(shè)計(jì)如圖1所示。

圖1 2048游戲算法設(shè)計(jì)圖

3 需解決的問題

需解決的問題包括方陣的數(shù)據(jù)結(jié)構(gòu)、隨機(jī)方塊的生成、運(yùn)動(dòng)算法的設(shè)計(jì)和游戲結(jié)束的判斷，其主要體現(xiàn)在控制和計(jì)算模塊。

3.1 方陣的數(shù)據(jù)結(jié)構(gòu)

方陣為一個(gè)的矩陣[6]，該矩陣需要一個(gè)長度為的二維數(shù)組來構(gòu)建，定義該數(shù)組為，記為式。

3.2 初始隨機(jī)方塊的生成

通過觀察發(fā)現(xiàn)，該游戲開始會(huì)在矩陣內(nèi)的任意位置生成數(shù)值為2的數(shù)。

3.3 運(yùn)動(dòng)的算法設(shè)計(jì)

3.3.1 模塊設(shè)計(jì)

整個(gè)運(yùn)動(dòng)操作分3個(gè)模塊進(jìn)行，包括移動(dòng)模塊、歸并模塊和隨機(jī)數(shù)生成模塊，具體結(jié)構(gòu)如圖2所示。

圖2 模塊設(shè)計(jì)說明圖

移動(dòng)模塊用來執(zhí)行在整個(gè)矩陣按選定方向整體移動(dòng)的功能，歸并模塊實(shí)現(xiàn)了相鄰方塊按該方向的合并，而隨機(jī)數(shù)生成模塊完成了在矩陣任意空位置生成值為2的方塊，具體見式⑵。

3.3.2 移動(dòng)設(shè)計(jì)

當(dāng)進(jìn)行向某個(gè)方向的操作運(yùn)動(dòng)時(shí)，可采用一種交換排序[7]的算法來實(shí)現(xiàn)該操作。以向右操作為例，首先將矩陣按行劃分為n個(gè)有序數(shù)列：

然后分別對(duì)每個(gè)序列進(jìn)行移動(dòng)操作。一次移動(dòng)操作具體分4步：

第一步：設(shè)指針p和j，它們的初值分別為n+1和n；

第二步：從j所指的位置起向前搜索，取j-1和p的最小值作為p指針的值；

第三步：判斷j所指的值是否為0，若為0，則將p指針向前移動(dòng)，直到p指向的值不為零且不越過邊界為止，再交換p和j各自指向的值；

第四步：重復(fù)第二步和第三步，直到p越過邊界或j＜1為止。由于有n個(gè)序列，故該矩陣進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為O(n^2)。單個(gè)序列向右移動(dòng)操作的全過程如圖3所示。

圖3 單個(gè)序列向右移動(dòng)操作示例圖

以向右移動(dòng)為例，代碼如rightmove所示。

3.3.3 歸并設(shè)計(jì)

當(dāng)方塊向右整體移動(dòng)后，需按反方向進(jìn)行歸并操作。在之前劃分的n個(gè)有序數(shù)列中，分別對(duì)其進(jìn)行歸并操作[8]，一次歸并操作分二步。第一步：設(shè)指針j，初值為n，從j所指的位置開始向前搜索，若j與j-1所指的值相等，則將j所指的值×2，j-1所指的值賦0。并設(shè)q指針的初值為j-1，向前遍歷至2，不斷通過交換q和q-1所指的值來實(shí)現(xiàn)0向前的交換，實(shí)現(xiàn)1... q所指值的整體右移。該矩陣進(jìn)行歸并操作的時(shí)間復(fù)雜度為O(n3)。單個(gè)序列向右歸并的全過程如圖4所示。

圖4 單個(gè)序列向右歸并操作示例圖

以向右歸并為例，代碼實(shí)現(xiàn)如rightmerge。

3.3.4 移動(dòng)中的隨機(jī)數(shù)生成

當(dāng)完成了移動(dòng)和歸并操作后，構(gòu)造randomcreat模塊，可實(shí)現(xiàn)在矩陣任意空位置生成值為的2方塊的功能。

3.4 游戲結(jié)束判斷

當(dāng)矩陣在上、下、左和右4個(gè)方向的運(yùn)動(dòng)操作均無效時(shí)，游戲結(jié)束。經(jīng)分析得，游戲結(jié)束必須滿足以下2個(gè)條件：

即對(duì)任意一個(gè)方格，數(shù)值不為空；且與之相鄰的方格數(shù)值也不相等。該解釋的偽代碼如judge所示。

4 關(guān)鍵技術(shù)

關(guān)鍵技術(shù)主要包括以隊(duì)列[9]的方式進(jìn)行坐標(biāo)運(yùn)算和操作擴(kuò)展。采用隊(duì)列方式可以減少編程的復(fù)雜度，方便進(jìn)行分布式計(jì)算[10]，加快求解速度。同時(shí)運(yùn)動(dòng)操作方式的多樣性也大幅度增加。

4.1 采用隊(duì)列的方式進(jìn)行坐標(biāo)運(yùn)算

由于4個(gè)方向的運(yùn)動(dòng)方式并不相同，在進(jìn)行重復(fù)編寫時(shí)，錯(cuò)誤率高且繁瑣，故考慮以隊(duì)列的方式，先將矩陣依照操作的方向劃分為n個(gè)有序數(shù)列。

然后對(duì)每個(gè)有序數(shù)列Qi，將其中每個(gè)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)依次加入隊(duì)列a；再以隊(duì)列所存儲(chǔ)的點(diǎn)的橫縱坐標(biāo)為基礎(chǔ)，進(jìn)行運(yùn)動(dòng)操作，設(shè)a為記錄點(diǎn)坐標(biāo)的記錄型數(shù)組，a.x記錄橫坐標(biāo)，a.y記錄縱坐標(biāo)，以向右運(yùn)動(dòng)為例，a隊(duì)列值如圖5所示。

圖5 向右運(yùn)動(dòng)坐標(biāo)運(yùn)算示例圖

這樣運(yùn)動(dòng)的偽代碼就不用按不同方向書寫了，程序所實(shí)現(xiàn)運(yùn)動(dòng)的方向只與a隊(duì)列的點(diǎn)坐標(biāo)次序有關(guān)，偽代碼的解釋如moveandmerge所示。

在進(jìn)行向右運(yùn)動(dòng)操作時(shí)，只需在以隊(duì)列為構(gòu)架的運(yùn)動(dòng)模塊的基礎(chǔ)上，附加一個(gè)給a隊(duì)列向右賦值的模塊即可，實(shí)現(xiàn)也相對(duì)容易。附設(shè)l為a隊(duì)列的隊(duì)尾指針，順序遍歷有序數(shù)列時(shí)，將有序數(shù)列的點(diǎn)依次賦值到a隊(duì)列的隊(duì)尾，并將隊(duì)尾指針l后移一位，具體偽代碼如right所示。

4.2 運(yùn)用隊(duì)列進(jìn)行更多方式的操作

在原有運(yùn)動(dòng)方向的基礎(chǔ)上，對(duì)其進(jìn)行合并和擴(kuò)展，就能寫出更多新穎的操作，像左上、右下、左下和右上等操作，以"右下"為例，具體如圖6所示。

圖6 右下運(yùn)動(dòng)坐標(biāo)運(yùn)算示例圖

5 性能測(cè)試結(jié)果分析

經(jīng)n次運(yùn)動(dòng)操作后，該矩陣內(nèi)能達(dá)到的方塊數(shù)值最大值為2n+2。但是最大值也受矩陣階數(shù)的限制，一般來說，四階矩陣所能達(dá)到的最大值為216=65 536。經(jīng)計(jì)算，理論上達(dá)到該值最少需要32 767步。實(shí)際上由于人所做的每一次決策并非最優(yōu)，智力極高的人通過較優(yōu)的決策只能達(dá)到的最大值為16 384，而一般人僅能達(dá)到2 048左右。

6 結(jié)束語

經(jīng)過對(duì)整個(gè)2048算法的設(shè)計(jì)與實(shí)現(xiàn)，在原有的基礎(chǔ)上對(duì)每個(gè)模塊的復(fù)雜算法進(jìn)行了優(yōu)化，并提出了一種新的運(yùn)動(dòng)方向的擴(kuò)展方法，這對(duì)日后的游戲軟件開發(fā)提供了一種新的思路。

[1]王曉東.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2003.

[2]石正喜,張捍東.一種改進(jìn)的MM中文分詞算法[J].計(jì)算機(jī)與網(wǎng)絡(luò),2009(2):48-54.

[3]杜勤,秦前付.N皇后問題的啟發(fā)式算法探討[J].計(jì)算機(jī)與網(wǎng)絡(luò),2010,36(24):51-53.

[4]王維,趙高.打磚塊游戲的算法分析[J].電腦編程技巧與維護(hù),2011,7(16):9-10.

[5]劉娜,佟冶.淺析C語言快速排序算法的改進(jìn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2008(1):113-116.

[6]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2008.

[7]THOMAS H.C.Introduction to Algorithms[M].北京:機(jī)械工業(yè)出版社,2012.

[8]張德富,鄭捷敏.人機(jī)丈棋游戲算法研究[J].計(jì)算機(jī)工程與科學(xué),2008,30(11):48-49.

[9]HU Chun-hua.Dynamic services selection algorithm in Web services composition supporting cross-enterprises collaboration [J].J.Cent.South Univ.Technol,2009(16):270-274.

[10]LI Pan-chi,LI Shi-yong.Learning Algorithm and Application of Quantum BP Neuralnetworks based on Universal Quantum Gates[J].Journal of Systems Engineering and Electronics,2008,19(1):167-174.

Design on 2048 Algorithm Base on C++Language

YAN Guan-peng1YAN Zhuo-cheng2
(1 School of International Trade and Economics,Shandong University of Finance and Economics,Jinan Shandong 250014,China)
(2 School of Microelectronic and Solid-State Electronics,University of Electronic Science and Technology of China,Chengdu Sichuan 610054,China)

Aiming at the rules of 2048 game,this paper analyzes the algorithm characteristics of this game,briefly introduces the relevant functional requirements and the algorithm design.A new design scheme is proposed,which solves the problems of this design in the aspects of matrix data structure,movement algorithm and game end judgment,and the key technologies of implementing the coordinate calculation and extended operation in a queue way is described.The software tests show that the matrix order and the operation number limit the maximum value of block numerical value of design,the theoretical maximum value of four factorial matrixes is 65536,and the intelligent people can achieve 16384 while the average people can only achieve 2048.

2048;algorithm design;data structure;coordinate calculation;queue

TP301.6

A

1008-1739（2014）24-62-5

定稿日期：2014-11-26