Алгоритм слияния плитки 2048 игра

Question

Я пытаюсь воссоздать игру 2048 в C, но я не могу заставить алгоритмы перемещать или объединять плитки вместе, чтобы нормально функционировать. В оригинальной игре 2048 вы бы переместить плитки вместе, как это:

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

So две плитки, которые являются такими же, можно объединить в одну плитку, которая в два раза больше. Моя версия почти то же самое, но вместо использования чисел я использую символы, которые увеличиваются на единицу при слиянии, поэтому [A|A] будет сливаться с [B] и т. Д. Я сделал это, чтобы не иметь дело с плитами различного размера.

Так что мой совет хранится как массив символов 4 * 4 внутри структуры я назвал сетку (вероятно, я знаю немного избыточен)

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

Я протестировал эти алгоритмы с помощью некоторых hardcoded testdata. Алгоритм, чтобы нажимать плитки слева, кажется, работает правильно. 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 

После этого можно было бы сделать простой шаг уплотнения или вывести в реальном времени второй буфер или когда-либо. Меньшее дублирование.

Answer 2

Я только сделал случай нажатия линий влево, но это тот же метод для каждого направления.Я взял код ответа и изменил его; посмотрите:

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

/* Functions prototypes */ 

void pushLeft(Grid* grid); 
void showGrid (Grid* g); 
void find_great_tile(Grid* grid); 

/* Main function */ 

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

    /* 

    The sequence is: 

    --> Show the grid 
    --> PushLeft 
    --> Find great tile 
    --> PushLeft 
    --> Show the grid 

    */ 

    printf("\n\n\n\n"); 
    showGrid (&g); 
    printf("\n\n\n\n"); 
    pushLeft(&g); 
    showGrid (&g); 
    printf("\n\n\n\n"); 
    find_great_tile(&g); 
    showGrid(&g); 
    printf("\n\n\n\n"); 
    pushLeft(&g); 
    showGrid(&g); 
    printf("\n\n\n\n"); 

    return 0; 
} 

/* Functions definitions */ 

void pushLeft(Grid* grid){ 

    int row, col, col2; 

    for (row = 0; row < 4; row++) 
    { 
     for (col = 0; col < 4; col++) 
     { 
      if (!grid->tiles[row][col]) 
      { 
       for (col2 = col+1; col2 < 4; col2++) 
       { 
        if (grid->tiles[row][col2]) 
        { 

         /* 
         if (grid->tiles[row][col] == grid->tiles[row][col2]) 
         { 
          grid->tiles[row][col++] *= 2; 
          grid->tiles[row][col2] = 0; 
         } 

         break; 
         */ 

         grid->tiles[row][col] = grid->tiles[row][col2]; 
         grid->tiles[row][col2] = 0; 

         break; 
        } 
       } 
      } 
     } 
    } 
} 

void showGrid (Grid* grid){ 

    int row, col; 

     for(row = 0; row < 4; row++){ 

      fprintf(stdout, "\t\t  |"); 

      for(col = 0; col < 4; col++) 
      { 

      /* 
      In case there's any number in the matrix, it will print those numbers, otherwise, it'll print a space (it is the alternative of putting a 0) 
      */ 

       if(grid->tiles[row][col]) 
       { 
        printf("%4d |", grid->tiles[row][col]); 
       }else 
        printf("%4c |", ' '); 
      } 

      fprintf(stdout, "\n\n"); 
     } 
} 

void find_great_tile(Grid* grid){ 

    int row, col, col2; 

    for(row = 0; row < 4; row++) 
    { 
     for(col = 0; col < 4; col++) 
     { 
      if(grid->tiles[row][col]) 
      { 
       col2 = col+1; 

       if(grid->tiles[row][col2]) 
       { 
        if(grid->tiles[row][col] == grid->tiles[row][col2]) 
        { 
         grid->tiles[row][col++] *= 2; 

         grid->tiles[row][col2] = 0; 
        } 
       } 
      } 
     } 
    } 
} 

Выход из этого:

  | 4 | 2 | 2 | 8 | 

     | 2 | 8 | 2 | 2 | 

     | 16 | 2 |  | 2 | 

     | 128 | 128 | 64 | 64 | 





     | 4 | 2 | 2 | 8 | 

     | 2 | 8 | 2 | 2 | 

     | 16 | 2 | 2 |  | 

     | 128 | 128 | 64 | 64 | 





     | 4 | 4 |  | 8 | 

     | 2 | 8 | 4 |  | 

     | 16 | 4 |  |  | 

     | 256 |  | 128 |  | 





     | 4 | 4 | 8 |  | 

     | 2 | 8 | 4 |  | 

     | 16 | 4 |  |  | 

     | 256 | 128 |  |  | 

Конечно, вы можете сжимать шаги делать:

-> PushLeft

-> FindGreatTile

-> PushLeft