1
\$\begingroup\$

I'm building a clone of 2048 in C with SDL2, and I'm implementing the function that adds a number randomly to an empty cell on the board. The board is representd by a 2-Dim array board[BOARD_SIZE][BOARD_SIZE], and stores the exponent for the square value(10 for 1024 and so on). There must be a 90% chance of the cell being worth 1 (i.e. 2^1) against 10% of it being 2. Here's how I implemented this

void randCell(int _board[BOARD_SIZE][BOARD_SIZE]) {
    int row;
    int col;
    bool has_space = false;
    // Check if there's any empty spaces
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            if (_board[i][j] == EMPTY) has_space = true;
        }
    }
    // Randomly pick a cell until we find an empty one
    // TODO: Better way to find empty cells.
    if (has_space) {
        do {
            row = randRange(0, BOARD_SIZE - 1);
            col = randRange(0, BOARD_SIZE - 1);
        } while (_board[col][row]);
        // Fill the cell
        _board[col][row] = (randRange(1, 100) < 90) ? 1 : 2;
    }
}

How can I improve this? Could I somehow decrease the number of loops my while performs by only picking a random cell from the EMPTY ones?

\$\endgroup\$
1
\$\begingroup\$

Confusing explanation

According to your explanation, storing 10 in the board means displaying \$2^{10}\$ or 1024 on the screen. If so, then storing a 1 in the board would display \$2^1\$ or 2, and storing a 2 would display \$2^2\$ or 4. But this contradicts your program which chooses a new display value of 1 and 2 using board values 1 and 2.

Either you should be generating board values 0 and 1, or your explanation was wrong. I'm guessing that your explanation was wrong and that storing x in your board represents \$2^{x-1}\$ and not \$2^x\$.

Random number generation off by one

You said you wanted to generate 1 with 90% frequency, but you actually are generating it with 89% frequency. You need to change your < to a <= to fix that.

One easy way to see that you are off by one is if you change the 90 to a 100. Then you will see that you still have a 1% chance of generating a 2 instead of a 0% chance.

Deterministic way of choosing empty cell

Instead of randomly picking cells until you get an empty one, you can count the number of empty cells, then pick among them. For example, if you count 5 empty cells, then you can pick a number between 0 and 4, and then go back through the cells and find the nth empty cell, where n is the random number you picked.

Sample rewrite

Here is an example of how you could implement the above suggestion:

void randCell(int _board[BOARD_SIZE][BOARD_SIZE]) {
    int num_spaces = 0;

    // Count the number of empty spaces.
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            if (_board[i][j] == EMPTY)
                num_spaces++;
        }
    }

    if (num_spaces == 0)
        return;

    int rand_space = randRange(0, num_spaces - 1);
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            if (rand_space-- == 0) {
                _board[i][i] = (randRange(1, 100) <= 90) ? 1 : 2;
                return;
            }
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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