瓦片合并算法2048游戏 [英] Tile merging algorithm 2048 game

问题描述

我试图用C重新创建游戏2048，但是我无法获得将图块移动或合并在一起以正常运行的算法。
在原始的2048游戏中，您将像这样移动瓷砖：

  2 | 2 | 4 | 4 4 | 8 | | 
 --- +-+ --- + --- *向左滑动*-> --- + --- + --- + --- 
 8 | | 8 | 16 | | | 
  

因此，两个相同的图块可以合并为一个两倍大小的图块。我的版本几乎是相同的，但是我不使用数字，而是使用合并时递增一个的字符，因此 [A | A] 将合并为 [B] ，等等。我这样做是为了不必处理各种大小的图块。

因此，我的电路板存储为我称为网格的结构中的4 * 4 char数组（我知道可能有点多余）

  typedef结构网格{
个字符块[4] [4]； 
}网格； 
  

我试图使算法向上，向下，向左和向右移动和合并，但它们并没有

  void pushLeft（Grid * grid）
 {
 in i，j， k; 
 for（i = 0; i< 4; i ++）//行号i 
 {
 for（j = 1; j< 4; j ++）//列号j 
 {
 if（grid-> tiles [i] [j]！=''）// tile不为空
 {
 int flag = 1; //防止一次合并多个级别的标志
 //从第k列开始，将图块尽可能向左推
 for（k = j; k> 0; k- -）
 {
 if（grid-> tiles [i] [k-1] ==''）//邻居块为空
 {
 grid-> tile [i] [k-1] =网格-> tiles [i] [k]; 
 grid-> tiles [i] [k] =’； 
} 
 else if（grid-> tiles [i] [k-1] == grid-> tiles [i] [k]&&标志）//邻居等于
 {
 grid-> tiles [i] [k-1] ++; 
 grid-> tiles [i] [k] =’； 
标志= 0; 
} 
 else //无法推送或合并
 {
 flag = 1; 
休息时间； 
} 
} 
} 
} //与行完成
} 
} 
 
 void pushRight（Grid * grid） 
 {
 int i，j，k; 
 for（i = 0; i< 4; i ++）//行数i 
 {
 for（j = 2; j> = 0; j--）//列数字j 
 {
 if（grid-> tiles [i] [j]！=''）// tile不为空
 {
 int flag = 1; //标记以防止一次合并多个级别
 //从第k列开始，将图块尽可能向右推
 for（k = j; k <3; k ++） 
 {
 if（grid-> tiles [i] [k + 1] ==''）//邻居块为空
 {
 grid-> tiles [ i] [k + 1] =网格-> tiles [i] [k]; 
 grid-> tiles [i] [k] =’； 
} 
 else if（grid-> tiles [i] [k + 1] == grid-> tiles [i] [k]&&标志）//邻居等于
 {
 grid-> tiles [i] [k + 1] ++; 
 grid-> tiles [i] [k] =’； 
标志= 0; 
} 
 else //无法推送或合并
 {
 flag = 1; 
休息时间； 
} 
} 
} 
} //与行完成
} 
} 
 
 void pushUp（Grid * grid） 
 {
 int i，j，k; 
 for（i = 0; i< 4; i ++）//列号i 
 {
 for（j = 1; j< 4; j ++）//行号j 
 {
 if（grid-> tiles [j] [i]！=''）// tile不为空
 {
 int flag = 1; //标志以防止一次合并多个级别
 //从第k行开始，将图块尽可能向上推
 for（k = j; k> 0; k--） 
 {
 if（grid-> tiles [k-1] [i] ==''）//邻居区块为空
 {
 grid-> tiles [ k-1] [i] =网格-> tiles [i] [k]； 
 grid-> tiles [k] [i] =‘’； 
} 
 else if（grid-> tiles [k-1] [i] == grid-> tiles [i] [k]&&标志）//邻居等于
 {
 grid-> tiles [k-1] [i] ++; 
 grid-> tiles [k] [i] =‘’； 
标志= 0; 
} 
 else //无法推送或合并
 {
 flag = 1; 
休息时间； 
} 
} 
} 
} //与列
一起完成} 
} 
 
 void pushDown（Grid * grid） 
 {
 int i，j，k; 
 for（i = 0; i< 4; i ++）//列号i 
 {
 for（j = 2; j> = 0; j--）//行数字j 
 {
 if（grid-> tiles [j] [i]！=''）// tile不为空
 {
 int flag = 1; //标志以防止一次合并多个级别
 //从第k行开始，将图块尽可能向下推
 for（k = j; k <3; k ++）
 {
 if（grid-> tiles [k + 1] [i] ==''）//邻居块为空
 {
 grid-> tiles [k + 1] [i] =网格-> tiles [i] [k]； 
 grid-> tiles [k] [i] =‘’； 
} 
 else if（grid-> tiles [k + 1] [i] == grid-> tiles [i] [k]&&标志）//邻居等于
 {
 grid-> tiles [k + 1] [i] ++; 
 grid-> tiles [k] [i] =‘’； 
标志= 0; 
} 
 else //无法推送或合并
 {
 flag = 1; 
休息时间； 
} 
} 
} 
} //用列
} 
} 
   
 
 
我用一些硬编码的测试数据测试了这些算法。将图块向左推的算法似乎正常工作。 pushRight几乎可以工作，但是它同时合并了两个级别，因此 [B | A | A] 合并为 [C] ，但应该合并为 [B | B] 。
 
 
 
 pushUp似乎总是在擦整个木板上有空的瓷砖（空间）。 
 pushDows似乎正在除去一些瓷砖。
 
 
 
有人看到这个问题或知道解决方法吗？我曾考虑过使用递归算法，但是我无法解决这个问题。
解决方案
我个人会破坏分为两步，因为向左滑动和向右滑动实际上与图块组合在功能上相同。唯一的区别是剩余的图块根据方向聚集在左侧或右侧。
 
 
 
下面是一种快速算法，用一个新的图块替换两个图块。我从左到右扫描，并用新的图块替换左图块，将右图块置零，然后确保从比较中排除该新图块：
  typedef结构网格{
 char tile [4] [4]; 
}网格； 
 
 void destroyHoriz（Grid * g）
 {
 int row，col，col2; 
 for（row = 0; row< 4; row ++）
 {
 for（col = 0; col< 4; col ++）
 {
 if（g- > tiles [row] [col]）
 {
 for（col2 = col + 1; col2 <4; col2 ++）
 {
如果（g-> tiles [ row] [col2]）
 {
 if（g-> tiles [row] [col] == g-> tiles [row] [col2]）
 {
 g-> tiles [row] [col ++] * = 2; 
 g-> tiles [row] [col2] = 0; 
} 
休息； 
} 
} 
} 
} 
} 
} 
 
 void showGrid（Grid * g）
 { 
 int行，col； 
代表（行= 0;行< 4;行++）
代表（col = 0; col< 4; col ++）
 printf（％4d％c，
 g -> tiles [row] [col]，
 col == 3？'\n'：''）; 
 printf（ \n）; 
} 
 
 int main（）
 {
网格g = {{{2,2,4,4，
 8,0,8,0 ，
 8,8,8,4，
 2,2,2,2}}； 
 
 showGrid（&g）; 
消除Horiz（&g）; 
 showGrid（&g）; 
 
系统（暂停）； 
返回0； 
} 
  
此输出：
  2 2 4 4 
 8 0 8 0 
 8 8 8 4 
 2 2 2 2 
 
 4 0 8 0 
 16 0 0 0 
 16 0 8 4 
 4 0 4 0 
  
在此之后，可以执行一个简单的压缩步骤，或者将其实时输出到第二个缓冲区，或者使用后者。减少重复。
 
I am trying to recreate the game 2048 in C, but I can't get the algorithms to move or merge tiles together to function properly.
In the original 2048 game you would move tiles together like this:
 2 | 2 | 4 | 4                             4 | 8 |   |   
---+---+---+---  *swipes to the left* ->  ---+---+---+---
 8 |   | 8 |                               16|   |   |
So two tiles that are the same can merge into one tile that is twice the size. My version is almost the same, but instead of using numbers I use characters that increment by one when they merge, so[A|A] would merge to [B], etc. I did that only to not have to deal with varying size tiles.

So my board is stored as a 4*4 char array inside a struct I called grid (I know probably a bit redundant)
typedef struct grid {
    char tiles[4][4];
} Grid;
I have tried to make algorithms to move and merge up, down, left and right, but they don't work properly.
void pushLeft(Grid * grid)
{
    int i, j, k;
    for(i = 0; i < 4; i++) //Row number i
    {
        for(j = 1; j < 4; j++) //Column number j
        {
            if(grid->tiles[i][j] != ' ') //tile is not empty
            {
                int flag = 1; //flag to prevent merging more than one level at a time
                //Starting on column k, push tile as far to the left as possible
                for(k = j; k > 0; k--)
                {
                    if(grid->tiles[i][k-1] == ' ') //neighbor tile is empty
                    {
                        grid->tiles[i][k-1] = grid->tiles[i][k];
                        grid->tiles[i][k] = ' ';
                    }
                    else if(grid->tiles[i][k-1] == grid->tiles[i][k] && flag) //neighbor equals
                    {
                        grid->tiles[i][k-1]++;
                        grid->tiles[i][k] = ' ';
                        flag = 0;
                    }
                    else //Can't push or merge
                    {
                        flag = 1;
                        break;
                    }
                }
            }
        } // Done with row
    }
}

void pushRight(Grid * grid)
{
    int i, j, k;
    for(i = 0; i < 4; i++) //Row number i
    {
        for(j = 2; j >= 0; j--) //Column number j
        {
            if(grid->tiles[i][j] != ' ') //tile is not empty
            {
                int flag = 1; //flag to prevent merging more than one level at a time
                //Starting on column k, push tile as far to the right as possible
                for(k = j; k < 3; k++)
                {
                    if(grid->tiles[i][k+1] == ' ') //neighbor tile is empty
                    {
                        grid->tiles[i][k+1] = grid->tiles[i][k];
                        grid->tiles[i][k] = ' ';
                    }
                    else if(grid->tiles[i][k+1] == grid->tiles[i][k] && flag) //neighbor equals
                    {
                        grid->tiles[i][k+1]++;
                        grid->tiles[i][k] = ' ';
                        flag = 0;
                    }
                    else //Can't push or merge
                    {
                        flag = 1;
                        break;
                    }
                }
            }
        } // Done with row
    }
}

void pushUp(Grid * grid)
{
    int i, j, k;
    for(i = 0; i < 4; i++) //Column number i
    {
        for(j = 1; j < 4; j++) //Row number j
        {
            if(grid->tiles[j][i] != ' ') //tile is not empty
            {
                int flag = 1; //flag to prevent merging more than one level at a time
                //Starting on row k, push tile as far upwards as possible
                for(k = j; k > 0; k--)
                {
                    if(grid->tiles[k-1][i] == ' ') //neighbor tile is empty
                    {
                        grid->tiles[k-1][i] = grid->tiles[i][k];
                        grid->tiles[k][i] = ' ';
                    }
                    else if(grid->tiles[k-1][i] == grid->tiles[i][k] && flag) //neighbor equals
                    {
                        grid->tiles[k-1][i]++;
                        grid->tiles[k][i] = ' ';
                        flag = 0;
                    }
                    else //Can't push or merge
                    {
                        flag = 1;
                        break;
                    }
                }
            }
        } // Done with column
    }
}

void pushDown(Grid * grid)
{
    int i, j, k;
    for(i = 0; i < 4; i++) //Column number i
    {
        for(j = 2; j >= 0; j--) //Row number j
        {
            if(grid->tiles[j][i] != ' ') //tile is not empty
            {
                int flag = 1; //flag to prevent merging more than one level at a time
                //Starting on row k, push tile as far down as possible
                for(k = j; k < 3; k++)
                {
                    if(grid->tiles[k+1][i] == ' ') //neighbor tile is empty
                    {
                        grid->tiles[k+1][i] = grid->tiles[i][k];
                        grid->tiles[k][i] = ' ';
                    }
                    else if(grid->tiles[k+1][i] == grid->tiles[i][k] && flag) //neighbor equals
                    {
                        grid->tiles[k+1][i]++;
                        grid->tiles[k][i] = ' ';
                        flag = 0;
                    }
                    else //Can't push or merge
                    {
                        flag = 1;
                        break;
                    }
                }
            }
        } // Done with column
    }
}
I tested these algorithms with some hardcoded testdata. The algorithm to push the tiles to the left seems to be working correctly. pushRight almost works, but it merges two levels at the same time, so  [B|A|A] merges into [C] but should merge into [B|B].

pushUp seems to be almost always just wiping the entire board with empty tiles (spaces).
pushDows seems to be removing some tiles.

Does anyone see the problem or know a way to do this? I have thought about using recursive algorithms, but I just can't wrap my head around it.
解决方案
I would personally break the swipe into two steps as the swipe left and swipe right are actually functionally the same regarding tile combination. The only difference is that the remaining tiles are bunched to either the left or the right depending on direction.

Below is a quick algorithm to replace two tiles with the a new one. I scan left->right and replace the left tile with the new tile, zero the right tile and then make sure I exclude this new tile from comparison:
typedef struct grid {
    char tiles[4][4];
} Grid;

void eliminateHoriz (Grid* g)
{
    int row, col, col2;
    for (row=0; row<4; row++)
    {
        for (col=0; col<4; col++)
        {
            if (g->tiles[row][col])
            {
                for (col2=col+1; col2<4; col2++)
                {
                    if (g->tiles[row][col2])
                    {
                        if (g->tiles[row][col] == g->tiles[row][col2])
                        {
                            g->tiles[row][col++] *= 2;
                            g->tiles[row][col2] = 0;
                        }
                        break;
                    }
                }
            }
        }
    }
}

void showGrid (Grid* g)
{
    int row, col;
    for (row=0; row<4; row++)
        for (col=0; col<4; col++)
            printf ("%4d%c",
                g->tiles[row][col],
                col == 3 ? '\n' : ' ');
    printf ("\n");
}

int main() 
{
    Grid g = {{2,2,4,4, 
               8,0,8,0,
               8,8,8,4, 
               2,2,2,2}};

    showGrid (&g);
    eliminateHoriz (&g);
    showGrid (&g);

    system ("pause");
    return 0;
}
Output of this:
   2    2    4    4
   8    0    8    0
   8    8    8    4
   2    2    2    2

   4    0    8    0
  16    0    0    0
  16    0    8    4
   4    0    4    0
After this a simple compaction step could be made, or output realtime to a second buffer, or which ever. Less duplication.

                        
这篇关于瓦片合并算法2048游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！