ECEn 425

Lab #8: Simptris


Overview

You are expected to complete this lab with a partner. In this lab you will write application code that makes use of your YAK kernel and interacts with Simptris, a Tetris-like game with significant time constraints. Conceptually, you are writing the code for an embedded, real-time system that will connect to and control another machine running the Simptris game. Your system is notified via interrupts when new pieces appear on the screen and your code must call functions that shift and rotate each piece as it falls so that you continue to clear lines. The shift and rotate functions have a fixed overhead that becomes the bottleneck; as the pieces come faster and fall faster, sooner or later you won't be able to move a piece before it touches down.

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.)

Simptris Details

Simptris is an extension of the simulator. To run put the simulator into simptris mode, enter the command 'simptris'. A new window entitled "Simptris" should appear. The box in this window is the game display. Normal text output from your program will still be displayed in the program output window.

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.

Interrupts

From a (simulated) hardware perspective, the reset, tick, and keypress interrupts are unchanged from previous labs. However, you are free to modify your interrupt handlers for these interrupts in any way you wish, so long as the requirements for this lab are met. (In other words, no specific output is required in the keypress or tick ISRs or handlers.)

Here is a table listing all possible interrupts that can be generated in Simptris:

Emu86 Simptris
Name Priority Name Priority
Reset 0 Game Over 3
Tick 1 New Piece 4
Keypress 2 Received Command 5
Touchdown 6
Line Clear 7

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:

Accessing and Interpreting the Variables

All variables in the description above correspond to word-size locations reserved in the clib.s file. You can easily access these variables in your C code by declaring each as an "extern unsigned" and then referencing it normally, just as you did with the KeyBuffer variable in previous labs.

Values of variables not fully explained above are interpreted as follows:

Control Functions

These functions are used to move the pieces and actually play the game. In order to use these functions, you must include the file simptris.s which provides function declarations. You may also include simptris.h, which provides headers for these functions. Consider the functions in simptris.s part of a "standard library" that is used to communicate with Simptris. (You should not modify these functions for this lab.)

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.

Requirements

Your application code must meet the following requirements:

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.

Important Notes and Recommendations

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:

Known bugs/features

When you clear a line, the pieces above that line fall no further than the line that was cleared. In other words, stuff above the line won't fall down into a hole and cause additional lines to be cleared. If your playing algorithm relies on this functionality, you'd better rethink it.

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.

Simptris Hall of Fame

Lines cleared Team
Fall 2009
(Seed 37428)
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
443 jka
Fall 2010
(Seed 75301)
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
451 jka
Fall 2011
(Seed 77823)
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
439 jka
Fall 2012
(Seed 40376)
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
444 jka
Fall 2013
(Seed 99963)
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
446 jka
Fall 2014
(Seed 10947)
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
443 jka
Fall 2015
(Seed 87532)
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
444 jka
Fall 2016
(Seed 87245)
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
430 jka

*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."

Debugging help

Here are comments from student reports describing their problems on this lab and how they tracked them down. As always, take them with a grain of salt. Also, if you notice any problems or inconsistencies with Simptris or Emu86, please contact a TA immediately so that the problem can be fixed.


Last updated 29 August 2016