Project 1 (MIPS): Adventure Game Solution

Early video games were written almost exclusively in assembly language for practical reasons. The computers that they ran on were extremely limited in speed and memory space, and assembly offered the only real way to write software for them.




For this project, you’ll be implementing a small game in the vein of “Adventure” for the Atari 2600 (think of it as the predecessor of the Legend of Zelda). MARS’s slow execution speed simulates CPUs of the era - you’re definitely not going to be able to draw entire screens of graphics every frame! But you may be surprised at how much stuff you can do in real time, too.

Useful Materials
Here are links to some useful materials:

led_keypad.asm - helper functions for interacting with the LED and keypad plugin
enter_and_leave.asm - macros for entering and leaving functions. Expand them as you see fit!
Slides to give you some help getting started
The grading rubric!



The user input and display will be handled by a special MARS plugin developed by a previous Pitt CS grad student, Jose Baiocchi. This plugin simulates a 64x64 display that looks like a grid of small LEDs (light-emitting diodes), plus four direction keys and a single “action button.” The keys are also mapped to the keyboard so you don’t have to click them: the direction keys are WASD and the action button is B. Here’s what it looks like:










I slightly modified the plugin to give you eight colors instead of four. This way you can display different kinds of objects with many different colors to distinguish them.

Game Description
Main Game Loop
If your game were to run at the full speed of the MARS simulator, things would run too fast and at different speeds on different computers. Your main game loop will be responsible for updating your game at an appropriate speed.

A game tick is the unit of time between each “frame” or “step” of the game. For our purposes, 1 game tick will be 0.1 seconds (100 ms). Don’t use the MARS “sleep” syscall to do this waiting between frames; instead use the “time” syscall to check if it’s been the right amount of time since the last update.
The Game Board
The game board is the virtual world that the game takes place in. It is a 64x64 grid, with coordinates from (0, 0) at the top-left to (63, 63) in the bottom-right. The entire game will take place on this single 64x64 screen.




The board itself is composed of empty spaces and walls. The player and other objects can traverse the empty spaces, and cannot traverse the walls. You will need to represent the game board in memory so that you can check for collision with walls. I don’t recommend storing the game objects in that board structure, as things can get very difficult if you do.




Empty spaces are represented by off (black) LEDs; walls by white LEDs.






Do not randomize the game board. Come up with a layout of walls and objects that is the same every time you load the game. The user should be able to complete the game; no “impossible” board layouts!




For loading the game board and objects during game startup, the easiest and quickest way to get it going is to use the .ascii directive to write 64 lines of 64-character strings in a row in your data segment, and use different characters to represent different kinds of objects/walls/empty spaces. Then it’s just a matter of looping through all 4096 characters and filling in your game’s memory structures appropriately.




If you wanted to get really fancy, and you’re familiar with this kind of stuff already, you could make a tileset and use an editor like Tiled to make your layout(s). Then you could either write an output plugin for Tiled to output a MIPS assembly file, or make a converter to convert the output from Tiled into a MIPS assembly file, or even write your program to use the file IO syscalls to read and parse the files yourself (yeesh). But this is just if you want to get fancy!

Game Objects
There will be several kinds of objects in your game. Most of them will have very simple behaviors, and all of them will interact with the player in some way. Some of the objects will have to “deactivate” or “disappear” during the course of the game as well.




I recommend coming up with a uniform representation for these objects as it will make things easier. What I mean by that is: try thinking about how you’d design this in Java or C++, and then turning that into ASM. You can actually do “object-oriented” coding with some simple techniques! See the programming hints section for some information about this technique.




Don’t overcomplicate it. Just think about what basic information every object needs to store. Then you can come up with data structures to store them. This will make things like collision detection much easier.




I recommend storing the game objects differently/separately from the game board. The objects may interact with the game board (such as the player and dragons colliding with the walls), but it’s easier to do things if the objects are handled separately.

Player Object
The player is represented by a single magenta LED.



The player can do the following:

Stand still.
Move in any of the four cardinal directions: up, down, left, or right. Every game tick, the player will move one space.
If the user presses a direction key, the player will begin moving in that direction and will continue to move in that direction, even if the key is released. (Limitations in the way Java does keyboard input forces us to do movement like this.)

If the player is moving and hits a wall, they stop.
If the player is moving and the user hits the action button, they stop.
Pick up keys by touching them.
Unlock doors by touching them after picking up the right key.
Win the game by touching the treasure.
Lose the game by touching a dragon.
Key Object
Key objects are represented by two horizontally adjacent LEDs which flash between black and the color of the key. Keys can be blue, green, or red.






Keys have the following properties:

Normally, the key just sits there, flashing its LEDs on and off.
When the player touches the key, it should disappear from the game.
Once the player picks up a key, they will keep it in an “inventory” and can use it an unlimited number of times. Each kind of key should have its own “inventory slot”, so the player can pick up multiple kinds of keys at the same time.
Keys are color-coded to the kind of door they open, i.e. red keys open red doors, etc.
Door Object
Door objects are represented by three horizontally or vertically adjacent LEDs, colored the same color as the key which opens them. Doors can therefore be blue, green, or red.






Doors have the following properties:

If the player touches the door and they don’t have the right key, it will behave exactly like a wall (the player stops).
If the player touches the door and they do have the right key, the door will disappear from the game and the player can move unimpeded.
Treasure Object
The treasure object is represented by a rectangle of orange LEDs 3 wide and 2 tall.



The treasure object just sits there until the player touches it. At that point, the player wins the game!

Dragon Object
The dragon object is represented by a rectangle of yellow LEDs 2 wide and 2 tall.




Dragons have the following properties:

Normally, they roam around the room. This can be as simple as just picking a random direction every n game ticks and moving one space in that direction, or more complex if you want it to be.
If the player is within 8 spaces of the dragon in any direction, the dragon will begin to chase the player.

To chase, it will move along one axis (horizontal or vertical) each game tick towards the player. If they were to move along both axes, they could quickly and unfairly overtake the player, who can only move along one axis at a time.
If the player is no longer within 8 spaces, the dragon goes back to roaming.
If the dragon touches the player, it’s a game over.
Displaying the Game
You have a 64x64 display available to you, but it’s very slow to update all 4096 LEDs. Therefore you’ll have to make use of some techniques to speed things up as you draw objects moving around and flashing.




The walls themselves can never have any objects overlapping them, so you can draw them once at the beginning of the game and never have to draw them again. Objects which move or flash are more complex though.




Suppose the player object is at (5, 10), and they want to move right to (6, 10). Currently, the LED at (5, 10) is magenta, and the LED at (6, 10) is black. In order to animate this happening, you only need to change two LEDs: turn the LED at (5, 10) black, and the LED at (6, 10) magenta.









This “turn off the old position, turn on the new position” technique works for larger objects like the dragons, too. A naive implementation would turn off all four of the dragon’s old LEDs and then turn on all four of the new ones, but since they can only ever move along one axis, you can do it by only turning off two old ones and turning on two new ones.

Input and Output
The MARS LED and Keypad plugin uses a technique called memory-mapped IO to communicate with your program. The idea of memory-mapped IO is something like a mailbox: if you want to send a message to a device, you put some data in a specific place in memory. Then the device can pick up the data at that place and act accordingly. It can respond by doing the same thing, such as putting data in another memory location which your program can periodically check.




You can download the assembly file to include in your project here.




The assembly defines several useful constants and three functions:
void Display_SetLED(int x, int y, int color)

void Display_FillRect(int x, int y, int w, int h, int color)

int Input_GetKeypress()




Their parameters (and what registers the parameters are in) and return values are documented in the assembly file.




Previous iterations of this course allowed you to read the colors of LEDs back from the display in order to tell what kinds of things (walls etc) there were. That’s ugly and gross and you’d never really want to do that in real life no no no NO NO NO!! Keep your own representation of walls and objects in memory, independent of how they are displayed on the screen.

Project milestones
On the course schedule, I’ve listed “P1 Part 1” etc. These are guidelines for how far along in the project you should be, but you don’t have to turn anything in for these milestones. These are just here to give you some structure and give an idea of a good order to work on things. Believe me, I know what it’s like to be a procrastinator…

Milestone 1
The first things you should work on are:

Coming up with a memory representation of the game board and a way to load it at game start (remember, just empty spaces and walls!)
Drawing the game board to the display at game start
Making the main game loop do the timing properly (remember, 100ms per game tick)
Starting on the player object: just make it appear and move around on keypresses - collision not necessary yet
Milestone 2
Next you should work on:

Making the player collide with walls (and you may want to make that code work with other kinds of objects, too - the dragons will need to do the same!)
Implementing the key object

Storing which kind of key it is
Making it flash
Letting the player collide with/pick it up
Making it disappear when the player picks it up
Setting a flag in the player’s inventory to say “picked up this kind of key”
Milestone 3
Next you should work on:

Implementing the door object

Storing which kind of door it is
Making the player collide with it as if it were a wall if they don’t have the key
Making it disappear if the player collides with it and they do have the key
Implementing the treasure object

Making it end the game when the player touches it - in other words, quit the game loop.
Milestone 4
To finish up the game, you should work on:

Implementing the dragon object

Making it roam around when the player is not near (it should collide with the walls just like the player does)
Making it chase the player when they get near
Making it stop chasing the player when they get far enough away
Game over when the dragon touches the player
Extra Credit
After those four milestones, your game should be feature-complete, but there’s still a lot of room for polish! You can earn up to 10% extra credit (for a maximum possible score of 110%) by going above and beyond the requirements.




Here are some ideas for extra credit opportunities (and these are just ideas! You don’t have to implement all of these, and you can come up with your own stuff too):

Implement extra treasure objects which give bonus points, and at the end of the game, give the player a score based on treasures + time
Difficulty levels, selectable on a screen before the game (could change the speed/aggressiveness of the dragons, for instance)
Extra challenges such as automated traps and hazards
Intro and game over screens
“Sound effects” using syscalls 31/33 (syscall 31 lets you play a single note and then keep running your program uninterrupted; syscall 33 lets you make simple tunes but your program pauses while the notes are playing)
Multiple “levels” with their own layouts
Programming Hints
Use constants!!!!!
In assembly, much more than in high-level languages, you’re going to be dealing with a lot of numbers. Your code will be much harder to read, write, and change if you hard-code all these numbers. The MIPS assembler gives you a directive for defining constant values called .eqv:




.eqv CELL_EMPTY 0

.eqv CELL_WALL 1




This defines CELL_EMPTY to the constant 0, and CELL_WALL to the constant 1. This will make your code easier to write and much more readable, to yourself and to the grader!

Large areas of memory in the .data segment
If you want to allocate a large area of memory in the data segment, you can use the following syntax:




label: .byte 0:size




Where size is a number saying how many bytes you want to allocate. All the bytes will be filled with the number before the colon. So this will allocate 128 bytes filled with 0s:




label: .byte 0:128




If you use other data sizes, it will allocate that many of that data type (so .word 0:16 allocates 16 words, or 64 bytes, of memory).

Structures/“Objects” in ASM
You can make very simple “objects” along the lines of C structures without much effort. First, decide what kinds of data needs to be in the structures. So let’s say we want a color structure that holds red, green, and blue, and each of these is one byte, i.e.




struct Color

{

uint8_t red;

uint8_t green;

uint8_t blue;

}




The way C represents this in memory is by treating any Color variable as a three-byte blob. If you access red, it gets the first byte; if you access green, it gets the second; if you access blue, it gets the third.




In ASM, we can represent these offsets as numerical offsets in our memory instructions. But you don’t have to hardcode these offsets to numbers! To make your code more readable, you can use the .eqv directive to make constants:




.eqv Color_red 0

.eqv Color_green 1

.eqv Color_blue 2

.eqv Color_sizeof 3




The Color_sizeof constant is so you can create a color object of the right size. For example, you could make a global like so:




my_color: .byte 0:Color_sizeof




Now you can access it through a pointer:




.text

# Let's set it to orange

la $t0, my_color

li $t1, 255

sb $t1, Color_red($t0)

li $t1, 127

sb $t1, Color_green($t0)

li $t1, 0

sb $t1, Color_blue($t0)




You’re still really using integer offsets on the memory instructions! But using .eqv to name the offsets makes the code much more readable. It also makes it possible to add/rearrange fields without having to change the code that accesses them.




I don’t recommend trying to implement “methods” by storing function pointers in objects. You can certainly do that if you want, but it’s way more complex than what you need for this project. Instead, you can store an “object type” field in an object and switch off of that to run different code for each object.

Jump Tables (“switches”)
Switches are useful in high-level languages for when you want to dispatch control among several possible paths, instead of just one or two. Jump tables are not strictly necessary to complete this project, but they’re kind of fun to implement and play with!




A jump table is an array of label addresses. You can index this array like any other array, but then you can load the label address and use the jr instruction to actually jump to the label.




Suppose you were making a little calculator program. It asks the user for their command: 0 to add, 1 to subtract, 2 to multiply, 3 to divide, and 4 to quit. This is where we’d use a switch in a high-level language. First we have to make the jump table array itself:




.data

command_jump_table:

.word _command_add

.word _command_subtract

.word _command_multiply

.word _command_divide

.word _command_quit




As you can see, it’s just a series of .word values with the addresses of labels in the program.




Now we have to write the code that actually jumps to the right label. This is pretty easy: just take the user’s input (a number in the range [0, 4]), index this array, load the address into a register, and then jump to the address in the register:




.text

# Assume here that we got their input and

# made sure it was in the valid range [0, 4].




# The input is in $t0.




la $t1, command_jump_table # get the table

sll $t0, $t0, 2 # multiply the index by 4

add $t0, $t0, $t1 # calculate the address in the table

lw $t0, 0($t0) # load the label from the table

jr $t0 # jump to the label!




This code will effectively branch to the correct command label based on the value in $t0.




A note about using jump tables to call functions: if you want to call a function (that is, do the equivalent of jal), you have to do a little extra work, since there’s no “jump and link to register” instruction. Remember that jal sets the $ra register to the return address. So you have to do that yourself!




Suppose that in the above code, each of the _command labels points to a function. Then we just have to change the jump table code slightly:




la $t1, command_jump_table # get the table

sll $t0, $t0, 2 # multiply the index by 4

add $t0, $t0, $t1 # calculate the address in the table

lw $t0, 0($t0) # load the label from the table

la $ra, _jump_return # give the function a label to return to

jr $t0 # call the function!

_jump_return:

addi.... # whatever code comes next

Macros
If you really want to take advantage of the power of the assembler, macros essentially let you make your own pseudoinstructions. For example, if you find yourself incrementing or decrementing variables a lot (such as in for loops, or moving objects around), you might define inc and dec pseudoinstructions like so:




.macro inc %reg

addi %reg, %reg, 1

.end_macro




.macro dec %reg

addi %reg, %reg, -1

.end_macro




The way a macro works is that it can take 0 or more parameters, whose names are preceded by percent signs (%). Whenever you use the macro, you give it parameters, and it will be replaced by whatever is inside the macro. Any instance of the parameter will be replaced by the argument you gave it. So for instance, the above macros expand like so:




inc $t0

dec $t1

become

addi $t0, $t0, 1

addi $t1, $t1, -1




You can pass anything to macros, not just registers. For example you can pass numeric literals, constants, and labels.




You can get really crazy with macros. You can have multiple macros of the same name and different numbers of parameters, so they can do different things depending on whether you pass one, two, three etc. parameters. For example I made some “enter” and “leave” macros to automate the process of saving and restoring the return address and $sx registers on the stack in functions, which I can use like this:




my_function:

enter # pushes $ra

jal something_else

leave # pops $ra and returns




something_else:

enter $s0 # pushes $ra and $s0

li $s0, 10 # now I can use $s0 freely

jal a_third_function

leave $s0 # pops $ra and $s0 and returns




These macros made it SO much easier to write functions, saving dozens of lines of code and making the functions shorter and easier to read as a result!

Separating code into multiple files
This is going to be a pretty big program, probably 500-1000 lines of assembly code. Keeping it all in one file might be a bit of a chore. If you want to split it up, you have two options:




Put code in multiple files, and then use the .include directive to include all the sub-files into a “main” file. This is an easy way to do things, but unfortunately you may start running into problems with label name collisions (e.g. a lot of your functions might have an “exit” label, so you’ll have to name them uniquely, like “update_player_exit”, “update_dragon_exit” etc.


Put code in multiple files, but DON’T use the .include directive. Instead, use the “Assemble all files in directory” setting in MARS. That way when you assemble, your entire project is assembled at once. This solves the label name collision problem. However, if you want to use functions from one file in another file, you have to use the .globl directive. This is similar to “public static” in Java. For example:

.globl update_player
update_player:
# code to update the player

Now other files can call update_player, but any non-global labels are invisible to other parts of the program (they’re “private” to the file). The .globl directive works with any kind of label, so you can use it to make global variables too.
Using external editors
I dunno about you but I think the MARS code editor is pretty awful, especially for writing a larger program like this. If you have a code editor that you like to use, you can certainly use it. There are probably MIPS syntax highlighting plugins for it since MIPS is so commonly used as a teaching language. I know there is one for Sublime Text.




You can keep the main project file open in MARS. Then when you save your code in your external editor, just hit F3 in MARS to assemble. You don’t need to close and reopen your assembly files in MARS. This way you can quickly re-assemble and test your code while still using a nice editor.