首页 > 代码库 > 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。
2048游戏回顾二:算法总结(移动、合并、动画等)