• Design and implementation of Tetris in Scheme
  • Design of the game
  • Analysis of the implementation

Design and implementation of Tetris in Scheme

We have discussed several tools which Inventor provides for creating graphics and providing interactivity. Using just these tools, it is possible to create several types of 3D applications. Today we will discuss how to put everything together to create a game; in our example, Tetris.

Design of the game

There were several desired properties in the design of this game. Among them were:

• Object-orientedness. Everything in the game (in this case, the pieces and game board) is an object. We can send messages to these objects; for example, pressing the arrow keys causes rotate messages to be sent to the current piece. The current piece knows when it has reached the bottom of its descent and sends a message to its board to add itself to the blocks currently in the board. Object-orientedness helps maintain levels of abstraction, so that at a high level the game is easy to program.
• Simple interface to the objects. The program only asks the game pieces to move themselves down and rotate themselves; it only asks the board to add a given piece to itself, set the current piece, update its state, and perform the "game over" sequence (displaying the game over text). All other functionality is handled within the objects.
• Speed. There was one glaring inefficiency in the first implementation which required, in the worst case, iteration over all of the blocks in the game board four times every time a piece was dropped. As the game board is 10 by 20 blocks, this meant an 800-step loop, which was too slow for Scheme to perform in real time. Changing the algorithm helped a great deal. There are no doubt several other places in the code where improvements like this could be made.

Analysis of the implementation

We will start from the top level interface of the game and work our way down into some of the implementations of methods of the objects. This mirrors the design process almost perfectly; one first decides upon the desired programming interface, and then implements whatever lower-level functions are necessary to realize that interface.

First, let's look at the function which moves the pieces down. A timer sensor controls the movements of the pieces downward in the game. This is the callback for this sensor, which gets triggered once a second.

(define (timer-sensor-cb user-data sensor)
  (if (not (send *current-piece* 'moveDown))
      (if (not (send *game-board* 'addPieceToBoard *current-piece*))
	  (begin
	    (send *game-board* 'gameOver)
	    (send (SoTimerSensor-cast sensor) 'unschedule))
	  (begin
	    (let* ((new-piece-index (random 5))
		   (new-piece (vector-ref *pieces* new-piece-index)))
	      (send new-piece 'setCurrentTranslation 4 16)
	      (send new-piece 'setCurrentRotation 0)
	      (send *game-board* 'setCurrentPiece new-piece)
	      (set! *current-piece* new-piece)
	      (send *game-board* 'updateState))))))

Note that the movements and additions of the pieces to the board are transparent because of the object oriented interface. The moveDown method of the pieces attempts to move the piece down, and returns #f if there was an obstacle underneath it. If there was an obstacle, this function sends a message to the game board to try to add this piece to the collection already in the board. If this fails (i.e. because there is no room left in the board), the "game over" message is raised and the timer sensor is unscheduled (that is, the pieces stop falling). If, however, the piece was successfully added to the board, it chooses a new one out of the collection of five available, sets it up at the top of the board, and tells the game board to update its state. This takes care of removing completed rows from the board.

The next major top-level callback is that which handles the keyboard events (i.e. pressing of the arrow keys or space bar). Let's look at how this was written:

(define (event-cb user-data node)
  (let ((ev (send node 'getEvent)))
    (if (or (= 1 (SO_KEY_PRESS_EVENT ev RIGHT_ARROW))
	    (= 1 (SO_KEY_PRESS_EVENT ev LEFT_ARROW))
	    (= 1 (SO_KEY_PRESS_EVENT ev DOWN_ARROW))
	    (= 1 (SO_KEY_PRESS_EVENT ev SPACE)))
	(begin
	  (if (= 1 (SO_KEY_PRESS_EVENT ev LEFT_ARROW))
	      (send *current-piece* 'moveLeft)
	      (if (= 1 (SO_KEY_PRESS_EVENT ev RIGHT_ARROW))
		  (send *current-piece* 'moveRight)
		  (if (= 1 (SO_KEY_PRESS_EVENT ev DOWN_ARROW))
		      (send *current-piece* 'rotate)
		      (let loop
			  ()
			(if (send *current-piece* 'moveDown)
			    (begin
			      (send *game-viewer* 'render)
			      (loop)))))))
	  (send node 'setHandled)))))

There are only three primary methods of the game pieces that this function uses: moveLeft, moveRight, and rotate. These functions have no return value because their success or failure does not affect the state of the game. The "else" clause of the final if statement handles the case in which the space bar was pressed. A named let is used for iteration; it repeatedly tells the current piece to move down and the viewer to render itself until the piece reaches the bottom. Note that this temporarily freezes all other interactivity; this is okay, because it fits in with the design of the game (after the space bar has been pressed, the piece can not be moved during its downward flight).

Now let's look at the initialization procedure for the game. This procedure is run exactly once, when the game is loaded.

(define (initialize-tetris)
  (make-board)
  (make-pieces)
  (send *game-viewer* 'setSceneGraph (send *game-board* 'getGeometry))
  (send *game-viewer* 'setTitle "SchemeTris")
  (send *game-viewer* 'show))

Make-board and make-pieces are the two major procedures used in here; let's see how they work.

(define (make-board)
  (set! *game-board* (make-tetris-board 10 20)))

(define (make-pieces)
  (define piece (make-tetris-piece 's))
  (send piece 'setBoard *game-board*)
  (vector-set! *pieces* 0 piece)
  (define piece (make-tetris-piece 'ls))
  (send piece 'setBoard *game-board*)
  (vector-set! *pieces* 1 piece)
  (define piece (make-tetris-piece 't))
  (send piece 'setBoard *game-board*)
  (vector-set! *pieces* 2 piece)
  (define piece (make-tetris-piece 'c))
  (send piece 'setBoard *game-board*)
  (vector-set! *pieces* 3 piece)
  (define piece (make-tetris-piece 'l))
  (send piece 'setBoard *game-board*)
  (vector-set! *pieces* 4 piece))

The make-board procedure is trivial; it simply creates a new tetris board object of size 10 by 20. The make-pieces procedure makes one each of the five different kinds of tetris pieces (s-shaped, long/straight, t-shaped, cube, and l-shaped) and stores them permanently in the global vector called *pieces*. These tetris piece objects are reused over and over again.

Let's look at the beginning of the constructor for the tetris pieces (here called "make-tetris-piece", but to mimic the Inventor syntax this should probably be renamed "new-TetrisPiece"):

(define (make-tetris-piece type)
  (if (not (memq type '(s ls t c l)))
      (error "make-tetris-piece: wrong type" type))
  (define piece-root (new-SoSeparator))
  (send piece-root 'ref)
  (define piece-xlate (new-SoTranslation))
  (define piece-rot (new-SoRotationXYZ))
  (send piece-root 'addChild piece-xlate)
  (send piece-root 'addChild piece-rot)
  (define current-rotation 0)
  (define current-translation '(0 0))
  (define rotation-max 0)
  (define parent-board '())
  (define piece-mask (build-piece-mask type))
  (define color 'none)

The first thing this constructor does is begin to create the internal scene graph of the piece. It then defines some instance variables (current-rotation, current-translation), and creates the "mask" for the piece, which is a series of coordinates centered about the origin which define exactly where the cubes go in this piece. In this implementation of Tetris the graphics are only loosely tied to the internal representation of the pieces and board; a better representation would probably lead to a faster game (and more understandable code).

The piece then completes the construction of its internal scene graph:

  (cond ((eq? type 'c)
	 (begin
	   (set! rotation-max 1)
	   (set! color 'yellow)))
	((eq? type 's)
	 (begin
	   (set! rotation-max 2)
	   (set! color 'blue)))
	((eq? type 'ls)
	 (begin
	   (set! rotation-max 2)
	   (set! color 'red)))
	((eq? type 't)
	 (begin
	   (set! rotation-max 4)
	   (set! color 'green)))
	((eq? type 'l)
	 (begin
	   (set! rotation-max 4)
	   (set! color 'aqua))))
  (send (send piece-rot 'axis) 'setValue SoRotationXYZ::Z)
  (build-tetris-piece piece-root type color)

The build-tetris-piece function knows how to create the graphical representation for each type of tetris piece (i.e. where to put the four cubes) and how to look up the English description of the color and convert it into the color values (in the color-lookup procedure). Note the use of the variable rotation-max. This variable specifies the maximum number of ninety-degree rotations each piece is allowed to undergo. The cube, for example, has its origin at the center of one of the corner cubes, but should not be able to visibly rotate about that corner.

We can see exactly how the rotation process works by beginning to look at the methods for TetrisPiece objects:

    (cond ((eq? message 'rotate)
	   (lambda (self)
	     (if (send parent-board 'checkCoordsPartial 
		       (send self 'getRotatedCoords 1))
		 (begin
		   (set! current-rotation
			 (modulo (1+ current-rotation) 
				 rotation-max))
		   (send (send piece-rot 'angle) 'setValue 
			 (* pi (/ current-rotation 2.0)))
		   #t)
		 #f)))

The first thing the rotate method does is check to see whether it is valid to rotate the piece, or whether there is already an obstacle in the board at any place along the new orientation of the piece. Note that a rotation is valid even if the piece extends off the top of the game board after the rotation; only when the piece hits the bottom do we want to constrain it to fit within the game board. Therefore we check its coordinates "partially". If this check succeeds, the current-rotation variable is set; we see that by using the modulo function that the rotations, in steps of 90 degrees, are actually constrained to be one less than the rotation-max variable. The SoRotationXYZ node is then updated with the piece's new rotation as well.

The moveLeft, moveRight, and moveDown methods work similarly to the rotate method; they check their coordinates against the left, right, and bottom boundaries of the board, and update their positions if it is valid to do so.

The rest of the methods of the TetrisPiece class are devoted primarily to implementing the above methods, so we will not discuss them. Instead, we will examine the TetrisBoard class to see how it implements adding pieces to the board.

The beginning of the constructor for the TetrisBoard class looks like this:

(define (make-tetris-board x-size y-size)
  (define board-slots (build-board x-size y-size))
  (define board-root (build-visual-board x-size y-size))
  (define game-root (new-SoSeparator))
  (define event-callback (new-SoEventCallback))
  (send game-root 'addChild event-callback)
  (define lines-root (build-surrounding-box x-size y-size))
  (send game-root 'addChild lines-root)
  (define cb-info (new-SchemeSoCBInfo))
  (send cb-info 'ref)
  (send (send cb-info 'callbackName) 'setValue "event-cb")
  (send event-callback 'addEventCallback
	(SoKeyboardEvent::getClassTypeId)
	(get-scheme-event-callback-cb)
	(void-cast cb-info))
  (define piece-root (new-SoSeparator))
  (send game-root 'addChild piece-root)
  (send game-root 'addChild board-root)
  (define score 0)
  (define score-root (build-score-text x-size y-size))
  (send game-root 'addChild score-root)
  (define new-game-text-root (build-new-game-text x-size y-size))
  (send game-root 'addChild new-game-text-root)
  (define game-over-text-root (build-game-over-text x-size y-size))
  (send game-root 'addChild game-over-text-root)

This function calls several others during the construction of the scene graph: build-board, build-visual-board, build-surrounding-box, and several build-text functions. We will briefly examine a few of these functions to see how Inventor is used to implement certain desired functionality.

As we stated before, the graphics of the Tetris game and the internal representation of the board and pieces are disparate. The "board slots", as obtained from the call to build-board, are represented in Scheme as a vector of vectors; a value of #t indicates an empty place in the board, while a value of #f means a specific coordinate in the board is occupied. The Inventor representation is similar; it is basically an LED display for which every cube can be made visible or invisible, and whose color can be set.

The build-visual-board procedure calls the make-board-switch procedure repeatedly; this is what creates the actual behavior of the elements of the board. The rest just groups these elements under SoSeparators.

(define (make-board-switch)
  (define root (new-SoSwitch))
  (send root 'ref)
  ;; First child is the empty translation
  (send root 'addChild (make-empty-translation))
  ;; second child is a cube with a translation after it
  (send root 'addChild (make-board-cube))
  (send (send root 'whichChild) 'setValue 0)
  (send root 'unrefNoDelete)
  root)

The call to make-empty-translation makes a scene graph which looks like this:

                  root
               (SoGroup)
                   |
                   -
                   |
                 xlate
            (SoTranslation)

and the call to make-board-cube returns a scene graph which looks like this:

                      root
                   (SoGroup)
                       |
            ------------------------
            |          |           |
           mat        cube       xlate
       (SoMaterial) (SoCube) (SoTranslation)

Note that once these functions return, the names of the individual nodes are no longer available (though Scheme knows not to garbage collect them, because deleting nodes manually in C++ is not allowed). How do we later modify them? Although this is bad programming practice (because it does not generalize), we can use the getChild method of SoGroup and our knowledge of how our scene graph is structured to obtain pointers to nodes in the scene graph if all we have is the root node. For example, here is the function to return a pointer to the SoSwitch node of a particular (x, y) coordinate in the Inventor representation of the board:

(define (get-board-switch board-root x y)
  (SoSwitch-cast (send (SoSeparator-cast
			(send board-root 'getChild (* x 2)))
		       'getChild y)))

Note the use of the type casting functions; these convert a pointer from one data type to another, as in C or C++. Be very careful when using these functions, because errors in usage can cause memory-related errors. One way of making the above procedure more robust would be to take advantage of Inventor's built-in type checking by using the isOfType methods before performing the cast (this was discussed in last Friday's lecture).

Let's briefly look at the build-new-game-text procedure:

(define (build-new-game-text x-size y-size)
  (define root (new-SoSelection))
  (send root 'ref)
  (send (send root 'policy) 'setValue SoSelection::ENUM_TOGGLE)
  (define text-pick-style (new-SoPickStyle))
  (send (send text-pick-style 'style)
	'setValue SoPickStyle::BOUNDING_BOX)
  (send root 'addChild text-pick-style)
  (define xlate (new-SoTranslation))
  (send (send xlate 'translation) 'setValue (* 1.2 (* 2.1 x-size))
	                                    (* 2.1 y-size)
					    (- (/ 2.1 2.0)))
  (send root 'addChild xlate)
  (define font (new-SoFont))
  (send (send font 'size) 'setValue 4.0)
  (send root 'addChild font)
  (define text-mat (new-SoMaterial))
  (send (send text-mat 'diffuseColor) 'setValue 0.0 0.2 1.0)
  (send root 'addChild text-mat)
  (define text (new-SoText3))
  (send root 'addChild text)
  (send (send text 'string) 'set1Value 0 (new-SbString "New Game"))
  (define cb-info (new-SchemeSoCBInfo))
  (send cb-info 'ref)
  (send (send cb-info 'callbackName) 'setValue "new-game-cb")
  (send root 'addSelectionCallback
	(get-scheme-selection-path-cb)
	(void-cast cb-info))
  (send root 'addDeselectionCallback
	(get-scheme-selection-path-cb)
	(void-cast cb-info))
  (send root 'unrefNoDelete)
  root)

This procedure sets up a scene graph with an SoSelection node as its root, and sets up the text "New Game" inside it, specifying that clicking anywhere in the bounding box of this object will select it. It then sets up a callback for both selection and deselection, and specifies that the selection policy be TOGGLE (remember that there is a conflict in Scheme, so SoSelection::TOGGLE becomes SoSelection::ENUM_TOGGLE); this ensures that the new game text will always have an effect when it is clicked.

Finally, let's briefly look at the addPieceToBoard and updateState methods of the TetrisBoard class:

((eq? message 'addPieceToBoard)
 (lambda (self the-piece)
   (let ((coord-list (send the-piece 'getCurrentCoordinates)))
     (if (send self 'checkCoordsFull coord-list)
	 (begin
	   (for-each
	    (lambda (coords)
	      (begin
		(vector-set! (vector-ref board-slots (car coords))
			     (cadr coords)
			     #f)
		(let* ((the-switch 
			(get-board-switch board-root
					  (car coords)
					  (cadr coords)))
		       (the-cube-root
			(SoSeparator-cast (send the-switch
						'getChild
						1)))
		       (the-material
			(SoMaterial-cast (send the-cube-root
					       'getChild
					       0))))
		  (send (send the-material 'diffuseColor) 
			'setValue 
			(color-lookup (send the-piece 'getColor)))
		  (send (send the-switch 'whichChild) 'setValue 1))))
	    coord-list)
	   #t)
	 #f))))

The algorithm for adding a piece to the board works in the following manner: it checks to see whether the piece can be added to the board (checking its blocks against all four boundaries of the board this time), and if it can, it updates the Scheme representation (vectors of vectors) of the board, as well as "turns on" the appropriate cubes in the Inventor representation of the board. The algorithm for updateState (code given below) works as follows: it scans the Scheme representation of the board, figuring out whether any rows have been completed. It calculates the update to the score, blinks the completed rows three times, and then shuffles the blocks downward to fill in the removed rows, copying the colors of the blocks as well. Note that if we had chosen a different representation for the board (i.e. as rows one on top of another as opposed to columns stacked next to each other) we would have been able to simply remove the entire row from the scene graph, which would have caused the graphics to automatically update themselves.

((eq? message 'updateState)
 (lambda (self)
   (let* ((rows-to-remove (get-board-rows-to-remove board-slots
						    x-size y-size))
	  (row-movements (get-row-movements rows-to-remove y-size))
	  (number-of-rows (length rows-to-remove)))
     (cond ((eq? number-of-rows 1)
	    (set! score (+ 100 score)))
	   ((eq? number-of-rows 2)
	    (set! score (+ 300 score)))
	   ((eq? number-of-rows 3)
	    (set! score (+ 700 score)))
	   ((eq? number-of-rows 4)
	    (set! score (+ 1500 score))))
     (send (send (SoText3-cast (send score-root 'getChild 2)) 
		 'string) 'set1Value 1 
		 (new-SbString (number->string score)))
     (if (not (null? row-movements))
	 (begin
	   (blink-rows board-root rows-to-remove x-size)
	   (for-each
	    (lambda (row-movement)
	      (define (horiz-loop x)
		(if (< x x-size)
		    (let* ((the-switch (get-board-switch
					board-root x
					(car row-movement)))
			   (next-switch (get-board-switch
					 board-root x
					 (cdr row-movement)))
			   (next-child (send 
					(send next-switch
					      'whichChild) 
					'getValue))
			   (the-material
			    (SoMaterial-cast
			     (send (SoGroup-cast 
				    (send the-switch 'getChild 1))
				   'getChild 0)))
			   (next-material
			    (SoMaterial-cast
			     (send (SoGroup-cast
				    (send next-switch 'getChild 1))
				   'getChild 0)))
			   (board-col (vector-ref board-slots x)))
		      (send (send the-switch 'whichChild) 
			    'setValue next-child)
		      (if (= next-child 1)
			  (send (send the-material 'diffuseColor) 
				'setValue 
				(SbVec3f-cast 
				 (send (send next-material
					     'diffuseColor)
				       'operator-brackets 0))))
		      (vector-set! board-col (car row-movement)
				   (vector-ref board-col
					       (cdr row-movement)))
		      (horiz-loop (1+ x)))))
	      (horiz-loop 0))
	    row-movements)
	   (define (clear-rows-starting-at y)
	     (define (horiz-loop x)
	       (if (< x x-size)
		   (let ((the-switch (get-board-switch 
				      board-root x y)))
		     (send (send the-switch 'whichChild) 'setValue 0)
		     (horiz-loop (1+ x)))))
	     (if (< y y-size)
		 (begin
		   (horiz-loop 0)
		   (clear-rows-starting-at (1+ y)))))
	   (clear-rows-starting-at
	    (cdr (car (reverse row-movements)))))))))

The take home lesson here is not to understand every detail of how the Tetris game works, but to see that Inventor is very nearly tangential to the implementation of the game. We use it as a tool; the hard part is figuring out how to design the engine behind your program (as well as how to manage the graphics of your program efficiently, and perhaps make them more tightly integrated with your program than was done here).

Next lecture

Next time we will go over some of the solutions to the problem set problems, and answer any questions you have about them. On Friday we will complete our coverage of the Open Inventor toolkit with a discussion of some of the elements we have not covered.

$Id: index.html,v 1.3 1996/01/22 18:35:15 kbrussel Exp $