6
\$\begingroup\$

I've created a a function that will move a tile that a user specifies within the game board.

The game board can be from 3*3 up to 9*9 and is filled with values 1 to d - 1. This function is called within another function that keeps track of "space" array and the 2d "board"array.

This function works however, I feel that I might be using too many constants? How can I make this better?

/**
* If tile borders empty space, moves tile and returns true, else
* returns false. 
* 
* @param   int     tile    The tile the user wants to move
* @param   int[]   space   Space keeps track of where the space is on the board
* @return  bool    
*/
bool move(int tile, int space[])
{
  //check the tile to the left of the space tile so we can swap the space tile with the tile the user wanted
  if ( board[ space[0] ][ space[1] + 1 ] == tile ) {

    board[ space[0] ][ space[1] + 1 ] = 0;

    board[ space[0] ][ space[1] ] = tile;
    space[1]++;

    return true;

  //check the tile to the right of the space tile so we can swap the space tile with the tile the user selected
  }else if ( board[ space[0] ][ space[1] - 1] == tile ) {

    board[ space[0] ][ space[1] - 1 ] = 0;

    board[ space[0] ][space[1] ] = tile;
    space[1]--;

    return true;

  //check the tile to the top of the space tile so we can swap the space tile with the tile the user selected
  }else if ( board[ space[0] + 1 ][ space[1] ] == tile ) {

    board[ space[0] + 1 ][ space[1] ] = 0;

    board[ space[0] ][space[1] ] = tile;
    space[0]++;

    return true;

  //check the tile to the bottom of the space tile so we can swap the space tile with the tile the user selected
  }else if ( board[ space[0] - 1 ][ space[1] ] == tile ) {

    board[ space[0] - 1 ][ space[1] ] = 0;

    board[ space[0] ][space[1] ] = tile;
    space[0]--;

    return true;

  } else {
    //the tile does not border the space tile
    return false;
  }
}
\$\endgroup\$
2
  • \$\begingroup\$ What is the definition of board? How do you know you aren't reading past the array bounds of board when you do something like board[space[0]+1][space[1]]? \$\endgroup\$
    – JS1
    Commented Mar 2, 2017 at 18:35
  • \$\begingroup\$ @JS1 Board will be a two dimensional array from 3x3 to 9x9 (d*d) filed with tiles 1 to d - 1. The function isn't concerned wether its reading past the array bounds as it only cares if you can find the tile. Unless I should be concerned with it? \$\endgroup\$ Commented Mar 2, 2017 at 18:44

2 Answers 2

4
\$\begingroup\$

As suggested in this answer, storing the board as a one-dimensional array would make the logic much simpler. For one thing, the location of the space could be represented as a single int rather than as a two-element array — and arrays are a pain to work with in C.

For an \$n \times n\$ board, the location would be represented as \$n \times row + col\$. To get the neighbours of space, you would only need to check…

  • space - n (above) and space + n (below)

    Index \$i\$ would be in bounds if \$0 \le i < n^2\$.

  • space - 1 (left), space + 1 (right)

    Index \$space \pm 1\$ would be in bounds if it is in the same row, i.e. \$\lfloor \frac{space \pm 1}{n} \rfloor\$ = \$\lfloor \frac{space}{n} \rfloor\$.

\$\endgroup\$
2
  • \$\begingroup\$ This is great! so instead of a 2d array we can just use 1d array that is the length of n * n? \$\endgroup\$ Commented Mar 2, 2017 at 21:37
  • \$\begingroup\$ Yes, that is what I suggested. \$\endgroup\$ Commented Mar 2, 2017 at 21:38
4
\$\begingroup\$

Reading past array bounds

Each of your four checks has the possibility of reading past array bounds. Very bad things can happen when that happens. I will illustrate with an example:

Let board be defined as int board[3][3], and lettile = 1, space[0] = 2, space[1] = 2. When the code reaches this first check:

  if ( board[ space[0] ][ space[1] + 1 ] == tile ) {

    board[ space[0] ][ space[1] + 1 ] = 0;

    board[ space[0] ][ space[1] ] = tile;
    space[1]++;

    return true;
  }

It will read the value of board[2][3], which is past the end of the board array. The memory location corresponding to board[2][3] is 4 bytes past the end of board, and will probably be occupied by some other global variable in your program. Suppose this memory location contains the value 1. In this case, you will swap the 1 with the 0 in board[2][2], and then you will set space[1] to 3 which is outside of your board dimensions. So now:

  1. Whatever global variable held the value 1 will now have the value 0 for no reason.
  2. The next time you call into this function, you will be reading even further out of bounds because space[1] is 3, which will cause you to read from board[2][4].

Simplify with loop

Instead of writing each of your four direction checks separately, you can combine them into a single loop. Here is how I would do that (with additional bounds checking as well to fix the first problem):

bool move(int tile, int space[])
{
    int dx[4] = {  0,  0,  1, -1 };
    int dy[4] = {  1, -1,  0,  0 };

    // Check in each of the four directions.
    for (int i = 0; i < 4; i++) {
        int x = space[0] + dx[i];
        int y = space[1] + dy[i];

        // If out of bounds, skip this direction.
        if (x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
            continue;

        // If we find the tile, swap them with the empty space.
        if (board[x][y] == tile) {
            board[x][y] = 0;
            board[space[0]][space[1]] = tile;
            space[0] = x;
            space[1] = y;
            return true;
        }
    }
    return false;
}
\$\endgroup\$
2
  • \$\begingroup\$ Wow, I was hoping I would be able to use a loop and this is a pretty neat way to implement it. What is your opinion on storing the board as a flattened array vs a 2d array? \$\endgroup\$ Commented Mar 2, 2017 at 21:40
  • 1
    \$\begingroup\$ @JosephPalomino I think that both flattened and 2D have advantages and disadvantages. In actuality, your 2D array is just a flat array in memory anyways. The only difference is that you index a 2D array with [row][column] and a flat array with [row*NUM_COLS + column]. Even with a 2D array, you could still store your space variable as an int and convert it to a row/column pair when you needed to. \$\endgroup\$
    – JS1
    Commented Mar 3, 2017 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.