基于C++語言的2048算法設計

顏冠鵬 顏卓程

（1 山東財經大學國際貿易學院山東濟南 250014）

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

基于C++語言的2048算法設計

顏冠鵬1顏卓程2

（1 山東財經大學國際貿易學院山東濟南 250014）

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

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

2048 算法設計 數據結構 坐標運算 隊列

1 引言

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

2 總體設計

2.1 功能需求

2048游戲一般由以下幾個模塊來構成：①矩陣方塊；②控制模塊；③計算模塊；④輸出模塊。每個模塊來實現2048游戲的各項功能，具體如下：方向移動、方塊合并、記錄當前數據和輸出計分結果等。

2.2 算法設計

根據2048游戲算法的功能需求和功能模塊，具體的算法設計如圖1所示。

圖1 2048游戲算法設計圖

3 需解決的問題

需解決的問題包括方陣的數據結構、隨機方塊的生成、運動算法的設計和游戲結束的判斷，其主要體現在控制和計算模塊。

3.1 方陣的數據結構

方陣為一個的矩陣[6]，該矩陣需要一個長度為的二維數組來構建，定義該數組為，記為式。

3.2 初始隨機方塊的生成

通過觀察發現，該游戲開始會在矩陣內的任意位置生成數值為2的數。

3.3 運動的算法設計

3.3.1 模塊設計

整個運動操作分3個模塊進行，包括移動模塊、歸并模塊和隨機數生成模塊，具體結構如圖2所示。

圖2 模塊設計說明圖

移動模塊用來執行在整個矩陣按選定方向整體移動的功能，歸并模塊實現了相鄰方塊按該方向的合并，而隨機數生成模塊完成了在矩陣任意空位置生成值為2的方塊，具體見式⑵。

3.3.2 移動設計

當進行向某個方向的操作運動時，可采用一種交換排序[7]的算法來實現該操作。以向右操作為例，首先將矩陣按行劃分為n個有序數列：

然后分別對每個序列進行移動操作。一次移動操作具體分4步：

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

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

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

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

圖3 單個序列向右移動操作示例圖

以向右移動為例，代碼如rightmove所示。

3.3.3 歸并設計

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

圖4 單個序列向右歸并操作示例圖

以向右歸并為例，代碼實現如rightmerge。

3.3.4 移動中的隨機數生成

當完成了移動和歸并操作后，構造randomcreat模塊，可實現在矩陣任意空位置生成值為的2方塊的功能。

3.4 游戲結束判斷

當矩陣在上、下、左和右4個方向的運動操作均無效時，游戲結束。經分析得，游戲結束必須滿足以下2個條件：

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

4 關鍵技術

關鍵技術主要包括以隊列[9]的方式進行坐標運算和操作擴展。采用隊列方式可以減少編程的復雜度，方便進行分布式計算[10]，加快求解速度。同時運動操作方式的多樣性也大幅度增加。

4.1 采用隊列的方式進行坐標運算

由于4個方向的運動方式并不相同，在進行重復編寫時，錯誤率高且繁瑣，故考慮以隊列的方式，先將矩陣依照操作的方向劃分為n個有序數列。

然后對每個有序數列Qi，將其中每個點的橫坐標和縱坐標依次加入隊列a；再以隊列所存儲的點的橫縱坐標為基礎，進行運動操作，設a為記錄點坐標的記錄型數組，a.x記錄橫坐標，a.y記錄縱坐標，以向右運動為例，a隊列值如圖5所示。

圖5 向右運動坐標運算示例圖

這樣運動的偽代碼就不用按不同方向書寫了，程序所實現運動的方向只與a隊列的點坐標次序有關，偽代碼的解釋如moveandmerge所示。

在進行向右運動操作時，只需在以隊列為構架的運動模塊的基礎上，附加一個給a隊列向右賦值的模塊即可，實現也相對容易。附設l為a隊列的隊尾指針，順序遍歷有序數列時，將有序數列的點依次賦值到a隊列的隊尾，并將隊尾指針l后移一位，具體偽代碼如right所示。

4.2 運用隊列進行更多方式的操作

在原有運動方向的基礎上，對其進行合并和擴展，就能寫出更多新穎的操作，像左上、右下、左下和右上等操作，以"右下"為例，具體如圖6所示。

圖6 右下運動坐標運算示例圖

5 性能測試結果分析

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

6 結束語

經過對整個2048算法的設計與實現，在原有的基礎上對每個模塊的復雜算法進行了優化，并提出了一種新的運動方向的擴展方法，這對日后的游戲軟件開發提供了一種新的思路。

[1]王曉東.算法設計與分析[M].北京:清華大學出版社,2003.

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

[3]杜勤,秦前付.N皇后問題的啟發式算法探討[J].計算機與網絡,2010,36(24):51-53.

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

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

[6]嚴蔚敏,吳偉民.數據結構[M].北京:清華大學出版社,2008.

[7]THOMAS H.C.Introduction to Algorithms[M].北京:機械工業出版社,2012.

[8]張德富,鄭捷敏.人機丈棋游戲算法研究[J].計算機工程與科學,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