The Most Efficient Way to Represent Tetris Pieces
some of the unneeded bit manipulation tricks in my games
Sep 14 2022
As software engineers in the modern programming landscape, there are very few legit reasons to resort to bit manipulation to solve a problem(perhaps excluding very low level programming such as some Operating System work). However, ever since I learned how binary works I've had this burning desire to use bits for everything. This desire has lead to a few interesting moments in my programming career so far, and I wanted to write a little bit about that.
In my freshman year of college I made 'Retrostasis', a puzzle platformer where the player has a limited amount of energy to jump with. I made it in 72 hours for a Gamejolt jam and got to show off the game at GDC. It was very cool. The game was based around collecting different robot parts which sit at the end of spokes off of a central hub where the player's partner is that you're trying to repair. The entire state of the game (in terms of how much a player had completed) boiled down to the different robot parts and if they had been collected.
The straight-forward way to store this would be to create a file and just store some representation of this there, but I wasn't sure how that would work in the browser. I looked for an alternative solution and stumbled upon PlayerPrefs. PlayerPrefs is a system in Unity that's supposed to be used to store player settings (or ~preferences~). It allows you to store small basic units of information identified by keys: integers, floats, strings. So a few approaches to storing this data probably come to mind. You could create a new key for each robot part, and save some kind of value that evaluates to the state of the part for each one. Alternatively, you could store a string with the names of the parts that have been collected, separated by some character. There are probably plenty of other ways, any of which would be completely sufficient for the game, but for some reason I was interested in finding an 'optimal' way to store this information.
Here's what I came up with. First you have to realize that all of the different parts were essentially a boolean decision. Either we've collected the piece, or we haven't. As long as you can uniquely identify which piece corresponds to which bool, you've got a functional solution. So we could save each piece as a key value pair with a string for the key and a bool for the value. However, this doesn't really save any space over any of the solutions already proposed. What we need is some way to store lots of booleans all at once with some method to retrieve and store based on a key. The solution: the save data is an integer, all parts are assigned a different power of two less than 2^64, then when we go to save the data for each robot part, if it has been collected, we take its power of two and OR it with the output.
So, if piece 64 has been collected, the output becomes 64(0b10000000), then if piece 8 is collected, it becomes 72 (0b1001000) and so on. The result is simply an integer, which can be stored in 64 bits. Pretty darn efficient. Then, to get the data back out we iterate through every robot part and do a binary AND on its power of two and the saved string. If we are looking at 8 (0b1000) we AND with 72 (0b1001000) and if the result is not zero (in this case 0b1000) we say this piece has been collected. So that is how Retrostasis stores its save data in 64 bits.
Another fun challenge I faced in my sophomore year of college was the question 'How do you represent tetris pieces?' This was for a Gamecraft, the school's game development club, jam, the first one that I managed to get a friend from outside Gamecraft to come join. The idea for the game was 'an infinite runner where you collect items like tetris pieces and have to fit them into your inventory.' So the game needed the ability to design different tetris pieces as a part of each item. We wanted the designers to be able to create any possible tetris shape without making the logical part of where those pieces fit into the grid overly complicated. For some reason this task sent my brain into overdrive, perhaps I was trying to impress my friend.
I thought that the best way to do this would be to have a grid of checkboxes pop up in the unity editor for the tetris item then we would just click certain checkboxes and store it as a 2-dimensional array of booleans. However, we weren't sure how to make a grid of checkboxes in editor in a game jam timeframe. So my idea was: let's lay out all of the bits of an integer in a square grid, and order them from bottom right to top left. That would give us a way to map integers to any unique piece we wanted (I think we decided the dimensions would be max 4x4). To design them, we actually whipped out a notebook with grid paper, wrote out which powers of two went where, and added them all up.
so if we take 1 + 2 + 16 + 256, we get 275, or this shape:
So those are the times that I used raw bits to represent some things in my games. I hope you found these weird solutions as interesting as I did.