adding specials to the field

When the player completes a certain number of lines, specified by the server at the beginning of the game, a number of special blocks are added to his or her field, to be collected when the player completes the lines they appear on.

The algorithm for adding a special block to the field is a bit complicated, and very poorly documented. The GTetrinet source, which claims to imitate the behavior of the original TetiNET client, does this:

1. for each special we wish to add to the field:
   1. count the number of filled cells on the field that do not contain specials
   2. if the number of non-special filled cells is 0 (i.e., the field is empty, or contains only specials):
      1. try the following 20 times:
         1. select a column of the field at random
         2. starting at the top of the field, check each cell in the selected column until we find a filled cell or the bottom of the field
      2. if, after 20 tries, we fail to find an empty column (a.k.a. the bottom of the field) or a column whose highest cell is a non-special, abandon adding any more specials
      3. otherwise, add a random special at the bottom of the empty column, or above the non-special cell
   3. if there are non-special cells on the field:
      1. choose one of the non-special cells at random, and replace it with a random special

As you may have noticed, there are some… oddities… in this method. First off, there is absolutely no reason to check for columns with non-special cells in them in the “no non-specials found” branch; we wouldn’t be in that branch if any such column existed. Secondly, there is a (somewhat remote) possibility that, even when there are empty columns present on the field, that branch may not add any specials to the field; I have chosen to replicate this chance, however, for consistency’s sake, as iTetrinet would otherwise spawn slightly more specials than other clients. (The above algorithm also inefficiently re-counts the number of non-special cells on the field for each special being placed, but that’s merely a speed concern.)

As such, iTetrinet uses an alternative method:
(The arrangement of the actual code is also different, and is reflected here)

1. count the number of non-special cells on the field
2. for each special we wish to add to the field:
   1. if there are non-special filled cells on the field:
      1. select a non-special cell at random, and replace it with a random special
      2. decrement the count of non-special cells on the field
   2. otherwise:
      1. try the following 20 times:
         1. select a column at random
         2. if the column is empty, place a random special in the bottom row; if not, continue trying
      2. if 20 tries pass without success, abandon placing any further specials

(A note: on a field with no non-special cells, and the bottom row almost completely filled with specials except for one column, both algorithms will only add the final special—and therefore complete an entire line of specials—approximately 82% of the time.)

A sample implementation of iTetrinet’s method, in C, using BSD’s random() (note that in iTetrinet, the field is indexed from bottom-to-top, i.e., row 0 is the bottom row):

// Add specials to this field
void add_specials(int specials_count)
{
    // Count the number of non-special filled cells on the field
    int non_special_cells = 0;
    char cell;
    for (int row = 0; row < NUM_ROWS; row++)
    {
        for (int column = 0; column < NUM_COLUMNS; column++)
        {
            cell = field_contents[row][column];
            if ((cell > 0) && (cell < NUM_CELL_COLORS))
                non_special_cells++;
        }
    }
    // Attempt to add the specified number of specials
    for (int specials_added = 0; specials_added < specials_count; specials_added++)
    {
        // If there are non-special cells on the field, replace one at random with a special
        if (non_special_cells > 0)
        {
            // Choose a random number of cells to pass over before dropping the special
            int cells_left = random() % non_special_cells;
            // Iterate over the field
            for (int row = 0; row < NUM_ROWS; row++)
            {
                for (int column = 0; column < NUM_COLUMNS; column++)
                {
                    // If this is a non-special cell, check whether to add the special
                    cell = field_contents[row][column];
                    if ((cell > 0) && (cell < NUM_CELL_COLORS))
                    {
                        // If we have skipped the predetermined number of cells, add the special
                        if (cells_left == 0)
                        {
                            // Replace the cell with a random special
                            field_contents[row][column] = random_special(special_frequencies);
                            // Decrement the number of non-special cells remaining
                            non_special_cells--;
                            // Jump to the next iteration of the special-adding loop
                            goto next_special;
                        }
                        // Haven't reached the predetermined number of cells yet
                        cells_left--;
                    }
                }
            }
        }
        else
        {
            // Make 20 attempts to find an empty column
            int tries;
            for (tries = 0; tries < 20; tries++)
            {
                // Choose a random column
                int row, column = random() % NUM_COLUMNS;
                // Check if the column is empty
                for (row = 0; row < NUM_ROWS; row++)
                {
                    if (field_contents[row][column] > 0)
                        break;
                }
                // If the column was empty, add the new special
                if (row == NUM_ROWS)
                {
                    // Add the new special to the bottom row
                    field_contents[0][column] = random_special(special_frequencies);
                    // Go to the next iteration of the special-adding loop
                    goto next_special;
                }
            }
            // If we've tried 20 times and not found an empty column, abandon adding more specials
            if (tries == 20)
                goto abort;
        }
        next_special:
    }
    abort:
}