|
January 2001 Programmer's Challenge
Tetris
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Monday, 1 January 2001
When George Warner first suggested that I base a Challenge on Tetris, I was skeptical. I hadn’t played Tetris in a long time, and my recollection was that Tetris is a game not only of strategy, but of manual dexterity as well. After some email conversation, however, I think we’ve found a way to formulate Tetris info a meaningful Challenge.
You remember how Tetris is played, right? The game is played on a board sized perhaps 10 cells wide and 20 cells high into which pieces of varying sizes are dropped. The player is able to move the pieces left or right as they drop, or to rotate them clockwise or counter-clockwise, or to drop them to the bottom of the board. The player accumulates points as each piece is positioned into its final location. As one or more rows become completely filled, those rows are removed, the other rows are shifted down, and more points are accumulated. As rows are deleted, the game progresses to higher and higher levels where the pieces drop faster and faster. The game continues until there is no room for the next piece to drop into the board.
In this month’s Challenge version of Tetris, the board size is generalized to something potentially larger than 10x20, the game speed remains constant, and the game continues until a specified time limit expires. You can make one move of the current game piece, a translation or a rotation, for each tick of the game clock. You can take as long as you like to figure out the best move, but every microsecond you use to calculate your move subtracts from the time limit and reduces your opportunity to score additional points. So you need to plan your moves both carefully and quickly.
The prototype for the code you should write is:
typedef char Piece[7][7];
/* aPiece[row][col] is 1 if aPiece occupies cell (row,col), 0 otherwise */
typedef char Board[256][256];
/* aBoard[row][col] is -1 if cell (row,col) is empty, otherwise it is the Piece index */
/* row 0 is the top row, col 0 is the leftmost column */
typedef enum {
kNoMove=0, /* allow piece to fall normally */
kMoveLeft, kMoveRight, /* move piece left/right one column */
kDrop, /* drop piece to bottom of board */
kRotateClockwise, /* rotate piece clockwise 90 degrees */
kRotateCounterClockwise /* rotate piece counterclockwise 90 degrees */
} MoveType;
void InitTetris(
short boardWidth, /* width of board in cells */
short boardHeight, /* height of board in cells */
short numPieceTypes, /* number of types of pieces */
const Piece gamePieces[], /* pieces to play */
long timeToPlay /* game time, in milliseconds */
);
MoveType /* move active piece */ Tetris(
const Board gameBoard,
/* current state of the game board,
bottom row is [boardHeight-1], left column is [0] */
short activePieceTypeIndex, /* index into gamePieces of active piece */
short nextPieceTypeIndex, /* index into gamePieces of next piece */
long pointsEarned, /* number of points earned thus far */
long timeToGo /* time remaining, in milliseconds */
);
void TermTetris(void);
The Tetris Challenge will work like this. Your InitTetris routine will be called first, to allow you to set up the problem based on the board configuration and the Piece shapes to be used in the problem. Next, your Tetris routine will be called multiple times, allowing you to manipulate the falling Tetris pieces, with the objective of accumulating as many points as possible. Your Tetris routine will continue to be called until the specified timeToPlay has expired, or until no more Pieces can be placed on the board. Then your TermTetris routine will be called, allowing you to deallocate any dynamically allocated storage.
InitTetris will be provided with the width (boardWidth) and height (boardHeight) of the game Board. It will also be given the numPieceTypes gamePieces to be used in the game, and the length of the game (timeToPlay) in milliseconds.
Each call to Tetris gives you the current state of the gameBoard; you should determine what you want to do with the active game Piece and return the corresponding MoveType. The test code will attempt to translate or rotate the active game Piece according to the MoveType you specify prior to dropping the Piece down one row. If the Piece cannot be moved or rotated as you request, the Piece will simply drop down one row. When the active Piece drops as far as it can, it will remain the active piece for one more game cycle, so that you can move it left or right by one position should you so choose. The Tetris parameters also provide you with the type of the next piece to be played (nextPieceTypeIndex), the pointsEarned so far, and the timeToGo still remaining in the game.
The gameBoard will contain the value —1 in each empty cell, and the index of the Piece occupying that cell for nonempty cells. Game Piece shapes are specified in a 7x7 array, with a 1 indicating that the corresponding cell is occupied. Pieces rotations occur about the central cell in that array. When Tetris is called with a new active game Piece, the Piece will be positioned just above the gameBoard, with the bottom row of the Piece due to appear on the gameBoard the next time Tetris is called.
The winner will be the solution that scores the most Tetris points within the specified timeToPlay. You score 1 point for each row that a Piece falls when it is dropped. When you eliminate a row, you earn 100 points. If multiple rows are completed at the same time, you win additional points: the second row completed by dropping a block is worth 200 points, the third 300 points, and the fourth 400 points. If you should eliminate all blocks on the board, you earn an additional 1000 points.
The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently. If you have wanted to compete in the Challenge, but have been discouraged from doing so, perhaps this is your chance at some recognition and a share of the Challenge prize.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal. You can also provide a solution in Java, provided you also provide a test driver equivalent to the C code provided on the web for this problem.
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the
Programmer's Challenge mailing list. It will be posted to the list on
or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com
with the subject "subscribe challenge-A". You can also join the
discussion list by sending a message with the subject "subscribe
challenge-D".
|
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
