The purpose of this lab is to give you experience in writing time-critical application code that runs with your YAK kernel. This is not a class in artificial intelligence, and you are not required to devise a complicated placement strategy. A reasonably straightforward playing approach is sufficient to clear the number of lines required for this lab. (For those who are not content with just satisfying the minimum requirement, we will have a little contest near the end of the semester with Twinkies awarded to the high scores.)
With some exceptions, the basic rules of Tetris apply to this game. For simplicity, the game board is smaller and the pieces consist of three blocks instead of four. There are only two possible shapes: a "straight" piece and a "corner" piece. More than one piece may be falling at the same time, but they will never fall side by side or be close enough to run into each other as they are being turned. As the number of lines increases, both the rate at which pieces fall and the frequency of their appearance increase as more lines are cleared. The score is simply the number of lines cleared and is displayed at the bottom of the Simptris window; there is no bonus for clearing multiple lines with one piece.
The game board is 6 units wide and 16 units deep. The upper three rows are a special buffer in which new pieces will appear. You can move pieces as soon as they appear in this buffer, but the game ends when a piece touches down with any part of it still in the top three rows. The columns are numbered 0-5 from left to right, and the rows are numbered 0-15 from bottom to top.
The type, placement, and orientation of each piece is generated randomly, but you can (and should) use the appropriate function to seed the random number generator, ensuring that you will see the same sequence of pieces to help with debugging. (If you notice that the behavior of your code is not the same every time you execute with the same seed, please inform a TA or the instructor.) When passing off the program you may use any seed you wish; for our friendly competition a particular seed will be selected at random.
To communicate with your application code, Simptris uses several different interrupts. You will need to write an ISR for every possible interrupt. Normally, if you wanted to ignore a certain interrupt, you would disable it by appropriately setting the IMR in the PIC. However, for this lab, if your simptris code does not need to handle a certain interrupt, create an ISR for it that contains just the iret instruction.
Here is a table listing all possible interrupts that can be generated in Simptris:
Please note that you must write and set up an ISR for all interrupts. If you do not intend to use one of the interrupts, then the ISR for that interrupt should simply send the EOI command and then iret. Don't forget to save and restore the registers that are used by the EOI command (usually AX). Here is a brief description of the new interrupts:
Values of variables not fully explained above are interpreted as follows:
0 1 2 3 * * ** ** ** ** * *
0 1 * *** * *
Both of the above functions use software interrupts to pass the information to Simptris. The actual code that is executed for the software interrupts is hidden from you but you are free to look at simptris.s to see how the software interrupt routines are called. There is some delay between the time these functions are called and when Simptris actually performs the requested command. This simulates a transmission and execution delay and makes the game far more interesting for our purposes. After the delay, Simptris will read the parameters from memory and respond with a received command (IRQ 5) interrupt. Only at this point in time can the next command be sent.
Your application code must meet the following requirements:
<CS: #, CPU: #>
You are to demonstrate your working program to the TA on or before the due date. You will be asked about your code; be prepared to show it and discuss it. If you are working with a partner, make sure that both of you understand how all the code works.
In addition to the demonstration, you should send email to the Lab TA with a written summary of any problems you encountered, any suggestions you have for improvement, and a reasonable estimate of the total time you and your partner spent completing this lab. Also, include the number of lines your application was able to clear.
You should study the application programs from previous labs for insight into how your code should be organized. If you cannot think of an obviously better way of organizing your code, it is recommended that you organize your code as follows: Create multiple tasks; one will handle the arrival of new pieces and then call a placement function for new corner pieces and a different placement function for new straight pieces. A second task is dedicated to communication with Simptris, and a third task tracks statistics. After lab 6, you should see obvious benefits of using a queue to communicate between the tasks that handle new pieces and the task that communicates with Simptris. You could use semaphores, queues, or events to allow ISRs to communicate the new piece details with the task(s) handling piece placement.
Even if you want to maximize your score, start with a simple placement algorithm. The approach described below is straightforward and works quite well. As you code it up, you'll think of some optimizations you can make, but get the simpler approach working first.
The fastest placement algorithms are fairly simple. Don't spend an excessive amount of time writing and debugging an extremely complex algorithm for piece placement only to find that it performs poorly.
Don't put this lab off to the end. Here is a statistical summary of hours reported per team to complete this lab in Fall 2010:
The actual number of lines you clear depends to some extent on the load on the machine you are running on. This is certainly less than ideal, and something you need to be aware of. Run your code again, and try a machine that has fewer active processes on it.
|1st place||445||Alex Sevey, Tyrie Vella|
|2nd place||409||Chase Johnson, Jared Havican|
|3rd place||406||Brett Gottula, Michael McCarty|
|Huxley award*||56||Joel Rendón, Drew Withers|
|1st place||467||Jack Quincy, Darren Turetzky|
|2nd place||441||Jeremy Mickelson|
|3rd place||440||David Gneiting, Aaron Nuzman|
|Huxley award*||27||Daniel Larsen, Adeline Rhoton|
|1st place||426||Michael Chamberlain, Daniel Hansen|
|2nd place||394||Bryan Bryce, Brad White|
|3rd place||389||Richard Black, Luke Davidson|
|Huxley award*||50||Colby Ballew, Alex Harding|
|1st place||420||Franklin Morley, Ricky Niemi|
|2nd place||417||Addison Floyd, Bradford Law|
|3rd place||415||Matt Abel, Shane Coles|
|Huxley award*||28||Philip Erickson, Thomas Sheffield|
|1st place||460||Brandon Williams, Alex Wilson|
|2nd place||407||Colton Lee, Malcolm Plessinger, Michael Skeen|
|3rd place||406||Warren Kemmerer, Michael Reeder|
|Huxley award*||51||Dayton Minor, Jared Moore|
|1st place||446||Luke Newmeyer, Joseph White|
|2nd place||414||Jonathan George, Andrew Keller|
|3rd place||411||Wyatt Hepler|
|Huxley award*||78||Matthew James, Aaron Swenson|
|1st place||405||Troy Hinckley, Glade Snyder|
|2nd place||390||Rick Lyon, James Parker|
|3rd place||365||Travis Chambers, Parker Ridd|
|Huxley award*||34||Kirstin Mickelson, Skylar Brown|
|1st place||410||Connor Anderson, Alec Crestani|
|2nd place||401||Sam Fuller, Seth Guthrie|
|3rd place||391||Ben Jacobson, Martin Sanchez|
|Huxley award*||56||Taylor Welker, Jordan Anderson|
*This is the lowest score by code that--without modification--cleared 200+ lines on another seed. Named after Aldous Huxley, who said: "Consistency is contrary to nature, contrary to life. The only completely consistent people are dead."
Useful Seeds for testing fun piece placement and rotation issues: