瓦片合并算法2048游戏

Question

我正在尝试用 C 重新创建游戏 2048，但我无法让算法将图块移动或合并在一起以正常运行。在最初的 2048 游戏中，您可以像这样将瓷砖移动到一起：

 2 | 2 | 4 | 4                             4 | 8 |   |   
---+---+---+---  *swipes to the left* ->  ---+---+---+---
 8 |   | 8 |                               16|   |   |

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

所以我的电路板被存储为一个 4*4 字符数组，我称之为 grid（我知道可能有点多余）

typedef struct grid {
    char tiles[4][4];
} Grid;

我试图让算法向上、向下、向左和向右移动和合并，但它们无法正常工作。

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
    }
}

我用一些硬编码的测试数据测试了这些算法。将图块向左推的算法似乎工作正常。pushRight 几乎有效，但它同时合并了两个级别，因此 [B|A|A]合并到[C]但应该合并到[B|B].

pushUp 似乎几乎总是用空瓷砖（空格）擦拭整个板。pushDows 似乎正在删除一些瓷砖。

有没有人看到这个问题或知道如何做到这一点？我曾想过使用递归算法，但我就是无法理解它。

Answer 1

我个人会将滑动分为两个步骤，因为就图块组合而言，向左滑动和向右滑动实际上在功能上是相同的。唯一的区别是剩余的瓷砖根据方向聚集到左侧或右侧。

下面是一种用新瓷砖替换两个瓷砖的快速算法。我从左到右扫描并用新图块替换左侧图块，将右侧图块归零，然后确保从比较中排除这个新图块：

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;
}

输出：

   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

此后，可以进行简单的压缩步骤，或者实时输出到第二个缓冲区，或者等等。减少重复。