17
\$\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
\$\endgroup\$
  • 6
    \$\begingroup\$ Good, performant code is not necessarily short, and may be longer than slow code. \$\endgroup\$ – Hosch250 Jul 30 '16 at 15:46
  • \$\begingroup\$ True. Maybe I should simply set the loop to a certain frequency. \$\endgroup\$ – Najib Jul 30 '16 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 Jul 30 '16 at 20:02
  • \$\begingroup\$ If you've come to new insights regarding your own code and would like to share them with the rest of the people, post it as an answer - don't edit your question. If you want to get your changes reviewed, post a new question. \$\endgroup\$ – Pimgd Jul 30 '16 at 20:03
  • 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 Jul 31 '16 at 9:15
15
\$\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\$
  • \$\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 Jul 30 '16 at 19:57
  • \$\begingroup\$ weirdo = the frequency changes a bit, so there are faster-slower jumps \$\endgroup\$ – Najib Jul 30 '16 at 20:00
1
\$\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\$

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.