Hi all! I have programming experience in Java and a little bit of C++ in high school, but in terms of game programming, the only experience I've had was making a Java version of tic-tac-toe. I realize that premature optimization is not recommended as the games one programs grows in complexity, but since this is my 2nd time making a game and since I wish to make a game that is reasonably simple (Tetris), I hope I can be forgiven for attempting optimization before even finishing the game... Now onto my question; I was wondering what would be the most efficient data structure to use for making Tetris. Logically, one would immediately think of a 2D array, but I wonder if this is actually the most efficient way. What I mean by efficient is the most minimalistic usage of both CPU and memory. Although you cant have the best of both worlds, but Im wondering what data structure generate the best ratio of memory/CPU usage. Although Tetris is generally low-spec, but I think it would be nice to know (might be helpful in future game programming to know what data structures are generally good). Im also wondering if there is any way to calculate the size of an object created in C++, and whether memory allocated for objects are usually larger than standard 1D and 2D arrays provided by the C++ std library, since the 2 implementations I have so far for Tetris are: 1. A linked-list of 1D arrays (this means nodes/objects need to be used) 2. A 2D array (I dont think objects are needed, but line clearing and then shifting the lines down, etc. might be use more CPU; less efficient, since you are going to have to swap all the data in the array, one line at a time) Any comments on good data structures to use and object creation techniques (in general), if any exist, would also be appreciated!

Don’t forget that you can make use of individual bits themselves.

Take a char. Assuming the system associates a char with 8 bits. So that’s 8 tetris spaces right there, to indicate the presence of a block (1) or not (0). Have any new ideas now?

I haven't touched C++ in awhile...how would you access the bits in the char though? Is there a function in STL? Is there a list of chars and their corresponding 8-bit values? Or should I just use a bitset from the STL?

Quote:Original post by ChesStrategy
I haven't touched C++ in awhile...how would you access the bits in the char though? Is there a function in STL? Is there a list of chars and their corresponding 8-bit values? Or should I just use a bitset from the STL?

Optimization of Tetris + STL do not mix.

Talking about optimizing Tetris means, for example, that you will use only 256 bytes of stack memory, and nothing else.

As soon as you bring standard library into the mix you've missed the goal already.

What does tetris require:
10 x H - field for board (for H=20 that's 200 entries)
bb - bits per board entry, if you don't need colors, that 1 bit per entry

Board will hence require 25 bytes to store.

Next are the pieces. The most trivial encoding is via bitmasks again, and since largest piece is 4 squares wide, that means you can represent all pieces with 16 bits. There's 7 (I think) pieces, hence you will need 14 bytes to represent all pieces.

Here are your parameters: You are allowed to use 25 bytes of memory for board, and 14 bytes for piece definitions.

This is about as optimal as it gets. Next you need 3 bits to store current piece, 4+5 bits to store current piece position. That leaves you 4 more bits to store current level.

As such, really hardcore optimized Tetris game state requires 25 + 14 + 2 = 41 bytes.

I'm not entirely certain but I seem to remember that using bit operators was the only way in C++ (a bitset in some library would then use this approach as well).
Basically you can use a mask and the 'and' operator to obtain a bit.

I found myself many times wondering what's the best algorithm to do something i needed and looking back i think it's not always about the best algorithm and sometimes it's about achieveing a good approximation of the best algorithm. I think that sometimes you have to think how clean and readable is an implementation and not if it's the best that can be done. In very big projects I think every bit counts but in small projects i don't think "the best algo anxiety" should even be considered. Computers have come a long way since the times when we we're children and now it's not always about the fastest code but it is about how manageable,extensible, clean the code is. I would guess a 2D array will just do for you're implementation of tetris,i know that's what i've used.

Quote:Original post by Antheus
As such, really hardcore optimized Tetris game state requires 25 + 14 + 2 = 41 bytes.

That wouldn't be fun since that'd leave you with 0 bits for the current score [wink].

Early optermisation is commonly regarded as the root of all evil, although thinking about algorithmn design early on certainly isn't :)

However, I am a firm believer that tidy code is better than optermised code, but prehaps thats because I'm on a gameplay team and not an engine team :)

It definately makes a lot of sense to try and write robust, easy to understand, easy to modify code. Optermisations these days don't come so much from 'shaving a few instructions out of this function' as they do from parrellel processing, and this is going to become more and more the case in future generations of hardware.

As for memory, the other day one of the programmers said that we couldn't possibly do something as it would create an extra couple of hundred ints, I was quick to point out how little that was compared to the massive 100MB of textures our environment was using, probably the equivilant to a pebbel (he had to get his mind out of the PS2 development way of thinking). I think many graphics programmers would argue with me, and they're right to do so, but when it comes to the volatile nature of gameplay mechanics, and a forever changing design specification, robustness is awesome. What I'm trying to say is, only optermise when you see the requirement to do so.

Now how would Bangz do it? Well, I think I would have a shape class, this would contain a 5x5 array of bools to define a shape (or whatever the maximum shape size is). We would also have an int to define the rotation (or an enum), this will have the range 0 to 3, and a 2D position that the shape occupies witin the game world. We would then have a game world class, this would contain a single shape class, and a 2D array of bools for the world (is there a block at location X,Y). The game world class will then update the shape class, telling it to go down at a regular time interval, and telling it to rotate and move dependant on player input (validation within this function will be required to make sure we can rotate, no overlaps in the new rotation). Each time the shape goes down we will check to see if any overlaps have occured and if so move it back up one and do an add into the game world bools array to update the location of the newly placed bricks. The shape class can then be reset, and created into a new shape (I'd imagine it would have a createShape function which could be passed a shape type enum and would contain a switch statement for creating the layouts in the boolean array).