Thread: Rotating a Matrix

In my tetris game, I created a function to rotate a 4x4 matrix.
It's done by copying the value of the matrix to an another matrix, then replacing the actual matrix values with the value from the temporary matrix.

It works prefectly, but is there a more efficient way to do this?
Without a temporary matrix for example.

Code:

void RotateBlock(int blocks[4][4]) {
	int i,j,temp[4][4];
	for(i=0;i<4;i++) {
   	     for(j=0;j<4;j++) {
      	           temp[i][j] = blocks[j][3-i];
             }
        }

        CopyBlock(temp,blocks);
}

No, not optimizing, but I'm looking for a more efficient and faster way to do it.

I see...
I thought this code could be faster, but it's fast enough I suppose...
Maybe I'll try that method with pointer, sounds good...

Thanks for your help

Code:

void SetLowestBlock(int block[4][4]) {
	int i,j,temp[4];
        for(i=0;i<4;i++) temp[i] = block[3][i];
        for(j=3;j>0;j--) {
   	     for(i=0;i<4;i++) {
       	          block[j][i] = block[j-1][i];
             }
        }
        for(i=0;i<4;i++) block[0][i] = temp[i];
	for(i=0;i<4;i++) if(block[3][i]!=0) break;
	if(i==4) SetLowestBlock(block);
}

void SetRightBlock(int block[4][4]) {
	int i,j,temp[4];
        for(i=0;i<4;i++) temp[i] = block[i][3];
        for(i=0;i<4;i++) {
   	     for(j=3;j>0;j--) {
      	         block[i][j] = block[i][j-1];
             }
        }
        for(i=0;i<4;i++) block[i][0] = temp[i];
        for(i=0;i<4;i++) if(block[i][3]!=0) break;
  	if(i==4) SetRightBlock(block);
}

void RotateBlock(int blocks[4][4]) {
	int i,j,temp[4][4];
	for(i=0;i<4;i++) {
   	    for(j=0;j<4;j++) {
      	        temp[i][j] = blocks[j][3-i];
            }
        }
        for(i=0;i<4;i++) if(temp[3][i]!=0) break;
        if(i==4) SetLowestBlock(temp);
        for(i=0;i<4;i++) if(temp[i][3]!=0) break;
        if(i==4) SetRightBlock(temp);
        CopyBlock(temp,blocks);
}

I have an another question...
It was because of this, that I thought my code wasn't efficient enough.
After rotating I'll check whether the non-zero values are located at the bottom right corner of the matrix.
It's done by the recursive SetLowestBlock() and SetRightBlock() functions.
The question is, can I make those functions faster?

Originally Posted by Todd Burch

Right now, you are passing the whole [4]X[4] array on the stack. It would be better to do either as laserlight suggested, or, pass a pointer to your [4]x[4] array to the RotateBlock() function as in

Code:

void RotateBlock(int * blocks[4][4]) {
	int i,j,temp[4][4];
	for(i=0;i<4;i++) {
   	     for(j=0;j<4;j++) {
      	           temp[i][j] = *blocks[j][3-i];
             }
        }

        CopyBlock(temp,blocks);
}

Of course, then you would have to change your CopyBlock function. Now, taking that into, consideration, you would be better off, again, with laserlight's suggestion of going to dynamic blocks and just passing pointers around.

If you didn't want to incur the overhead of all the dynamic malloc()s and free()s, and your need for [4]x[4] arrays were fixed at say, 100 of them, you could get an initial 101 arrays and keep a free one anchored some where. Anytime you need to rotate & copy a block, you could grab the free block as the target block, and after your rotate and copy were finished, you could make the source block the new free block.

Todd

Are you saying he's passing 4x4, e.g. 16 ints of memory every time to the function? Are you sure about this? Aren't arrays always passed as pointers?

Well, that's certainly what I said, but I just concluded that that was an incorrect statement. Thanks for clarification.

Code:

#include <stdio.h>

void myfunc(int myblocks[4][4]) { 
	int i , j ; 
	for ( i = 0 ; i < sizeof(myblocks[0])/sizeof(int) ; ++i) { 
		for (j = 0 ; j < sizeof(myblocks[0])/sizeof(int) ; ++j ) { 
			myblocks[i][j] = 'B' ; 
		}
	}
}

void 	printf_array( int blocks[4][4] ) { 
	int i , j ; 
	for ( i = 0 ; i < sizeof(blocks[0])/sizeof(int) ; ++i) { 
		for (j = 0 ; j < sizeof(blocks[0])/sizeof(int) ; ++j ) { 
			printf("blocks[&#37;d][%d] = %c\n", i, j, blocks[i][j] ) ; 
		}
	}
}

int main (int argc, const char * argv[]) {
	int blocks[4][4] ; 
	int i , j ; 
	for ( i = 0 ; i < sizeof(blocks[0])/sizeof(int) ; ++i) { 
		for (j = 0 ; j < sizeof(blocks[0])/sizeof(int) ; ++j ) { 
			blocks[i][j] = 'A' ; 
		}
	}
	printf_array( blocks ) ; 
	myfunc( blocks ) ; 
	printf_array( blocks ) ; 
	return 0;
}

Todd

Originally Posted by ThLstN

[code]
I have an another question...
It was because of this, that I thought my code wasn't efficient enough.
After rotating I'll check whether the non-zero values are located at the bottom right corner of the matrix.
It's done by the recursive SetLowestBlock() and SetRightBlock() functions.
The question is, can I make those functions faster?

Yeah that's what those two functions are doing, it will check whether all values are located at the right bottom corner of the matrix. It will move the values one by one to the bottom and to the right, and check whether there's a not zero value at the bottom row and the right column.

Not sure if it helps you or is a particularly good way, but when I started preparations for my tetris game, the first thing I tried was a rotate function for a 4*4 (or n*n) array. Then I looked at it, and decided many things can be implemented more simply (and would probably be faster), if the block was not represented by a 2D array, but a 1D array of four coordinate-pairs.

Code:

e.g
A (0, 1)
B (1, 1)
C (2, 1)
D (2, 2)

for

XXX
X

Add these values to the coordinates of the bounding box's upper-left corner, and you'll know where the four cells are in the game area (a 2D array).

That's interesting, but I don't quite understand how it works.
What does the A,B,C and D represents?

anon's idea about using a small 1d array of 4 points seems best.
Also, do you really need to justify your pieces to the bottom-right? You may not have to since it might cause the pieces to jiggle around on the screen.
Here's an example of anon's idea. Looks fast.

Code:

typedef struct coord {
    int x, y;
} coord;
 
typedef coord piece[4]; /* A piece is 4 coordinates */
 
/* Rotate a piece 90 degrees clockwise */
void rotate90cw( piece p ) {
    int i;
    for (i = 0; i < 4; ++i) { /* You could unroll this small loop */
        p[i].x = 3 - p[i].y;
        p[i].y = p[i].x;
    }
    /* If you must justify it to the bottom-right
     * then find max_x and max_y; if max_x is not 3,
     * add 3-max_x to all x's; same for max_y. */
}