The simplest thing that could possibly work in Tetris

February 12, 2013 Andrew Fader

At Pivotal we practice a form of Agile software development descended from the original Extreme Programming (XP) created by Kent Beck et al. XP codifies many of our core practices including pair programming, test-driven development, iteration planning, and stand-up. XP also has a very strong emphasis on flat hierarchies and frequent communication. Because of its values and engineering guidelines, XP allows for high-quality software to be produced and shipped extremely quickly. XP values working software over extensive specifications or documentation, so-called “big design up front.” This is so the product can be iterated on quickly, both in the business and the technical sense.

Opinions differ as to which of XP’s practices is the most valuable in accomplishing this. One of my personal favorites is simplicity and clarity in code and design. Simplicity is a difficult thing to pin down. Occam’s Razor, one of the earliest and most popular statements of the parsimony principle, suggests we form a hypothesis with the least “plurality,” or the fewest assumptions or entities possible. Since then people have rephrased this idea as “keep it simple, stupid” (KISS) or probably the most elegant, “less is more.” My favorite statement is St. Exupéry’s:

“It seems that perfection is reached not when there is nothing left to add, but when there is nothing left to take away.”

XP offers us its own guidance on simplicity and writing simple code. It has two simply stated tenets on simplicity: “do the simplest thing which can possibly work,” and the related “you ain’t gonna need it” (YAGNI). Ward Cunningham, another father of XP, explains the first concept as:

“What’s possible? What is the simplest thing we could say in code, so that we’ll be talking about something that’s on the screen, instead of something that’s ill-formed in our mind. Once we get something on the screen, we can look at it. If it needs to be more, we can make it more.”

YAGNI is an answer to the temptation to prematurely optimize: “Always implement things when you actually need them, never when you just foresee that you need them.” Yet, XP also tells us we should “refactor mercilessly,” and Cunningham has long been a proponent of object-oriented design patterns. There is some tension there and it depends on the project and situation.

Clojure creator Rich Hickey tells us in his 2011 talk that the easiest thing isn’t always the most simple, and the simplest design isn’t always immediately apparent. This is a veiled jab at object-oriented programming in favor of functional languages. Obviously object orientation leads to many more “entities” than functional design, assuming entities are objects. Yet most programmers will tell you that objected-oriented design is “easier” than functional design. Perhaps this is merely because they are more familiar with OOP from past experience. However, many would also argue that functional code is quite complex. Code is communication, so a good design is easily parsed (by humans) and understood. That might mean favoring OOP conventions over a more functional style. In Ruby we have a number of functional-inspired techniques that allow for some middle ground to follow the principle of least astonishment.

Let’s look at a case study. Some months ago, I worked on a Ruby implementation of Tetris in my spare time. My goal was to have a working implementation in the shortest time possible, to win a bet that a working game of Tetris would take more than a few days. I settled on Gosu, a C++ 2D game development library that provides graphics, sound, and many other features in a pure Ruby wrapper. The game is on Github. After bundling, you should be able to run it with ‘ruby game_window.rb,’ and try prefacing that with bundle exec if it doesn’t work right away. You will need to have a number of dependencies installed, see the Gosu documentation for more.

I assume the reader is familiar with the rules of Tetris. One of the first things I did was create the shapes for the pieces. Tetris has 7 pieces. All somewhat resemble letters: I the 4×1 stick, J and its mirror L, S and its mirror Z, O the square box, and T. I knew in my head what these pieces looked like, and could easily draw them. So, I created a relative X,Y coordinate system and a draw method. For example, the I piece was [[0,0],[1,0],[2,0],[3,0]].

Now that I had pieces, I needed rotation. I knew what the rotation should look like, but I was not entirely sure how to implement the concept in code. Without researching the question much, I decided to hard-code my values. This seems “dirty” or “ugly,” but it is in keeping with Cunningham’s urging to put something on the screen now and iterate on it later. It was the simplest thing that could possibly provide a working implementation of the game. I also knew that there was a bounded number of possible pieces and rotations in the game, and no need to generalize further. Furthermore, I wasn’t working with a team, didn’t need to maintain the code going forward, and had to win a bet. So I created a large case statement of hashes that looked like this:

def shape
   case @type
   when :I
      {0 => [[1,0],[2,0],[3,0]],
       1 => [[0,-1],[0,-2],[0,-3]],
       2 => [[-1,0],[-2,0],[-3,0]],
       3 => [[0,1],[0,2],[0,3]] }

The pieces, when generated, would randomly assign themselves a type from the list, and a rotation starting at 0. The current_shape method would call to the shape hash method with the current rotation to get the current shape. When the player pressed up, the game would increment the rotation by 1 or reset it back to 0 if it had reached 3. This is not a bad “simplest thing” solution because it is fairly easy to understand what it is doing, and hopefully easy to refactor it into something a bit more elegant. You can see this early commit here. Feel free to checkout that version of the code and run it as well (git checkout 04d590d114cdd564f54491b77339c6ac24bb1693). It will generate a random Tetris piece and then crash. The next commit, ebfcc34e461d30321edf7293f8dc3de95fa2af2b, has semi-functional rotation using the hash method.

I was able to finish the Tetris game with this hard-coded implementation and left it alone for some months. However, in the back of my head, the hard-coded solution was bothering me, and I wanted to implement it using a rotation matrix, a concept I dimly recalled from math class.

Good tests are the most important requirement for refactoring confidently, since they provide a known basis that your refactor preserved the correct behavior and did not break anything. I had been sloppy the first time around and hadn’t written a test for the method that contained the massive case statement, which later became a class method with a type parameter. So here it is:

it "I" do
   Piece.shape(:I)[0].should == [[1,0],[2,0],[3,0]]
   Piece.shape(:I)[1].should == [[0,-1],[0,-2],[0,-3]]
   Piece.shape(:I)[2].should == [[-1,0],[-2,0],[-3,0]]
   Piece.shape(:I)[3].should == [[0,1],[0,2],[0,3]]
end

This was green, as you’ll note it is quite similar to the implementation above. For my refactor I wanted to change the interface of the shape method to have 2 parameters instead of returning a hash, so my test would look like

Piece.shape(:I,0).should == [[1,0],[2,0],[3,0]]

but would otherwise remain the same. The case statement would remain, but would only return the 0 rotation, after which I would perform some sort of matrix transformation.

Wikipedia tells us that the rotation matrix for 90 degrees counterclockwise is:

rotation matrix

After some Googling I settled on an implementation like this:

rotation.times do
   shape = shape.map{|arr|(Matrix[arr] * Matrix[[0,-1],[1,0]]).to_a.flatten}
end

Although the tests passed for the I, J, and L shapes, the other piece tests did not. The O shape actually moved around its axis of rotation even though in my hard-coded version, I had it remain stationary. I had also previously suspected a bug in the implementation of the S or Z shapes, since they seemed to be roughly the same, even though they should have been mirror images. More than likely my known “true” values were simply off. Playing the game confirmed that the rotation was functional and acted as intended. You can see the commit at GitHub.

I was further able to refactor away the rotation variable, generate the shape at object initialize time, and apply the rotation upon receiving player input (commit). This optimizes the number of rotations. Previously, each rotation would start at 0 and progress to a maximum of 3. So if I rotated from 2 to 3, the old code would actually calculate the interim steps 0 to 1 and 1 to 2 as well. The new stateful version will only perform one matrix transformation per rotation.

This change also allowed me to rewrite the test in a much more object-oriented and end-to-end way, as follows:

let(:piece) { Piece.new(window, grid, type) }
describe "I" do
   let(:type) { :I }
      it "rotates" do
         piece.shape.should == [[1,0],[2,0],[3,0]]
         piece.rotate
         piece.shape.should == [[0,-1],[0,-2],[0,-3]]
         piece.rotate
         piece.shape.should == [[-1,0],[-2,0],[-3,0]]
         piece.rotate
         piece.shape.should == [[0,1],[0,2],[0,3]]
       end
   end
end

I think this is a reasonable showcase of a balance between refactoring and simplicity. My initial implementation was pretty ugly, but it allowed me to continue making progress. After getting the simplest thing out the door and hitting my deadline, I went back to refactor the technological debt I had accrued.

Also, I am not going to need it, but the solution is now generalized enough that I could add additional pieces. For example:

   [[1,0],[2,0],[2,1],[2,2],[2,3],[3,0],[4,0],[5,0],[5,1],[5,2],[5,3]]


Additional Tetris piece

Some would argue that the new design is actually simpler. It's fewer lines of code, fewer branches in logic, it uses a well-established algorithm, it's more elegant. Sure, the refactored version is a vastly improved design, but "simple" isn't about lines of code or branches in logic. "Simple" is about complexity of implementation. For example, XP tells us about the "rule of three": refactor out duplication only on the third occurrence of duplicate logic, not the second. The implication is that duplication is more lines, but "simpler" to write.

What "simple" definitely is not about is elegance. The hard-coded solution was simpler because it had fewer levels of abstraction and required less of a cognitive load to understand than the matrix manipulation: the difference between basic Cartesian coordinates versus a result obtained using linear algebra. Math, even pre-calculus, is often quite elegant but quite abstract and therefore more complex than a simple table of values. Why does the rotation matrix work? Well, to understand that, you'll need to understand its generalized form, and quickly this solution becomes quite slow and complicated to implement, especially if it's late at night and you're having trouble remembering trigonometry.
rotation matrix general

It's clear that according to XP's philosophy, the hard-coded solution is the preferred first step. Kent Beck outlines the benefit of doing the easiest simple thing first:

  • You get done sooner
  • Your work is easier to communicate
  • Duplication is obvious, so the needs and means for refactoring are clearer
  • Tests are easier to write
  • The code is easier to performance tune (Or, at least, there will be more scope for tuning performance)
  • You feel less stress, which enhances all of the above

The key benefit of a simple solution is that you get it done faster so you can iterate on it. It's a first pass used to enable continued progress. Perhaps this principle should be called "do the easiest thing to make the tests pass," "do the ugliest, dirtiest thing first," "do what comes to mind first and stop thinking so hard," or maybe just "be as agile as possible." Agile, of course, primarily means "quick."

About the Author

Biography

More Content by Andrew Fader
Previous
Harper Reed on the Power of Data, at Hadoop: the Foundation for Change
Harper Reed on the Power of Data, at Hadoop: the Foundation for Change

Hadoop: The Foundation for Change, on Monday, February 25th in San Francisco, will reveal Greenplum’s new t...

Next
[Metrics] It's so hard to say goodbye
[Metrics] It's so hard to say goodbye

When you release early and often, you’re bound to churn through new customers. I showed you in my last post...

Enter curious. Exit smarter.

Register Now