20
\$\begingroup\$

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 :)

\$\endgroup\$
8
  • 7
    \$\begingroup\$ Good, performant code is not necessarily short, and may be longer than slow code. \$\endgroup\$
    – user34073
    Commented Jul 30, 2016 at 15:46
  • \$\begingroup\$ True. Maybe I should simply set the loop to a certain frequency. \$\endgroup\$
    – Najib
    Commented Jul 30, 2016 at 17:53
  • 2
    \$\begingroup\$ Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Pimgd
    Commented Jul 30, 2016 at 20:02
  • 1
    \$\begingroup\$ Code Review isn't really place for short-just-to-be-short code. You might like Code Golf, where people get thousands of upvotes for that sort of thing. \$\endgroup\$
    – wizzwizz4
    Commented Jul 31, 2016 at 9:15
  • 4
    \$\begingroup\$ Congratulations because your code appeared in the new Tetris film just released At approximately 21:15 into the film! I paused the screen because I wanted to see the C code and it's exactly the same as the start of your code posted. \$\endgroup\$ Commented Apr 19, 2023 at 5:24

3 Answers 3

18
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Didn't do exactly what you suggested, but you got the point. Conversions were dumb, honestly I copied that part. 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) 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%, however due to the blocking delay shape jumps got a bit weirdo. Thanks! \$\endgroup\$
    – Najib
    Commented Jul 30, 2016 at 19:57
  • \$\begingroup\$ weirdo = the frequency changes a bit, so there are faster-slower jumps \$\endgroup\$
    – Najib
    Commented Jul 30, 2016 at 20:00
  • \$\begingroup\$ IS_LATER(a, b) ((a).tv_sec > (b).tv_sec || ((a).tv_sec == (b).tv_sec && (a).tv_usec > (b).tv_usec)) \$\endgroup\$
    – greybeard
    Commented Apr 19, 2023 at 6:19
2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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);
}
\$\endgroup\$

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.