Printable View
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);
}
Do you need to optimize this function?
No, not optimizing, but I'm looking for a more efficient and faster way to do it.
You should answer vart's question first, since something that works fast enough does not need to be optimised.
That said, if you are looking to avoid the copying back to the original, that could be done if you were using pointers to dynamic arrays instead, upon which after you do the rotate to the temporary array, you simply free the original array, then assign the pointer to the temporary array to the original array pointer. However, with such small arrays involved there may be no benefit at all, even if this rotate function is called frequently (and I expect that it is, considering that this is tetris).
You also could implement some "on place" rotation algorithm. But it is not guranteed to work better than the current code. So it is no point to optimize just to receive "effective" code - you should profile the application and decide if the function is a bottle neck and should be optimized
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
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
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.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);
}
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
I have an another question...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);
}
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?
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?Quote:
Originally Posted by Todd Burch
Well, that's certainly what I said, but I just concluded that that was an incorrect statement. Thanks for clarification.
ToddCode:#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[%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;
}
Sorry, but I would expect rotate to be called very-very infreqently in a tetris game (only when the Rotate key is pressed, and the human finger, eyes and keyboard really can't keep up with what the computer is capable of).Quote:
even if this rotate function is called frequently (and I expect that it is, considering that this is tetris)
I don't quite understand what these functions are doing. Could you explain better? You seem to be moving data around there, and not just checking things. Do you want the block to be moved against the bottom and right edge?Quote:
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?
----------
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.
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).Code:e.g
A (0, 1)
B (1, 1)
C (2, 1)
D (2, 2)
for
XXX
X
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.Quote:
Originally Posted by ThLstN
That's interesting, but I don't quite understand how it works.Quote:
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).
What does the A,B,C and D represents?
I meant to typeQuote:
Originally Posted by ThLstN
The idea is that you don't need to worry about 12 empty squares for each block, and you never need to search for the cells of the block as you are storing their (relative) location.Code:A (0, 1)
B (1, 1)
C (2, 1)
D (2, 2)
for
ABC
D
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. */
}
Well thanks.
I wouldn't worry so much about execution speed. Unless you use Speed-up loops in your implementation, it could complete the whole game in less than a blink of an eye no matter how it is coded.
You'll probably see that the main task will be slowing the code down to a playable speed.
The main goal of that was to (hopefully) reduce the complexity of the code which it seems to have a tendency to do. For example, how hard would it be to test if the block is colliding against the left wall?
Code:/*coord block_ulx represents the position of the imaginary 4*4 box
relative to which the coordinates of pieces are given*/
int collides_with_left_wall(coord block_ulx, coord piece[4])
for (i = 0; i < 4; ++i) {
if (block_ulx.x + piece[i].x < 0) { /*block_ulx.x can be negative*/
return 1; //is streching over the edge
}
}
return 0;
}
Many thanks for your help, I'm really interested in trying that method.
So, I think I'll start from scratch again with my tetris game.