#+TITLE: A Tetris Clone * Playfield definition The game of tetris is played on a grid ten squares wide by $n$ deep. A single piece at a time begins at the top of the play area, descending normally at some rate that increases by "level". The player can rotate each piece by $\pi\over 2$ radians at a time, can move the piece horizontally, and can cause the piece to drop faster. A piece "lands" when it can drop no further without either leaving the grid or intersecting a piece already in the grid. When, upon a piece landing, a row in the grid is completely filled, it is declared to be a "line", is removed, and all higher rows are moved down to fill the gap. Due to the shapes of the pieces, up to four rows can be filled at once. #+begin_src lisp (defconstant playfield-width 10) #+end_src Each row in the grid either has a block in it or it doesn't, making the entire grid a bitmap. If we represent each row as a 10-bit integer bitfield then we can detect a line as a row with each bit set to 1, which is #x3ff. If, in order to make boundary-detection easier, we define a single-square-wide barrier on each side of the playfield to be inaccessible, we have the full-row value as #x7fe and the side-collision value as #x801. #+begin_src lisp (defconstant full-row-mask (mask-field (byte playfield-width 1) -1)) (defconstant side-collision-mask (logandc2 (1- (ash 1 (+ playfield-width 2))) full-row-mask)) #+end_src * Piece definition Pieces are made up of contiguous sets of four blocks (tetrominoes). Counting mirror images, this means that there are seven different shapes. If each row of the playfield is a bitfield, then the easiest way to deal with a piece is if it also is a bitmap, with 4-bit integer bitfields for each row. This makes placement within the grid largely a matter of shift operations and collision a mask testing operation. ** The Pieces Themselves Let us presume a "define-piece" macro which names each piece and defines its shape visually. It is easier to write out each rotated piece image directly than to write and debug code to perform the rotation, so the macro should accept one bitmap for each valid rotation. This also absolves us from defining a center of rotation, as the bitmap position need not move, and the center of rotation becomes implicit within the rotated bitmaps. #+begin_src lisp (define-piece (t-piece) " " " " " " " " " # " " # " " " " # " " ###" " ##" " ###" " ## " " " " # " " # " " # ") (define-piece (o-piece) " " " " " " " " " ## " " ## " " ## " " ## " " ## " " ## " " ## " " ## " " " " " " " " ") (define-piece (l-piece) " # " " " " " " " " # " " ###" " ## " " # " " ## " " # " " # " "### " " " " " " # " " ") (define-piece (r-piece) " # " " " " " " " " # " " # " " ## " "### " " ## " " ###" " # " " # " " " " " " # " " ") (define-piece (s-piece) " " " # " " " " # " " ##" " ## " " ##" " ## " " ## " " # " " ## " " # " " " " " " " " ") (define-piece (z-piece) " " " # " " " " # " " ## " " ## " " ## " " ## " " ##" " # " " ##" " # " " " " " " " " ") (define-piece (i-piece) " " " # " " " " # " " " " # " " " " # " "####" " # " "####" " # " " " " # " " " " # ") #+end_src ** Selecting a Piece Pieces are drawn from the full set of defined pieces under an IID distribution. #+begin_src lisp (defun choose-new-piece () (elt *defined-pieces* (random (length *defined-pieces*)))) (defun choose-new-next-piece () (setf *next-piece* (choose-new-piece))) #+end_src ** Piece Rotation We define orientation to be an integer between zero and three, inclusive, ordered in 90-degree increments, clockwise. #+begin_src lisp (defun rotate-from (orientation direction) (declare (type (member :clockwise :anticlockwise) direction) (type (integer 0 3) orientation)) (ecase direction (:clockwise (logand 3 (1+ orientation))) (:anticlockwise (logand 3 (1- orientation))))) #+end_src ** Starting a New Piece Implicitly, the current piece has a position and a rotation. Each piece is put into play at the same horizontal position (centered within the grid?), the same vertical position (covering the top four rows of the grid?), and rotation 0 (the first piece image defined). #+begin_src lisp (defconstant starting-right-column (1+ (ash (- playfield-width 4) -1))) (defconstant starting-orientation 0) (defconstant starting-top-row 0) (defun start-next-piece () (setf *current-piece* *next-piece* *current-top-row* starting-top-row *current-right-column* starting-right-column *current-orientation* starting-orientation)) #+end_src ** Piece Bitmaps Pieces are comprised of 4x4 bitmaps of the piece in each orientation. A piece is passed around as a symbol, with a value of an array containing the bitmaps for each orientation. FIXME: Rewrite this description when I'm not sodding drunk. #+begin_src lisp (defun piece-bitmap (piece orientation) (aref (symbol-value piece) orientation)) #+end_src ** The Definition Machinery A piece is, essentially, a collection of bitmaps indexed by orientation. As such, why not create them as a parameter (to allow redefinition) containing an array of bitmaps? We then create the bitmaps themselves as arrays of integers. This two-level structure allows us to easily map over the rows of a bitmap (useful for collision detection as well as graphics rendering), and to easily find a bitmap for a particular orientation. #+begin_src lisp (defmacro define-piece ((piece-name) &rest rows) (assert (= (* 4 4) (length rows))) (let ((piece-bitmaps (make-piece-bitmaps rows))) `(progn (defparameter ,piece-name ,(make-array 4 :initial-contents piece-bitmaps)) (pushnew ',piece-name *defined-pieces*)))) #+end_src *** Creating The Bitmaps Each oriented bitmap for a piece needs to be pieced together from the more graphical layout used by the callers of DEFINE-PIECE, which has all four first rows first, followed by all four second rows, /et cetera/. This is equivalent to attempting to refer to a column-major array in row-major order. #+begin_src lisp (defun collect-bitmap-rows (all-rows orientation) (loop for row-index below 4 for current-row on (nthcdr orientation all-rows) by #'cddddr collect (car current-row))) (defun make-piece-bitmaps (all-rows) (loop for orientation below 4 for bitmap-rows = (collect-bitmap-rows all-rows orientation) collect (make-piece-bitmap bitmap-rows))) #+end_src *** Converting Bitmap Rows Each oriented piece bitmap is comprised of 4-bit integer rows, but is input as a string of spaces and # characters with the rightmost character in the string being the least significant bit of the integer. We thus need a function to convert from the latter form to the former. #+begin_src lisp (defun convert-bitmap-row (row) (loop for index below 4 for element = (aref row index) for weighted-bit = 8 then (ash weighted-bit -1) when (char= #\# element) sum weighted-bit)) #+end_src *** Creating a Single Piece Bitmap So now we need a function to produce a piece-bitmap from a list of rows. #+begin_src lisp (defun make-piece-bitmap (rows) (make-array 4 :initial-contents (loop for row in rows collect (convert-bitmap-row row)))) #+end_src *** Administrivia And finally, as a piece of administrivia related to piece selection, we have a list of defined pieces. #+begin_src lisp (defvar *defined-pieces* nil) #+end_src * World Interaction The two main operations in interacting with the game world are collision detection and updating the playfield. ** Collision Detection Collision detection is performed by shifting the piece bitmap left to bring it into the correct horizontal position, then masking it against the appropriate rows of the grid (and the side-collision value mentioned above). Should any of the masked bitfields contain set bits then a collision has occurred. #+begin_src lisp ;; FIXME: The call-sites would look better if this used keyword ;; arguments that defaulted to the current game state. (defun piece-collides-world (piece orientation top-row right-column) (loop with piece-bitmap = (piece-bitmap piece orientation) for piece-row below 4 for piece-bitfield across piece-bitmap for playfield-bitfield = (aref *playfield* (+ top-row piece-row)) for shifted-piece-bitfield = (ash piece-bitfield right-column) when (or (not (zerop (logand shifted-piece-bitfield side-collision-mask))) (not (zerop (logand shifted-piece-bitfield playfield-bitfield)))) do (return-from piece-collides-world (values t))) (values nil)) #+end_src ** Updating the Playfield Updating the playfield is performed once a piece has landed. This is similar to collision detection, but instead of masking the piece against the playfield to determine if there is a collision, the piece is merged into the playfield at its current position. #+begin_src lisp (defun update-playfield () (loop with piece-bitmap = (piece-bitmap *current-piece* *current-orientation*) for piece-row below 4 for piece-bitfield across piece-bitmap for playfield-row = (+ *current-top-row* piece-row) for playfield-bitfield = (aref *playfield* playfield-row) for shifted-piece-bitfield = (ash piece-bitfield *current-right-column*) do (setf (aref *playfield* playfield-row) (logior playfield-bitfield shifted-piece-bitfield))) (values nil)) #+end_src * Game State The immediately-controllable game state consists of the current piece, its location and its orientation. #+begin_src lisp (defvar *current-piece*) (defvar *current-top-row*) (defvar *current-right-column*) (defvar *current-orientation*) #+end_src There is also a look-ahead to show what the next piece will be. #+begin_src lisp (defvar *next-piece*) #+end_src * Moving Pieces Around Collision detection is run for each move prior to allowing it. If the move would cause a collision, then the move is denied. If a drop would cause a collision, then the piece is considered to have landed, and the current position is merged into the playfield. ** Rotation By our definition for rotation of a piece under user control, rotation succeeds unless the resulting position collides with the world. #+begin_src lisp (defun rotate-current-piece (direction) (declare (type (member :clockwise :anticlockwise) direction)) (let ((new-orientation (rotate-from *current-orientation* direction))) (unless (piece-collides-world *current-piece* new-orientation *current-top-row* *current-right-column*) (setf *current-orientation* new-orientation)))) #+end_src ** Horizontal Motion By our definition for horizontal motion of a piece under user control, the motion succeeds unless the resulting position collides with the world. #+begin_src lisp (defun move-current-piece (direction) (declare (type (member :left :right) direction) (let ((new-right-column (+ *current-right-column* (ecase direction (:left 1) (:right -1))))) (unless (piece-collides-world *current-piece* *current-orientation* *current-top-row* new-right-column) (setf *current-right-column* new-right-column))))) #+end_src ** Dropping By our definition of a piece falling, a drop occurs unless the resulting position collides with the world, in which case the piece lands. #+begin_src lisp (defun drop-current-piece () (let ((new-top-row (1+ *current-top-row*))) (if (piece-collides-world *current-piece* *current-orientation* new-top-row *current-right-column*) (piece-has-landed) (setf *current-top-row* new-top-row)))) #+end_src *** Upon Landing There is a certain amount of game-state update that must occur when a piece lands. #+begin_src lisp (defun piece-has-landed () (update-playfield) (start-next-piece) (chose-new-next-piece) (check-for-game-end)) #+end_src The game is over when the initial position for a piece collides with already-placed blocks. #+begin_src lisp (defun check-for-game-end () (when (piece-collides-world *current-piece* *current-orientation* *current-top-row* *current-right-column*) ;; FIXME: Game over! )) #+end_src * Starting a New Game Rather than directly accessing the current state or having a special "new game" way to set up the current piece, we simply select a "next" piece and immediately start it. #+begin_src lisp (defun start-new-game () (choose-new-next-piece) (start-next-piece) (choose-new-next-piece)) #+end_src * Loose Ends ** The playfield The playfield is clearly an array of integers, but to simplify the implementation of collision detection there must be a "dummy" last row, with all bits set, that is neither displayed nor checked to see if it contains a complete line. I don't recall how tall the playfield is supposed to be. Very little of the playfield machinery (initialization, /et cetera/) has been defined. ** Scoring No mechanism is yet in place to detect completed lines, remove them from the playfield, /et cetera/. ** Levels The only real purposes for levels are to increase the update frequency and to possibly supply a score multiplier. ** Main game loop It'd be nice to have one. ** Piece representation At present, we're passing bare arrays around as pieces. I'd much rather pass around the symbol for the piece, and have the PIECE-BITMAP accessor (which has yet to be written) use SYMBOL-VALUE.