Tetris in C, in 200 lines

Question

I aimed at making fully functional (real) Tetris, in the shortest way possible in C. The result is a terminal game for Linux, that uses ncurses. I made it for my friend, who wanted to play it on his Arduino with LED matrix. Before doing it, I browsed for the shortest Tetris code so far. I found the 140-bytes (buggy) JS "Tetris" and 36 lines of JS Tetris with additional HTML.

The main idea is to make it even shorter is using bitwise operations: shifting and logical OR. That was my first idea, but when I got to rotation, I had to switch to the array structure.

However, there is a problem: it is insanely CPU-intensive. My bet is the main loop that gets cycled too many times. So how can I regulate this problem? And do you think this can be done even shorter in C?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <ncurses.h>

#define ROWS 20
#define COLS 11
#define TRUE 1
#define FALSE 0

char Table[ROWS][COLS] = {0};
int score = 0;
char GameOn = TRUE;
double timer = 500000; //half second

typedef struct {
    char **array;
    int width, row, col;
} Shape;
Shape current;

const Shape ShapesArray[7]= {
    {(char *[]){(char []){0,1,1},(char []){1,1,0}, (char []){0,0,0}}, 3},                           //S_shape     
    {(char *[]){(char []){1,1,0},(char []){0,1,1}, (char []){0,0,0}}, 3},                           //Z_shape     
    {(char *[]){(char []){0,1,0},(char []){1,1,1}, (char []){0,0,0}}, 3},                           //T_shape     
    {(char *[]){(char []){0,0,1},(char []){1,1,1}, (char []){0,0,0}}, 3},                           //L_shape     
    {(char *[]){(char []){1,0,0},(char []){1,1,1}, (char []){0,0,0}}, 3},                           //ML_shape    
    {(char *[]){(char []){1,1},(char []){1,1}}, 2},                                                   //SQ_shape
    {(char *[]){(char []){0,0,0,0}, (char []){1,1,1,1}, (char []){0,0,0,0}, (char []){0,0,0,0}}, 4} //R_shape
};

Shape CopyShape(Shape shape){
    Shape new_shape = shape;
    char **copyshape = shape.array;
    new_shape.array = (char**)malloc(new_shape.width*sizeof(char*));
    int i, j;
    for(i = 0; i < new_shape.width; i++){
        new_shape.array[i] = (char*)malloc(new_shape.width*sizeof(char));
        for(j=0; j < new_shape.width; j++) {
            new_shape.array[i][j] = copyshape[i][j];
        }
    }
    return new_shape;
}

void DeleteShape(Shape shape){
    int i;
    for(i = 0; i < shape.width; i++){
        free(shape.array[i]);
    }
    free(shape.array);
}

int CheckPosition(Shape shape){ //Check the position of the copied shape
    char **array = shape.array;
    int i, j;
    for(i = 0; i < shape.width;i++) {
        for(j = 0; j < shape.width ;j++){
            if((shape.col+j < 0 || shape.col+j >= COLS || shape.row+i >= ROWS)){ //Out of borders
                if(array[i][j]) //but is it just a phantom?
                    return FALSE;
            }
            else if(Table[shape.row+i][shape.col+j] && array[i][j])
                return FALSE;
        }
    }
    return TRUE;
}

void GetNewShape(){ //returns random shape
    Shape new_shape = CopyShape(ShapesArray[rand()%7]);

    new_shape.col = rand()%(COLS-new_shape.width+1);
    new_shape.row = 0;
    DeleteShape(current);
    current = new_shape;
    if(!CheckPosition(current)){
        GameOn = FALSE;
    }
}

void RotateShape(Shape shape){ //rotates clockwise
    Shape temp = CopyShape(shape);
    int i, j, k, width;
    width = shape.width;
    for(i = 0; i < width ; i++){
        for(j = 0, k = width-1; j < width ; j++, k--){
                shape.array[i][j] = temp.array[k][i];
        }
    }
    DeleteShape(temp);
}

void WriteToTable(){
    int i, j;
    for(i = 0; i < current.width ;i++){
        for(j = 0; j < current.width ; j++){
            if(current.array[i][j])
                Table[current.row+i][current.col+j] = current.array[i][j];
        }
    }
}

void Halleluyah_Baby(){ //checks lines
    int i, j, sum, count=0;
    for(i=0;i<ROWS;i++){
        sum = 0;
        for(j=0;j< COLS;j++) {
            sum+=Table[i][j];
        }
        if(sum==COLS){
            count++;
            int l, k;
            for(k = i;k >=1;k--)
                for(l=0;l<COLS;l++)
                    Table[k][l]=Table[k-1][l];
            for(l=0;l<COLS;l++)
                Table[k][l]=0;
        }
    }
    timer-=1000; score += 100*count;
}

void PrintTable(){
    char Buffer[ROWS][COLS] = {0};
    int i, j;
    for(i = 0; i < current.width ;i++){
        for(j = 0; j < current.width ; j++){
            if(current.array[i][j])
                Buffer[current.row+i][current.col+j] = current.array[i][j];
        }
    }
    clear();
    for(i = 0; i < ROWS ;i++){
        for(j = 0; j < COLS ; j++){
            printw("%c ", (Table[i][j] + Buffer[i][j])? 'O': '.');
        }
        printw("\n");
    }
    printw("\nScore: %d\n", score);
}

void ManipulateCurrent(int action){
    Shape temp = CopyShape(current);
    switch(action){
        case 's':
            temp.row++;  //move down
            if(CheckPosition(temp))
                current.row++;
            else {
                WriteToTable();
                Halleluyah_Baby(); //check full lines, after putting it down
                GetNewShape();
            }
            break;
        case 'd':
            temp.col++;  //move right
            if(CheckPosition(temp))
                current.col++;
            break;
        case 'a':
            temp.col--;  //move left
            if(CheckPosition(temp))
                current.col--;
            break;
        case 'w':
            RotateShape(temp);  //yes
            if(CheckPosition(temp))
                RotateShape(current);
            break;
    }
    DeleteShape(temp);
    PrintTable();
}

int main() {
    srand(time(0));
    score = 0;
    int c;
    initscr();
    struct timeval before, after;
    gettimeofday(&before, NULL);
    nodelay(stdscr, TRUE);
    GetNewShape();
    PrintTable();
    while(GameOn){
        if ((c = getch()) != ERR) {
          ManipulateCurrent(c);
        }
        gettimeofday(&after, NULL);
        if (((double)after.tv_sec*1000000 + (double)after.tv_usec)-((double)before.tv_sec*1000000 + (double)before.tv_usec) > timer){ //time difference in microsec accuracy
            before = after;
            ManipulateCurrent('s');
        }
    }
    printw("\nGame over\n");
    DeleteShape(current);
    return 0;
}

Makefile:

tetris: tetris.c
   gcc tetris.c -lncurses -o tetris

UPDATE

This is how I finished this little "project":

https://github.com/najibghadri/Tetris200lines

You can make any shape and play on any sized table :)

Answer 1

Minimize math operations

        if (((double)after.tv_sec*1000000 + (double)after.tv_usec)-((double)before.tv_sec*1000000 + (double)before.tv_usec) > timer){ //time difference in microsec accuracy

You do four conversions from integer types to a double precision floating point type. And do two multiplications times a million.

Consider

        //time difference in microsec accuracy
        if (((double)(after.tv_sec - before.tv_sec)*1000000 + (double)(after.tv_usec - before.tv_usec)) > timer) {

This only does two conversions and one multiplication.

Or this answer suggests that you could instead use uint64_t.

        //time difference in microsec accuracy
        if (((after.tv_sec - before.tv_sec)*(uint64_t)1000000 + (after.tv_usec - before.tv_usec)) > timer) {

Optimize the common path

Also, if this is usually false, consider flipping things around.

        if (((double)after.tv_sec*1000000 + (double)after.tv_usec)-((double)before.tv_sec*1000000 + (double)before.tv_usec) > timer){ //time difference in microsec accuracy
            before = after;
            ManipulateCurrent('s');
        }

could become

        if (IS_LATER(after, before)) {
            before = ADD_TO_TIMEVALUE(after, 500000);
            ManipulateCurrent('s');
        }

with

#define IS_LATER(a, b) ((a.tv_sec == b.tv_sec && a.tv_usec > b.tv_usec) || a.tv_sec > b.tv_sec)

and

#define ADD_TO_TIMEVALUE(tv, t) do {\
    tv.tv_usec += t; \
    while (tv.tv_usec >= 1000000) { \
        tv.tv_usec -= 1000000; \
        tv.tv_sec++; \
    } \
} while (0)

This makes updating before more expensive, but makes comparing before and after cheaper (up to three comparisons rather than two conversions, a multiplication, an addition, subtractions, and a comparison). If you usually don't update, this is better.

Also note that it is more modern (C99 and later) to do this with inline functions than macros.

But is that the problem?

This will make the loop operate faster, but that's not really the problem. You keep looping until a certain amount of time has passed. Looping faster won't change that. You might better find a way to loop more slowly to use less CPU.

You are using

    nodelay(stdscr, TRUE);

Consider instead

    halfdelay(1);

Then it should block on input until it times out (after a tenth of a second). So if the user isn't hitting keys, this will only process five times (at most) before advancing the row.

Note: I haven't tried it.

Answer 2

I reduced it to one conversion with converting the time_t (tv_sec) to suseconds_t and made timer's type of that:

if (((suseconds_t)(after.tv_sec - before.tv_sec)*1000000 + (after.tv_usec - before.tv_usec)) > timer)

I also made this inline. Then I did the same delay with getch, but rather with timeout(1) which delays only one millisecond, and still gives the same result. Now CPU usage is 1% rather than 99%.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <ncurses.h>

#define ROWS 20
#define COLS 11
#define TRUE 1
#define FALSE 0

char Table[ROWS][COLS] = {0};
int score = 0;
char GameOn = TRUE;
suseconds_t timer = 500000; //half second

typedef struct {
    char **array;
    int width, row, col;
} Shape;
Shape current;

const Shape ShapesArray[7]= {
    {(char *[]){(char []){0,1,1},(char []){1,1,0}, (char []){0,0,0}}, 3},                           //S_shape     
    {(char *[]){(char []){1,1,0},(char []){0,1,1}, (char []){0,0,0}}, 3},                           //Z_shape     
    {(char *[]){(char []){0,1,0},(char []){1,1,1}, (char []){0,0,0}}, 3},                           //T_shape     
    {(char *[]){(char []){0,0,1},(char []){1,1,1}, (char []){0,0,0}}, 3},                           //L_shape     
    {(char *[]){(char []){1,0,0},(char []){1,1,1}, (char []){0,0,0}}, 3},                           //ML_shape    
    {(char *[]){(char []){1,1},(char []){1,1}}, 2},                                                   //SQ_shape
    {(char *[]){(char []){0,0,0,0}, (char []){1,1,1,1}, (char []){0,0,0,0}, (char []){0,0,0,0}}, 4} //R_shape
};

Shape CopyShape(Shape shape){
    Shape new_shape = shape;
    char **copyshape = shape.array;
    new_shape.array = (char**)malloc(new_shape.width*sizeof(char*));
    int i, j;
    for(i = 0; i < new_shape.width; i++){
        new_shape.array[i] = (char*)malloc(new_shape.width*sizeof(char));
        for(j=0; j < new_shape.width; j++) {
            new_shape.array[i][j] = copyshape[i][j];
        }
    }
    return new_shape;
}

void DeleteShape(Shape shape){
    int i;
    for(i = 0; i < shape.width; i++){
        free(shape.array[i]);
    }
    free(shape.array);
}

int CheckPosition(Shape shape){ //Check the position of the copied shape
    char **array = shape.array;
    int i, j;
    for(i = 0; i < shape.width;i++) {
        for(j = 0; j < shape.width ;j++){
            if((shape.col+j < 0 || shape.col+j >= COLS || shape.row+i >= ROWS)){ //Out of borders
                if(array[i][j]) //but is it just a phantom?
                    return FALSE;
            }
            else if(Table[shape.row+i][shape.col+j] && array[i][j])
                return FALSE;
        }
    }
    return TRUE;
}

void GetNewShape(){ //returns random shape
    Shape new_shape = CopyShape(ShapesArray[rand()%7]);

    new_shape.col = rand()%(COLS-new_shape.width+1);
    new_shape.row = 0;
    DeleteShape(current);
    current = new_shape;
    if(!CheckPosition(current)){
        GameOn = FALSE;
    }
}

void RotateShape(Shape shape){ //rotates clockwise
    Shape temp = CopyShape(shape);
    int i, j, k, width;
    width = shape.width;
    for(i = 0; i < width ; i++){
        for(j = 0, k = width-1; j < width ; j++, k--){
                shape.array[i][j] = temp.array[k][i];
        }
    }
    DeleteShape(temp);
}

void WriteToTable(){
    int i, j;
    for(i = 0; i < current.width ;i++){
        for(j = 0; j < current.width ; j++){
            if(current.array[i][j])
                Table[current.row+i][current.col+j] = current.array[i][j];
        }
    }
}

void Halleluyah_Baby(){
    int i, j, sum, count=0;
    for(i=0;i<ROWS;i++){
        sum = 0;
        for(j=0;j< COLS;j++) {
            sum+=Table[i][j];
        }
        if(sum==COLS){
            count++;
            int l, k;
            for(k = i;k >=1;k--)
                for(l=0;l<COLS;l++)
                    Table[k][l]=Table[k-1][l];
            for(l=0;l<COLS;l++)
                Table[k][l]=0;
        }
    }
    timer-=1000; score += 100*count;
}

void PrintTable(){
    char Buffer[ROWS][COLS] = {0};
    int i, j;
    for(i = 0; i < current.width ;i++){
        for(j = 0; j < current.width ; j++){
            if(current.array[i][j])
                Buffer[current.row+i][current.col+j] = current.array[i][j];
        }
    }
    clear();
    for(i = 0; i < ROWS ;i++){
        for(j = 0; j < COLS ; j++){
            printw("%c ", (Table[i][j] + Buffer[i][j])? 'O': '.');
        }
        printw("\n");
    }
    printw("\nScore: %d\n", score);
}

void ManipulateCurrent(int action){
    Shape temp = CopyShape(current);
    switch(action){
        case 's':
            temp.row++;  //move down
            if(CheckPosition(temp))
                current.row++;
            else {
                WriteToTable();
                Halleluyah_Baby(); //check full lines, after putting it down
                GetNewShape();
            }
            break;
        case 'd':
            temp.col++;  //move right
            if(CheckPosition(temp))
                current.col++;
            break;
        case 'a':
            temp.col--;  //move left
            if(CheckPosition(temp))
                current.col--;
            break;
        case 'w':
            RotateShape(temp);  //yes
            if(CheckPosition(temp))
                RotateShape(current);
            break;
    }
    DeleteShape(temp);
    PrintTable();
}

int main() {
    srand(time(0));
    score = 0;
    int c;
    initscr();
    struct timeval before, after;
    gettimeofday(&before, NULL);
    nodelay(stdscr, TRUE);
    struct timespec ts = {0, 1000000}; //sleep for 0.1 millisec = 100 microsec
    timeout(1);
    inline int is_later(){
        return ((suseconds_t)(after.tv_sec*1000000 + after.tv_usec) -((suseconds_t)before.tv_sec*1000000 + before.tv_usec)) > timer;
    }
    GetNewShape();
    PrintTable();
    while(GameOn){
        if ((c = getch()) != ERR) {
          ManipulateCurrent(c);
        }
        gettimeofday(&after, NULL);
         if (is_later()) { //time difference in microsec accuracy
            ManipulateCurrent('s');
            gettimeofday(&before, NULL); //again, it's for accuracy
        }
    }
    printw("\nGame over!\n");
    DeleteShape(current);
    endwin();
    return 0;
}

Answer 3

I feel a bit uncomfortable seeing structs passed around.
While I'd suggest not to use dynamic allocation for Shapes, I'd use one allocation rather than 1 + size(width) - it would be possible to use a variable size array of pointers into a common char[] of variable size (declared at the end of Shape). But little is to be gained: even assuming 4 byte pointers, the only shape needing less than (1+3)*4 bytes for pointers is the square - but the four characters bump up the total to 16 bytes.
Just declare a 4by4 array, part of it unused:

#define SIZE_MAX 4
typedef struct {
    char pattern[SIZE_MAX][SIZE_MAX];
    int size, row, col;
} Shape;
Shape current;

const Shape Stencils[] = {
        {{0,1,1},
         {1,1,0},
         {0,0,0},}, 3},                 // S_shape
        …
        {{1,1},
         {1,1}}, 2},                    // SQ_shape
        {{1,1,1,1}/*, {}, {}, {}*/}, 4} // I_shape
    };

Shape clone_shape(Shape const shape) {
    Shape new_shape = shape;
    return new_shape;
}

clone_shape() (CopyShape() looks so C#) gets to be trivial (not sure about dispensable); DeleteShape() is obsolete.
In CheckPosition(), both return FALSE; are controlled by array[i][j]:

        if (array[i][j] &&                          // no phantom
            (shape.col+j < 0 || COLS <= shape.col+j
             || shape.row+i >= ROWS                 // Out of borders
             || Table[shape.row+i][shape.col+j]))   // occupied
                return FALSE;

Naming "the size member" of Shape width makes the control of the first nested loop in PrintTable() look odd.
Rather than initialising Buffer to {0}, I'd memcpy() Table and not need to or/add table entries in the loop iterated more often. I'd try out "setting current in buffer" unconditionally:

void print_table() {
    char buffer[ROWS][COLS];
    memcpy(buffer, Table, sizeof buffer);

    for (int i = 0; i < current.size; i++)
        for (int j = 0; j < current.size; j++)
         // if(current.pattern[i][j])
                buffer[current.row+i][current.col+j] = current.pattern[i][j];

    clear();
    for (int i = 0; i < ROWS ; i++) {
        for (int j = 0; j < COLS ; j++)
            printw("%c ", buffer[i][j] ? 'O': '.');
        printw("\n");
    }

    printw("\nScore: %d\n", score);
}