基于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