Recently I was looking at a problem involving extracting and transposing submatrices of data within a larger data grid. Somehow this got me thinking how easy it would be to rotate tetrominos using Clojure. In case you are wondering, it is super easy:
(defn rotate-ccw [shape] (apply mapv vector (map rseq shape))) (defn rotate-cw [shape] (apply mapv (comp vec rseq vector) shape))
After doing this trivial exercise I soon found myself asking myself "How fast can I code up Tetris in Clojure." It turns out that the answer is "pretty fast." Let me first say that this is not a new idea. It has been done here and here as well. I still thought it would be fun, so here is my solution along with some insights.
Here's the game. Press the left and right arrow keys to translate, up and down arrows to rotate, and the space bar to make the the tetromino immediately fall into place.
Read on to learn more about how the game was actually written.
Data First Design
As anyone who has seen my Clojure/conj video or talked to me knows, I believe the best approach to coding a solution to a problem is to model the data literally rather than design an API to represent the data. Why model a domain when you can represent it directly instead? Clojure is made for this approach. This exercise is no different, as the first step is to model the shapes as maps of vector literals. Rather than making some sort of base "Tetromino" class and extending a bunch of methods and having some field that loads a bitmap or some such nonsense, I just did what you see here:
Pretty cool, eh? You can look right at the shape entries and see the shapes as they are encoded in the data structures as 1s in a field of 0s. Of course, the current shape will be translating and rotating during the game, so I must keep track of that. I also want to track a few other game values, such as the current score, high score, values to keep track of when a tetromino falls, as well as the cells that are currently locked into place.
This can all be captured in a single function that generates an initial state representing a complete value for the game.
The data structure above completely represents all of the values I need to keep track of for my entire game. The most interesting entries are locked, shape-pos, and shape. locked is a set of coordinates in the board that contain locked cells. shape-pos is the upper left hand coordinate of the current tetramino. shape is the current falling tetramino shape. Note that I do not keep track of rotation. I just rotate the piece in place.
At this point, all that remains is filling in some functions and methods around this data for user interaction, game rules, and rendering. Here are some of the details.
Implicit Board Representation
Rather than taking the usual approach of creating an MxN grid, I implicitly represent the board by using rules for boundaries (nothing can be outside of the board dimensions) and a hash set to represent the blocks currently "locked in" to the board. This definition looks like this:
Basically, for every coordinate in the current falling shape (The shape-coords function) I check to see if it is within the game's x-y grid and if it is not contained in the locked set of cells.
Speaking of computing the coordinates of the current shape, this is something I'll do a lot, so here's a handy function to do it:
This function destructures the current shape position and shape cells from the game and returns the coordinates of the 4 cells in the shape (the 1s).
Moves
Given the above representations, the game reduces down to making valid tetromino moves within the board. There are two scenarios for moving a tetromino:
Read on to learn more about how the game was actually written.
Data First Design
As anyone who has seen my Clojure/conj video or talked to me knows, I believe the best approach to coding a solution to a problem is to model the data literally rather than design an API to represent the data. Why model a domain when you can represent it directly instead? Clojure is made for this approach. This exercise is no different, as the first step is to model the shapes as maps of vector literals. Rather than making some sort of base "Tetromino" class and extending a bunch of methods and having some field that loads a bitmap or some such nonsense, I just did what you see here:
(def shapes
{:I [[0 0 0 0]
[1 1 1 1]
[0 0 0 0]
[0 0 0 0]]
:J [[0 0 0]
[1 1 1]
[0 0 1]]
:L [[0 0 0]
[1 1 1]
[1 0 0]]
:O [[1 1]
[1 1]]
:S [[0 0 0]
[0 1 1]
[1 1 0]]
:T [[0 0 0]
[1 1 1]
[0 1 0]]
:Z [[1 1 0]
[0 1 1]
[0 0 0]]})
This can all be captured in a single function that generates an initial state representing a complete value for the game.
(defn initial-state []
{:frame 0
:speed 50
:score 0
:high-score 0
:locked #{}
:shape-pos [(rand-int 7) 0]
:shape ((rand-nth (keys shapes)) shapes)})
At this point, all that remains is filling in some functions and methods around this data for user interaction, game rules, and rendering. Here are some of the details.
Implicit Board Representation
Rather than taking the usual approach of creating an MxN grid, I implicitly represent the board by using rules for boundaries (nothing can be outside of the board dimensions) and a hash set to represent the blocks currently "locked in" to the board. This definition looks like this:
(defn valid? [{:keys [locked] :as state}]
(every? (fn [[x y :as c]]
(and ((complement locked) c)
(<= 0 x 9) (< y 22)))
(shape-coords state)))
Basically, for every coordinate in the current falling shape (The shape-coords function) I check to see if it is within the game's x-y grid and if it is not contained in the locked set of cells.
Speaking of computing the coordinates of the current shape, this is something I'll do a lot, so here's a handy function to do it:
(defn shape-coords [{:keys [shape-pos shape]}]
(let [d (count shape)]
(for [i (range d) j (range d)
:when (= 1 (get-in shape [i j]))]
(mapv + [i j] shape-pos))))
Moves
Given the above representations, the game reduces down to making valid tetromino moves within the board. There are two scenarios for moving a tetromino:
- The user moves it (This does not include the user making the tetromino fall faster). A user can translate or rotate a tetromino. The only thing the game must do when a user performs a translation or rotation is see if the new piece is in a valid location. If it is you accept the new value, if not you just reject the move.
- It is falling. When a tetromino falls (either over time or by a user forcing it to fall faster) there is only one thing to consider: Is the new position overlapping the set of locked blocks? If so, we do not allow the tetromino to fall, but instead add the former grid positions of the tetromino to the locked block set.
A key point here is that rather than allowing invalid operations to be performed and throwing exceptions or other similar mechanisms, this program simply rejects any invalid operations and always maintains a valid value for the current state.
Here are the functions for piece translation and rotation:
In the above code x-shift means "translate shift" and f is a function to be applied to the shape position (either inc or dec for right or left translation, respectively). rotate takes on of the two rotation functions I defined at the beginning of this post.
For falling, the logic is a bit more complex:
Again, we first do a simple shift. If it is valid, we are done. If it isn't valid that means we've either moved off the bottom of the board or intersected with existing locked pieces. Either way, we lock the unshifted cells into the board and then check to see if rows need clearing. Finally, we add in a new random shape at the top of the board. I also give the player a point when a cell locks.
The player can also execute a fast drop in which they have a piece prepositioned and want it to immediately lock so they can get the next piece. This is as simple as:
The function iterates over the current state with the fall function until the set of locked set of cells change. This will occur when the falling piece can no longer fall.
Clearing Rows
Clearing a row occurs when all every cell in a row is locked. When this occurs, state is threaded such that 10 points are awarded, the speed is decreased (more on this in the next section), and cells are kept, removed, or shifted depending on their relation to the row to be removed.
Bringing It All Together
The final function needed is a game-step function that is called by the user interface layer for each game time step. Here's the function:
The function updates the frame at each time step then does some conditional threading at the new game step. First, if the frame modded with the current speed is zero, the tetromino falls. So, speed in this game is really a misnomer. Lower speed makes the tetromino fall more frequently. Finally, if any y coordinate in the locked cells is at 0 (I am using screen coordinates, so 0 is at the top of the screen going down) we reset the game but maintain the current high score.
A Complete Rule Set and a UI
All of the above code in a single namespace completely defines the game engine. All that is needed is a user interface to display the current value and take user input. I won't go into the details of the UI in this post, but might later. However, here are a couple of high level details about the UI:
Conclusion
Once again, Clojure's ability to let me model a domain directly as data and then write functions to manipulate those domain values has yielded a simple and concise solution to a problem. I find it pretty amazing that I can write an entire game, including UI, in about 150 lines of code. Not only is the solution brief, but I think the simple function names and full-state representation of values makes the code pretty readable. Despite being a simple case in this post, I've found this technique to be quite useful in domains of any size or complexity. However, a key requirement for this approach is a language that has full support for modeling the domain as data. Clojure is an excellent fit as it was designed to be data first from inception.
The complete source for this project can be cloned here.
Here are the functions for piece translation and rotation:
(defn x-shift [state f]
(let [shifted (update-in state [:shape-pos 0] f)]
(if (valid? shifted) shifted state)))
(defn rotate [state f]
(let [shifted (update state :shape f)]
(if (valid? shifted) shifted state)))
For falling, the logic is a bit more complex:
(defn fall [state]
(let [shifted (update-in state [:shape-pos 1] inc)]
(if (valid? shifted)
shifted
(let [locked-coords (shape-coords state)]
(-> state
(update :locked into locked-coords)
(score 1)
(#(reduce clear-row % (map second locked-coords)))
(into { :shape ((rand-nth (keys shapes)) shapes)
:shape-pos [(rand-int 7) 0]}))))))
The player can also execute a fast drop in which they have a piece prepositioned and want it to immediately lock so they can get the next piece. This is as simple as:
(defn fast-drop [{:keys [locked] :as state}]
(some #(when (not= locked (:locked %)) %)
(iterate fall state)))
Clearing Rows
Clearing a row occurs when all every cell in a row is locked. When this occurs, state is threaded such that 10 points are awarded, the speed is decreased (more on this in the next section), and cells are kept, removed, or shifted depending on their relation to the row to be removed.
(defn clear-row [{:keys [locked] :as state} row]
(if (every? locked (for [i (range 10)] [i row]))
(-> state
(score 10)
(update :speed dec)
(assoc :locked
(set (for [[i j] locked :when (not= j row)]
(if (< j row) [i (inc j)] [i j])))))
state))
Bringing It All Together
The final function needed is a game-step function that is called by the user interface layer for each game time step. Here's the function:
(defn game-step [{:keys [frame locked speed] :as state}]
(cond-> (update state :frame inc)
(zero? (mod frame (max speed 1)))
fall
(some zero? (map second locked))
(into (dissoc (initial-state) :high-score))))
A Complete Rule Set and a UI
All of the above code in a single namespace completely defines the game engine. All that is needed is a user interface to display the current value and take user input. I won't go into the details of the UI in this post, but might later. However, here are a couple of high level details about the UI:
- I actually did 2 interfaces - one using Quil and one using Reagent. The one embedded here is the Reagent version.
- The Quil UI compiles to both Java and JavaScript where the Reagent version just compiles to JavaScript.
- The rules are written as cljc files so cross compile without issue.
- Either UI is only about 50-70 lines of code, so are pretty minimal.
Conclusion
Once again, Clojure's ability to let me model a domain directly as data and then write functions to manipulate those domain values has yielded a simple and concise solution to a problem. I find it pretty amazing that I can write an entire game, including UI, in about 150 lines of code. Not only is the solution brief, but I think the simple function names and full-state representation of values makes the code pretty readable. Despite being a simple case in this post, I've found this technique to be quite useful in domains of any size or complexity. However, a key requirement for this approach is a language that has full support for modeling the domain as data. Clojure is an excellent fit as it was designed to be data first from inception.
The complete source for this project can be cloned here.
