Josh Stone, Blog

Josh’s projects and security nerdery

Representing Tetrominos

I was thinking today about how one might implement Tetris. Or, rather, considering the legal battles over words that contain “tris”, I’ll call it the game of “falling tetrominos”. I’m sure everyone knows what it looks like, but how would we describe the game objects in code?

To start off, I’m not sure how the original, nor how any successive implementations of the tetromino games have implemented their data structures. I tried to find some, but Google left me empty-handed, and I didn’t want to waste too much time on it. So, if this is what someone else came up with, sorry – I did actually come up with it on my own, and I do think it’s kind of cool.

Here are the seven shapes that comprise the tetrominos:

I flirted with the idea of representing each one as a bitmap, and applying it to the “board” whenever it moved. But there are some problems with that:

  • The shape has to rotate, which means I need implement either bitmap rotation or do weird coordinate loops to get things right – yuck!
  • Defining them is yucky, since they have different dimensions. Then I have to define internal dimensions, since not all hit the 3rd row or 3rd column (or 4th, in the case of the straight line!)

Instead, I started thinking about how I would tell someone to draw them, especially if I had to be very precise. I started thinking about simple ways to draw things – and I thought of an etch-a-sketch. The tetrominos turn into little sequences of actions, kind of like turtle graphics. So, for the following shape:

I have a sequence of actions:

  1. set a block
  2. move forward
  3. set a block
  4. move forward
  5. set a block
  6. turn right 90 degrees
  7. move forward
  8. set a block

And that can be easily encoded into a short string of characters. Each char represents an action, and they are to be interpreted in order. The shape above becomes “sfsfsfrfs”. The chars have the following meanings:

CharMeaning
sset block
fmove forward
rturn right
lturn left
bmove backwards

So now, my tetrominos look like this:

    tetros = ["sfsfsfs",   "sfsfsrfs",
              "sfsfslfs",  "sfsrfslfs",
              "sfslfsrfs", "sfsrfsrfs",
              "sfslfsbrfs"]

And I wrote a little simulator for this mini-language. As it processes it, it also does double duty – testing to see if it encounters occupied spaces on the board (the ‘map’ variable). In these cases, it short-circuits and returns false. As it sets the blocks down, it makes a list of the coordinates where it needs to set down blocks (this is used later to write them to the game board). Finally, the “direction” is represented as a 2-dimensional vector.

  def test(w, h, map)
    (@points, x, y) = [[], @x, @y]
    vec = @v
    @seq.each_byte() do |i|
      case i
      when ?s
        if inbounds?(x, y, w, h) and not map[y][x]
          @points << [x,y]
        elsif y >= 0
          return false
        end
      when ?f: (x,y) = [x + vec[0], y + vec[1]]
      when ?b: (x,y) = [x - vec[0], y - vec[1]]
      when ?r: vec = turn(vec, true)
      when ?l: vec = turn(vec, false)
      end
    end
    return true
  end

Another cool advantage is that by using the “starting vector” stored in the block object (@v above), I don’t have to really do anything about rotation. The “turtle” mode takes care of that by its very design!