📄 tetris-architecture.html
字号:
<!doctype html public "-//w3c//dtd html 4.0 transitional//en"><html><head> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <meta name="GENERATOR" content="Mozilla/4.77 (Macintosh; U; PPC) [Netscape]"> <title>Tetris Overview</title></head><body bgcolor="#FFFFFF"><h1>Tetris Architecture Overview</h1>Nick Parlante, nick.parlante@cs.stanford.edu<p>This is the architectural overview that describes the Tetris classes.The tetris project lives at the Stanford CS Ed library as document #112(<a href="http://cslibrary.stanford.edu/112/">http://cslibrary.stanford.edu/112/</a>).See the Readme for an introduction to the project and instructions forrunning the program.<p>These Tetris classes provide a framework for a few different Tetrisapplications. For a fun little assignment, students can write their own"brain" AI code (surprisingly easy), and then load it into the providedJTetris GUI to see how it plays. For 2nd year CS undergraduates, we havea fairly difficult assignment where they implement all the main tetrisclasses. This makes a nice exercise in OOP decomposition -- dividing therather large Tetris problem into several non-trivial classes that cooperateto solve the whole thing.<p>The classes that make up Tetris are...<ul><li>Piece -- a single tetris piece</li><li>Board -- the tetris board</li><li>JPieceTest / JBoardTest -- tester classes for Piece and Board</li><li>JTetris -- present the GUI for tetris in a window and do the animation</li><li>LameBrain -- simple heuristic logic that knows how to play tetris</li><li>JBrainTetris -- a subclass of JTetris that uses a brain to play the gamewithout a human player</li></ul>As an additional feature, the tetris classes implement the logic for tetrisin a way that runs <b>quickly</b>. The speed is needed for the later "brain"parts of the project.<h2>Piece</h2>The Piece class defines a tetris piece in a particular rotation. Each pieceis defined by a number of blocks known as its "body". The body is representedby the (x, y) coordinates of its blocks, with the origin in the lower-leftcorner.<br><img SRC="piece.gif" BORDER=0 height=92 width=102><br>So the body of this piece is defined by the (x, y) points : (0,0), (1, 0), (1, 1), (2, 1).<p>The Piece class and the Board class (below) both measure things in thisway -- block by block with the origin in the lower-left corner. As a designdecision, the Piece and Board classes do not know about pixels -- theymeasure everything block by block. Or put another way, all the knowledgeof pixels is isolated in the JTetris class.<p>Each piece responds to the messages like getWidth(), getHeight(), andgetBody() that allow the client to see the state of the piece. The getSkirt()message returns an array that shows the lowest y value for each x valueacross the piece ({0, 0, 1} for the piece above). The skirt makes it easierto compute how a piece will come to land in the board. There are no messagesthat change a piece -- it is "immutable". To allow the client to see thevarious piece rotations that are available, the Piece class builds an arrayof the standard tetris pieces internally -- available through the Piece.getPieces().This array contains the first rotation of each of the standard pieces.Starting with any piece, the nextRotation() message returns the "next"piece object that represents the next counter-clockwise rotation. Enoughcalls to nextRotation() gets the caller back to the original piece.<h2>Board</h2>The Board class stores the 2-d state of the tetris board. The client usesthe place() message to add the blocks of a piece into the board. Once theblocks are in the board, they are not connected to each other as a pieceany more; they are just 4 adjacent blocks that will eventually get separatedby row-clearing.<ul><li>place(piece, x, y) -- add a piece into the board with its lower-left cornerat the given (x, y)</li><li>clearRows() -- compact the board downwards by clearing any filled rows</li></ul>Board has many methods that allow the client to look at the Board state.These all run in constant time -- makes things easy and fast for the client,but harder for the board implementation...<ul><li>int getWidth() -- how many blocks wide is the board</li><li>int getHeight() -- how many blocks high is the board</li><li>int getRowWidth(y) -- the number of filled blocks in the given horizontalrow</li><li>int getColumnHeight(x) -- the height the board is filled in the given column.This is 1 + the y value of the highest filled block</li><li>int getMaximumHeight() -- the max of the getColumnHeight() values</li><li>int dropHeight(piece, x) -- the y value where the origin (lower left corner)of the given piece would come to rest if the piece dropped straight downat the given x</li></ul><h3>Board Undo</h3>The Board also supports a 1-deep undo() facility that allows the clientto undo the most recent placement and/or row clearing. The undo facilityis rather limited -- the client can do a single place() and a single clearRows(),and then use undo() to return to the original state. Although simple, theundo facility is fast. It turns out that the Brain (below) needs exactlythis facility of a simple but fast undo. Here's how undo works...<ul><li>We'll designate the state of the board as "committed" -- astate that can be returned to.</li><li>From a committed state, the client can do a place() operation that modifiesthe board. An undo() will remove the change so the board is back at thecommitted state.</li><li>Then the client can do a clearRows() operation which further modifies theboard. An undo() will remove all the changes so the board is back at thecommitted state.</li><li>Finally, the client can do a commit() operation which marks the currentstate as the new committed state. The previous committed state can no longerbe reached via undo().</li></ul>A client can use the undo facility to animate a piece moving in the boardlike this: place() piece with y=15, pause, undo(), place() with y=14, pause,undo(), place() with y=13, ...<h2>JPieceTest, JBoardTest</h2>These are simple test classes that exercise the Piece and Board respectively.Tetris is complex enough that it's important to build and test the componentsseparately.<h2>JTetris</h2>The JTetris class presents the GUI for a playable tetris game in a window.It uses Piece and Board to do the real work. Usually, I have the studentswrite Piece and Board, but I provide JTetris.<h2>JBrainTetris</h2>JBrainTetris is a subclass of JTetris that uses the LameBrain (below) oranother loaded brain to play tetris without a human player. JBrainTetriscan also implement an "adversary" feature. The adversary is a cruel yethilarious feature where the game figures out what the worst possible nextpiece is (using the brain), and then gives that piece to the player.<h2>LameBrain</h2>LameBrain includes heuristic logic that knows how to play the game of tetris.The LameBrain algorithm is very simple -- it knows that height is bad andcreating holes is bad. Students can write their own brains. Here is thecode...<p><tt>/*</tt><br><tt> A simple brain function.</tt><br><tt> Given a board, produce a number that rates</tt><br><tt> that board position -- larger numbers for worse boards.</tt><br><tt> This version just counts the height</tt><br><tt> and the number of "holes" in the board.</tt><br><tt> See Tetris-Overview.html for brain ideas.</tt><br><tt>*/</tt><br><tt>public double rateBoard(Board board) {</tt><br><tt> final int width = board.getWidth();</tt><br><tt> final int maxHeight = board.getMaxHeight();</tt><p><tt> int sumHeight = 0;</tt><br><tt> int holes = 0;</tt><p><tt> // Count the holes, and sum up the heights</tt><br><tt> for (int x=0; x<width; x++) {</tt><br><tt> final int colHeight = board.getColumnHeight(x);</tt><br><tt> sumHeight += colHeight;</tt><p><tt> int y = colHeight - 2; // addr of first possible hole</tt><p><tt> while (y>=0) {</tt><br><tt> if (!board.getGrid(x,y)) {</tt><br><tt> holes++;</tt><br><tt> }</tt><br><tt> y--;</tt><br><tt> }</tt><br><tt> }</tt><p><tt> double avgHeight = ((double)sumHeight)/width;</tt><p><tt> // Add up the counts to make an overall score</tt><br><tt> // The weights, 8, 40, etc., are just made up numbers thatappear to work</tt><br><tt> return (8*maxHeight + 40*avgHeight + 1.25*holes);</tt><br><tt>}</tt><br> <p>It's pretty easy to write better brain logic, and that alone can bethe basis of an assignment. Here's some suggestions for building a betterbrain (or don't look at these if you want to puzzle it out yourself) ...<ul><li>Height is bad</li><li>Holes are bad</li><li>Stacking more blocks on top of holes is bad</li><li>Holes that are horizontally adjacent to other holes are not quite as bad</li><li>Holes that are vertically aligned with other holes are not quite as bad</li><li>Tall 1-wide troughs are bad</li><li>1-wide troughs are not so bad if they are only 1 or 2 deep. Think aboutwhich pieces could fill a 2-deep trough -- 1, 2, or 3 out of the 7 piecesdepending on the two sides of the trough.</li><li>Concentrate on issues that are near the current top of the pile. Holesthat 10 levels below the top edge are not as important as holes that areimmediately below the top edge.</li><li>At some point, my brain code always has some arbitrary constants like 1.54and -0.76 in it that I can only lamely optimize by hand. To get the bestpossible brain, use a separate genetic algorithm to optimize the constants.This is another reason why the design here has such an emphasis on speed-- the genetic optimizer needs to be able to rip through millions of boardpositions.</li></ul><br> </body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -