title: Tile merging algorithm 2048 game
body: <p>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:</p>
  
  <pre><code> 2 | 2 | 4 | 4                             4 | 8 |   |   
  ---+---+---+---  *swipes to the left* -&gt;  ---+---+---+---
   8 |   | 8 |                               16|   |   |
  </code></pre>
  
  <p>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<code>[A|A]</code> would merge to <code>[B]</code>, etc. I did that only to not have to deal with varying size tiles.</p>
  
  <p>So my board is stored as a 4*4 char array inside a struct I called grid (I know probably a bit redundant)</p>
  
  <pre><code>typedef struct grid {
      char tiles[4][4];
  } Grid;
  </code></pre>
  
  <p>I have tried to make algorithms to move and merge up, down, left and right, but they don't work properly.</p>
  
  <pre><code>void pushLeft(Grid * grid)
  {
      int i, j, k;
      for(i = 0; i &lt; 4; i++) //Row number i
      {
          for(j = 1; j &lt; 4; j++) //Column number j
          {
              if(grid-&gt;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 &gt; 0; k--)
                  {
                      if(grid-&gt;tiles[i][k-1] == ' ') //neighbor tile is empty
                      {
                          grid-&gt;tiles[i][k-1] = grid-&gt;tiles[i][k];
                          grid-&gt;tiles[i][k] = ' ';
                      }
                      else if(grid-&gt;tiles[i][k-1] == grid-&gt;tiles[i][k] &amp;&amp; flag) //neighbor equals
                      {
                          grid-&gt;tiles[i][k-1]++;
                          grid-&gt;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 &lt; 4; i++) //Row number i
      {
          for(j = 2; j &gt;= 0; j--) //Column number j
          {
              if(grid-&gt;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 &lt; 3; k++)
                  {
                      if(grid-&gt;tiles[i][k+1] == ' ') //neighbor tile is empty
                      {
                          grid-&gt;tiles[i][k+1] = grid-&gt;tiles[i][k];
                          grid-&gt;tiles[i][k] = ' ';
                      }
                      else if(grid-&gt;tiles[i][k+1] == grid-&gt;tiles[i][k] &amp;&amp; flag) //neighbor equals
                      {
                          grid-&gt;tiles[i][k+1]++;
                          grid-&gt;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 &lt; 4; i++) //Column number i
      {
          for(j = 1; j &lt; 4; j++) //Row number j
          {
              if(grid-&gt;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 &gt; 0; k--)
                  {
                      if(grid-&gt;tiles[k-1][i] == ' ') //neighbor tile is empty
                      {
                          grid-&gt;tiles[k-1][i] = grid-&gt;tiles[i][k];
                          grid-&gt;tiles[k][i] = ' ';
                      }
                      else if(grid-&gt;tiles[k-1][i] == grid-&gt;tiles[i][k] &amp;&amp; flag) //neighbor equals
                      {
                          grid-&gt;tiles[k-1][i]++;
                          grid-&gt;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 &lt; 4; i++) //Column number i
      {
          for(j = 2; j &gt;= 0; j--) //Row number j
          {
              if(grid-&gt;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 &lt; 3; k++)
                  {
                      if(grid-&gt;tiles[k+1][i] == ' ') //neighbor tile is empty
                      {
                          grid-&gt;tiles[k+1][i] = grid-&gt;tiles[i][k];
                          grid-&gt;tiles[k][i] = ' ';
                      }
                      else if(grid-&gt;tiles[k+1][i] == grid-&gt;tiles[i][k] &amp;&amp; flag) //neighbor equals
                      {
                          grid-&gt;tiles[k+1][i]++;
                          grid-&gt;tiles[k][i] = ' ';
                          flag = 0;
                      }
                      else //Can't push or merge
                      {
                          flag = 1;
                          break;
                      }
                  }
              }
          } // Done with column
      }
  }
  </code></pre>
  
  <p>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  <code>[B|A|A]</code> merges into <code>[C]</code> but should merge into <code>[B|B]</code>.</p>
  
  <p>pushUp seems to be almost always just wiping the entire board with empty tiles (spaces).
  pushDows seems to be removing some tiles.</p>
  
  <p>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.</p>