首页 > 代码库 > 2048游戏回顾二:算法总结(移动、合并、动画等)

2048游戏回顾二:算法总结(移动、合并、动画等)

如果只是单纯的写一个2048游戏,让这个游戏可以玩的话,工作量还是蛮小的。不过,在这写工作中,你可能花时间最多的就是数字的移动与合并的算法了,如果没有做过,可能确实要花点时间来构思,所以,写完2048游戏以后,我希望能把它做个记录。

移动与合并的算法

比如说我们有如下一个界面:
技术分享
现在,玩家向左划,这个导致所有的数字向左移动,并且移动的过程中如果发生碰撞,会检查数字是不是可以合并。
我们的算法应该是通用的,不仅对于4*4模式,即便是针对3*3模式,n*n模式,它都应该是一样的。
那么怎么做呢?其实就两步:
第一步:把第一个空格和空格后面的第一个数字(如果有)交换。
第二步:交换后检查需不需要合并。
以此类推。
为了便于陈述,我们给图片做一个坐标:
技术分享
在这张图片中,按照我们说的,第一个空白和第一个数字交换,也就是把(2,C)和(3,C)交换,交换后检查能不能合并,如果能则合并,不过不能则不合并,这里显然可以合并,所以我们把他们合并为4.然后空白后面就没有数字了,算法结束。
因此,我们的算法必须记录第一个空白的位置和第一个数字的位置,那么我们用k记录空白,用j记录第一个数字,然后对于每一行,从左向右做这样的事情。
直接上代码吧,结合代码一说就会明白:
首先,我们的一个数字使用一个Number类来表述:

public class Number {
    public int mScores;
    public int mCurPosition;
    public int mBeforePosition;
    public boolean isNeedMove;
    public boolean isNeedCombine;
    public Number(int position,int scores){
        mScores = scores;
        mCurPosition = mBeforePosition = position;
        isNeedMove = false;
        isNeedCombine = false;
    }
    public void reset(){
        mScores = 0;
        isNeedMove = false;
        isNeedCombine = false;
    }
}

可见一个Number中有scores,也就是分数,当前的位置和之前的位置是用来计算动画的,我们需要把一个Number从之前的位置移动到当前的位置。
然后整个游戏使用一个Numbers类来表述:

public class Numbers {
    Number [][] mNumbers = new Number[Game2048StaticControl.gamePlayMode][Game2048StaticControl.gamePlayMode];
    public Numbers(){
        for(int i=0;i<Game2048StaticControl.gamePlayMode;i++){
            for(int j=0;j<Game2048StaticControl.gamePlayMode;j++){
                mNumbers[i][j] = new Number(0,0);
            }
        }
    }
    public Number getNumber(int x,int y){
        return mNumbers[x][y];
    }
    public Number [][] getNumbers (){
        return mNumbers;
    }
    public int getBlankCount(){
        int count = 0;
        for(int i=0;i<Game2048StaticControl.gamePlayMode;i++){
            for(int j=0;j<Game2048StaticControl.gamePlayMode;j++){
                if(mNumbers[i][j].mScores==0){
                    count++;
                }
            }
        }
        return count;
    }
    public int getPositonFromBlankCountTh(int blankTh){
        int count = 0;
        for(int i=0;i<Game2048StaticControl.gamePlayMode;i++){
            for(int j=0;j<Game2048StaticControl.gamePlayMode;j++){
                if(mNumbers[i][j].mScores==0){
                    if(count==blankTh){
                        return i*Game2048StaticControl.gamePlayMode+j;
                    }else {
                        count++;
                    }
                }
            }
        }
        return -1;
    }
    public void swapNumber(int position1,int position2){
        mNumbers[position1/Game2048StaticControl.gamePlayMode][position1%Game2048StaticControl.gamePlayMode].mCurPosition = position2;
        mNumbers[position1/Game2048StaticControl.gamePlayMode][position1%Game2048StaticControl.gamePlayMode].mBeforePosition = position1;
        mNumbers[position2/Game2048StaticControl.gamePlayMode][position2%Game2048StaticControl.gamePlayMode].mCurPosition = position1;
        mNumbers[position2/Game2048StaticControl.gamePlayMode][position2%Game2048StaticControl.gamePlayMode].mBeforePosition = position2;
        Number tem = mNumbers[position1/Game2048StaticControl.gamePlayMode][position1%Game2048StaticControl.gamePlayMode];
        mNumbers[position1/Game2048StaticControl.gamePlayMode][position1%Game2048StaticControl.gamePlayMode] = mNumbers[position2/Game2048StaticControl.gamePlayMode][position2%Game2048StaticControl.gamePlayMode];
        mNumbers[position2/Game2048StaticControl.gamePlayMode][position2%Game2048StaticControl.gamePlayMode] = tem;
    }
}

这个类的核心就是一个Number [n][n]的数组,n可以为任意值,因为我们的算法是通用的。

有了这个的概念以后,我们来看向左移动的算法,思想前面已经讲过了,直接看代码,结合代码非常容易理解。

   //return 0:do nothing
    //return 1:move
    //return 2:combine
    public int leftKeyDealAlgorithm(){
        int i, j, k;
        boolean isMoved = false;
        boolean isFinalMove = false;
        boolean isFinalCombie = false;
        for(i=0;i<Game2048StaticControl.gamePlayMode;i++){
            j=k=0;
            isMoved = false;
            while (true) {
                while (j<Game2048StaticControl.gamePlayMode && !isPosionHasNumber(i,j))
                    j++;
                if (j > Game2048StaticControl.gamePlayMode-1)
                    break;
                if (j > k){
                    isMoved = true;
                    isFinalMove = true;
                    Number number = getNumber(i,j);
                    number.isNeedMove = true;
                    number.isNeedCombine = false;
                    swapNumber(i*Game2048StaticControl.gamePlayMode+k,i*Game2048StaticControl.gamePlayMode+j);
                }
                if (k > 0 && getNumber(i,k).mScores==getNumber(i,k-1).mScores && !getNumber(i,k-1).isNeedCombine){
                    isFinalCombie = true;
                    Number numberk = getNumber(i,k);
                    Number numberkl = getNumber(i,k-1);
                    if(isMoved){
                        numberkl.mBeforePosition = numberk.mBeforePosition;
                    }else {
                        numberkl.mBeforePosition =  i*Game2048StaticControl.gamePlayMode+k;
                    }
                    numberkl.mCurPosition = i*Game2048StaticControl.gamePlayMode+k-1;
                    numberkl.isNeedMove = true;
                    numberkl.isNeedCombine = true;
                    numberkl.mScores <<=1;
                    updateCurScoresAndHistoryScores(numberkl.mScores);
                    numberk.reset();
                    numberk.mCurPosition = numberk.mBeforePosition = i*Game2048StaticControl.gamePlayMode+k;
                } else{
                    k++;
                }
                j++;
            }
        }
        return isFinalCombie?2:(isFinalMove?1:0);
    }

第一步:j=k=0;
第二步:找到第一个数字:

                while (j<Game2048StaticControl.gamePlayMode && !isPosionHasNumber(i,j))
                    j++;

第三步:如果j > k,那就意味这k这个位置的数字一定是空的,j这个位置的一定是第一个数字,所以就把他们交换。
第四步:判断是不是需要合并

if (k > 0 && getNumber(i,k).mScores==getNumber(i,k-1).mScores && !getNumber(i,k-1).isNeedCombine

判断的条件是k>0,因为是向前合并,所以合并至少是从第二个开始的,其次就是两个数字要相等,同时,已经合并了得数字不能再合并。
然后再做下一个循环,如此往复即可完成。

下面贴出其他三个方向的代码。

   public int rightKeyDealAlgorithm(){
        int i, j, k;
        boolean isMoved = false;
        boolean isFinalMove = false;
        boolean isFinalCombie = false;
        for(i=0;i<Game2048StaticControl.gamePlayMode;i++){
            j=k=Game2048StaticControl.gamePlayMode-1;
            isMoved = false;
            while (true) {
                while (j>-1 && !isPosionHasNumber(i,j))
                    j--;
                if (j < 0)
                    break;
                if (j < k){
                    isMoved = true;
                    isFinalMove = true;
                    Number number = getNumber(i,j);
                    number.isNeedMove = true;
                    number.isNeedCombine = false;
                    swapNumber(i*Game2048StaticControl.gamePlayMode+k,i*Game2048StaticControl.gamePlayMode+j);
                }
                if (k < Game2048StaticControl.gamePlayMode-1 && getNumber(i,k).mScores==getNumber(i,k+1).mScores && !getNumber(i,k+1).isNeedCombine){
                    isFinalCombie = true;
                    Number numberk = getNumber(i,k);
                    Number numberkl = getNumber(i,k+1);
                    if(isMoved){
                        numberkl.mBeforePosition = numberk.mBeforePosition;
                    }else {
                        numberkl.mBeforePosition =  i*Game2048StaticControl.gamePlayMode+k;
                    }
                    numberkl.mCurPosition = i*Game2048StaticControl.gamePlayMode+k+1;
                    numberkl.isNeedMove = true;
                    numberkl.isNeedCombine = true;
                    numberkl.mScores <<=1;
                    updateCurScoresAndHistoryScores(numberkl.mScores);
                    numberk.reset();
                    numberk.mCurPosition = numberk.mBeforePosition = i*Game2048StaticControl.gamePlayMode+k;
                } else{
                    k--;
                }
                j--;
            }
        }
        return isFinalCombie?2:(isFinalMove?1:0);
    }
    public int upKeyDealAlgorithm(){
        int i, j, k;
        boolean isMoved = false;
        boolean isFinalMove = false;
        boolean isFinalCombie = false;
        for(i=0;i<Game2048StaticControl.gamePlayMode;i++){
            j=k=0;
            isMoved = false;
            while (true) {
                while (j<Game2048StaticControl.gamePlayMode && !isPosionHasNumber(j,i))
                    j++;
                if (j > Game2048StaticControl.gamePlayMode-1)
                    break;
                if (j > k){
                    isMoved = true;
                    isFinalMove = true;
                    Number number = getNumber(j,i);
                    number.isNeedMove = true;
                    number.isNeedCombine = false;
                    swapNumber(k*Game2048StaticControl.gamePlayMode+i,j*Game2048StaticControl.gamePlayMode+i);
                }
                if (k > 0 && getNumber(k,i).mScores==getNumber(k-1,i).mScores && !getNumber(k-1,i).isNeedCombine){
                    isFinalCombie = true;
                    Number numberk = getNumber(k,i);
                    Number numberkl = getNumber(k-1,i);
                    if(isMoved){
                        numberkl.mBeforePosition = numberk.mBeforePosition;
                    }else {
                        numberkl.mBeforePosition =  k*Game2048StaticControl.gamePlayMode+i;
                    }
                    numberkl.mCurPosition = (k-1)*Game2048StaticControl.gamePlayMode+i;
                    numberkl.isNeedMove = true;
                    numberkl.isNeedCombine = true;
                    numberkl.mScores <<=1;
                    updateCurScoresAndHistoryScores(numberkl.mScores);
                    numberk.reset();
                    numberk.mCurPosition = numberk.mBeforePosition = k*Game2048StaticControl.gamePlayMode+i;
                } else{
                    k++;
                }
                j++;
            }
        }
        return isFinalCombie?2:(isFinalMove?1:0);
    }
    public int downKeyDealAlgorithm(){
        int i, j, k;
        boolean isMoved = false;
        boolean isFinalMove = false;
        boolean isFinalCombie = false;
        for(i=0;i<Game2048StaticControl.gamePlayMode;i++){
            j=k=Game2048StaticControl.gamePlayMode-1;
            isMoved = false;
            while (true) {
                while (j>-1 && !isPosionHasNumber(j,i))
                    j--;
                if (j < 0)
                    break;
                if (j < k){
                    isMoved = true;
                    isFinalMove = true;
                    Number number = getNumber(j,i);
                    number.isNeedMove = true;
                    number.isNeedCombine = false;
                    swapNumber(k*Game2048StaticControl.gamePlayMode+i,j*Game2048StaticControl.gamePlayMode+i);
                }
                if (k < Game2048StaticControl.gamePlayMode-1 && getNumber(k,i).mScores==getNumber(k+1,i).mScores && !getNumber(k+1,i).isNeedCombine){
                    isFinalCombie = true;
                    Number numberk = getNumber(k,i);
                    Number numberkl = getNumber(k+1,i);
                    if(isMoved){
                        numberkl.mBeforePosition = numberk.mBeforePosition;
                    }else {
                        numberkl.mBeforePosition =  k*Game2048StaticControl.gamePlayMode+i;
                    }
                    numberkl.mCurPosition = (k+1)*Game2048StaticControl.gamePlayMode+i;
                    numberkl.isNeedMove = true;
                    numberkl.isNeedCombine = true;
                    numberkl.mScores <<=1;
                    updateCurScoresAndHistoryScores(numberkl.mScores);
                    numberk.reset();
                    numberk.mCurPosition = numberk.mBeforePosition = k*Game2048StaticControl.gamePlayMode+i;
                } else{
                    k--;
                }
                j--;
            }
        }
        return isFinalCombie?2:(isFinalMove?1:0);
    }

动画

计算结束以后,我们需要使用动画移动和合并数字,因为都是直线运动,所以动画并不复杂,想想我们的Number类,计算动画只需要两个变量,一个之前的位置,一个是当前的位置。
我们可以理一下思路:当用户需要向左移动时:

                    case Game2048StaticControl.DIRECT_LEFT:{
                        mNumberQueue.pushItem(mGAM.getmNumbers());
                        int ret =  mGAM.leftKeyDealAlgorithm();
                        if (ret>0){
                            startAnimation(mHolder,mPaint,Game2048StaticControl.DIRECT_LEFT);
                            mGAM.updateNumbers();
                            doDrawGameSurface();
                            sendEmptyMessage(Game2048StaticControl.GENERATE_NUMBER);
                            playSoundEffect(ret);
                        }
                        break;
                    }

我们需要做如下几步:
第一步:保存当前的游戏,用于反悔的时候回退。mNumberQueue.pushItem(mGAM.getmNumbers())
第二步:计算移动与合并
mGAM.leftKeyDealAlgorithm();
第三步:使用动画移动和合并数字
startAnimation(mHolder,mPaint,Game2048StaticControl.DIRECT_LEFT);
第四步:生成一个新的数字
sendEmptyMessage(Game2048StaticControl.GENERATE_NUMBER);
通过发送消息来实现,具体的实现在消息的处理代码中,这很简单,这里暂不展开。
下面看一个startAnimation方法。
startAnimation定义如下:

    public void startAnimation(SurfaceHolder holder,Paint paint,int direct){
        int count = 0;
        RectF rectF = new RectF();
        while (count++<Game2048StaticControl.ANIMATION_MOVE_STEP) {
            Canvas canvas = holder.lockCanvas();
            mDrawTools.initSurfaceBg(canvas, paint);
            mDrawTools.drawSurfaceMap(canvas, paint);
            mDrawTools.drawSurfaceMapAndNumbersWhoIsNeedCombine(canvas,paint);
            for (int i = 0; i < Game2048StaticControl.gamePlayMode; i++) {
                for (int j = 0; j < Game2048StaticControl.gamePlayMode; j++) {
                    mGAM.aniInsertValue(i, j, count, Game2048StaticControl.ANIMATION_MOVE_STEP,direct,rectF);
                    if(rectF != null && mGAM.isPosionHasNumber(i,j) && mGAM.getNumber(i,j).isNeedMove){
                        mDrawTools.drawNumberByRectF(i,j,canvas,paint,rectF);
                    }
                }
            }
            holder.unlockCanvasAndPost(canvas);
        }
    }

就是对每一个Number,使用 mGAM.aniInsertValue方法来计算它的坐标:

  public void aniInsertValue(int x,int y,int count,int insertCount,int direct,RectF rectF){
        Number number = getNumber(x,y);
        if(number.mCurPosition ==  number.mBeforePosition){
            return;
        }
        float xDiffPixels = Game2048StaticControl.GameNumberViewPosition[number.mCurPosition/Game2048StaticControl.gamePlayMode]
                [number.mCurPosition%Game2048StaticControl.gamePlayMode].left
                -Game2048StaticControl.GameNumberViewPosition[number.mBeforePosition/Game2048StaticControl.gamePlayMode]
                [number.mBeforePosition%Game2048StaticControl.gamePlayMode].left;
        float yDiffPixels = Game2048StaticControl.GameNumberViewPosition[number.mCurPosition/Game2048StaticControl.gamePlayMode]
                [number.mCurPosition%Game2048StaticControl.gamePlayMode].top
                -Game2048StaticControl.GameNumberViewPosition[number.mBeforePosition/Game2048StaticControl.gamePlayMode]
                [number.mBeforePosition%Game2048StaticControl.gamePlayMode].top;
        xDiffPixels = Math.abs(xDiffPixels);
        yDiffPixels = Math.abs(yDiffPixels);
        float xStep = xDiffPixels/insertCount;
        float yStep = yDiffPixels/insertCount;
        float xNewPosition = Game2048StaticControl.GameNumberViewPosition[number.mCurPosition/Game2048StaticControl.gamePlayMode]
                [number.mCurPosition%Game2048StaticControl.gamePlayMode].left;
        float yNewPosition = Game2048StaticControl.GameNumberViewPosition[number.mCurPosition/Game2048StaticControl.gamePlayMode]
                [number.mCurPosition%Game2048StaticControl.gamePlayMode].top;;
        switch (direct){
            case DIRECT_UP:{
                yNewPosition = Game2048StaticControl.GameNumberViewPosition[number.mBeforePosition/Game2048StaticControl.gamePlayMode]
                        [number.mBeforePosition%Game2048StaticControl.gamePlayMode].top
                        - yStep*count;
                break;
            }
            case DIRECT_DOWN:{
                yNewPosition = Game2048StaticControl.GameNumberViewPosition[number.mBeforePosition/Game2048StaticControl.gamePlayMode]
                        [number.mBeforePosition%Game2048StaticControl.gamePlayMode].top
                                + yStep*count;
                break;
            }
            case DIRECT_LEFT:{
                xNewPosition = Game2048StaticControl.GameNumberViewPosition[number.mBeforePosition/Game2048StaticControl.gamePlayMode]
                        [number.mBeforePosition%Game2048StaticControl.gamePlayMode].left
                        - xStep*count;
                break;
            }
            case DIRECT_RIGHT:{
                xNewPosition = Game2048StaticControl.GameNumberViewPosition[number.mBeforePosition/Game2048StaticControl.gamePlayMode]
                        [number.mBeforePosition%Game2048StaticControl.gamePlayMode].left
                        + xStep*count;
                break;
            }
            default:break;
        }
        rectF.set(xNewPosition,yNewPosition,xNewPosition+Game2048StaticControl.gameNumberViewLength
                ,yNewPosition+Game2048StaticControl.gameNumberViewLength);
    }

计算的过程正对上下左右各不相同,原理非常简单:
技术分享
原理就是在途中的花点的地方绘制一下数字就好了。也就是所谓的线性插值法。

在随机位置随机生成2或者4

生成2或者4就太简单了,随机位置怎么计算呢?这里要注意实在空白方格的随机位置哦,因此首先要获取当前有多少个空格:

    public int getBlankCount(){
        return mNumbers.getBlankCount();
    }

进一步:

    public int getBlankCount(){
        int count = 0;
        for(int i=0;i<Game2048StaticControl.gamePlayMode;i++){
            for(int j=0;j<Game2048StaticControl.gamePlayMode;j++){
                if(mNumbers[i][j].mScores==0){
                    count++;
                }
            }
        }
        return count;
    }

比如说当前有7个空白处,那么就只能生7以内的随机数n,然后 把它插到第n个空白处。
插入方法如下:

    public int  setOneRandomNumberInRandomPosition(){
        int scores = Game2048Algorithm.getRandom2Or4();
        int blankCount = getBlankCount();
        Log.d(TAG,"blankCount:"+blankCount);
        int blankTh = 0;
        if(blankCount<=0){
            return -1;
        }else{
            blankTh = Game2048Algorithm.getRandomPosition(blankCount);
        }
        int position = mNumbers.getPositonFromBlankCountTh(blankTh);
        if (position<0){
            Log.d(TAG,"getPositonFromBlankCountTh return error");
            return -1;
        }
        Number num = mNumbers.getNumber(position/Game2048StaticControl.gamePlayMode,position%Game2048StaticControl.gamePlayMode);
        num.mScores = scores;
        num.mBeforePosition = num.mCurPosition = position;
        num.isNeedCombine = num.isNeedMove = false;
        return position;
    }

检测游戏失败

检测游戏的失败也有一个通用的方式:

   public boolean checkGameOver(){
        Log.d(TAG,"checkGameOver");
        for (int i = 0; i < Game2048StaticControl.gamePlayMode; i++)
        {
            for (int j = 0; j < Game2048StaticControl.gamePlayMode; j++)
            {
                if (j != Game2048StaticControl.gamePlayMode-1 && getNumber(i,j).mScores == getNumber(i,j+1).mScores)
                    return false;
                if (i != Game2048StaticControl.gamePlayMode-1 && getNumber(i,j).mScores == getNumber(i+1,j).mScores)
                    return false;
            }
        }
        if (mListener!=null){
            mListener.onGameOver();
        }
        return true;
    }

算法的核心思想就是一定要对每一个数字对比它的前后左右。只要发现有相等的就认为可以继续。当然,判断的前提的空白格子的数量为0。

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

    2048游戏回顾二:算法总结(移动、合并、动画等)