DPST1092 Computer Systems Fundamentals - Assignment 1: Pacman in MIPS
Assignment 1: Pacman in MIPS
Aims
- to give you experience writing MIPS assembly code
- to give you experience translating C to MIPS
- to give you experience with data and control structures in MIPS
- to give you experience writing MIPS assembly code
- to give you experience translating C to MIPS
- to give you experience with data and control structures in MIPS
Getting Started
Create a new directory for this assignment called pacman, change to this directory, and fetch the provided code by running these commands:
mkdir -m 700 pacman
cd pacman
1092 fetch pacman
If you're not working at CSE, you can download the provided files as a zip file or a tar file.
This will add the following files into the directory:
pacman.s: a stub MIPS assembly file to complete.pacman.c: a reference implementation of Pacman in C.pacman_EOF.c: additional C file for testing.input.txt: example input file.
Create a new directory for this assignment called pacman, change to this directory, and fetch the provided code by running these commands:
mkdir -m 700 pacman cd pacman 1092 fetch pacman
If you're not working at CSE, you can download the provided files as a zip file or a tar file.
This will add the following files into the directory:
pacman.s: a stub MIPS assembly file to complete.pacman.c: a reference implementation of Pacman in C.pacman_EOF.c: additional C file for testing.input.txt: example input file.
Pacman: The Game
1092 mipsy pacman.s
Enter a non-zero number for the seed: 42
Welcome to 1092 Pacman!
# = wall
@ = you
. = dot
M = ghost
The objective is to collect all the dots.
Use WASD to move.
Ghosts will move every time you move.
Touching them will end the game.
#############
#...........#
#.#########.#
#.#M#.......#
#.#####.###.#
#...M.#@#...#
#.#####.###.#
#.#.#...#M..#
#.....#...#.#
#############
You've collected 0 out of 53 dots.
Choose next move (wasd): -- CUT --
pacman.c is an implementation of Pacman, a classic arcade game.
An example game of Pacman can be seen to the right.
A game of Pacman takes place on a 2D grid, as the player tries to collect dots while avoiding ghosts!
Each turn, you can move up (W), left (A), down (S), or right (D). If you move onto a dot on the grid, that dot becomes collected. Your goal is to collect all the dots. Each turn the ghosts also move, and if you run into a ghost the game ends.
To get a feel for this game, try it out in a terminal:
dcc pacman_EOF.c -o pacman
./pacman
You should read through pacman.c. There are comments throughout it that should help you understand what the program is doing [citation needed] — which you'll need for the next part of the assignment.
1092 mipsy pacman.s Enter a non-zero number for the seed: 42 Welcome to 1092 Pacman! # = wall @ = you . = dot M = ghost The objective is to collect all the dots. Use WASD to move. Ghosts will move every time you move. Touching them will end the game. ############# #...........# #.#########.# #.#M#.......# #.#####.###.# #...M.#@#...# #.#####.###.# #.#.#...#M..# #.....#...#.# ############# You've collected 0 out of 53 dots. Choose next move (wasd): -- CUT --
pacman.c is an implementation of Pacman, a classic arcade game.
An example game of Pacman can be seen to the right.
A game of Pacman takes place on a 2D grid, as the player tries to collect dots while avoiding ghosts!
Each turn, you can move up (W), left (A), down (S), or right (D). If you move onto a dot on the grid, that dot becomes collected. Your goal is to collect all the dots. Each turn the ghosts also move, and if you run into a ghost the game ends.
To get a feel for this game, try it out in a terminal:
dcc pacman_EOF.c -o pacman ./pacman
You should read through pacman.c. There are comments throughout it that should help you understand what the program is doing [citation needed] — which you'll need for the next part of the assignment.
pacman.s: The Assignment
Your task in this assignment is to implement pacman.s in MIPS assembly.
You have been provided with some assembly and some helpful information in pacman.s. Read through the provided code carefully, then add MIPS assembly so it executes exactly the same as pacman.c.
The functions get_seed and random_number has already been translated to MIPS assembly for you.
You have to implement the following functions in MIPS assembly:
print_welcomemainget_directionplay_trickcopy_mapget_valid_directionsprint_maptry_movecheck_ghost_collisioncollect_dot_and_check_windo_ghost_logic.
You must translate each function separately to MIPS assembler, following the standard calling conventions used in lectures. When translating a function, you must not make any assumptions about the behaviour or side effects of any other function which is called.
Your task in this assignment is to implement pacman.s in MIPS assembly.
You have been provided with some assembly and some helpful information in pacman.s. Read through the provided code carefully, then add MIPS assembly so it executes exactly the same as pacman.c.
The functions get_seed and random_number has already been translated to MIPS assembly for you.
You have to implement the following functions in MIPS assembly:
print_welcomemainget_directionplay_trickcopy_mapget_valid_directionsprint_maptry_movecheck_ghost_collisioncollect_dot_and_check_windo_ghost_logic.
You must translate each function separately to MIPS assembler, following the standard calling conventions used in lectures. When translating a function, you must not make any assumptions about the behaviour or side effects of any other function which is called.
Subsets
This assignment is split into four subsets. Later subsets will involve more complex translation.
Subset Functions Performance Weight Subset 0 print_welcome
5% Subset 1 mainget_directionplay_tick
45% Subset 2 copy_mapget_valid_directionsprint_maptry_move
30% Subset 3 check_ghost_collisioncollect_dot_and_check_windo_ghost_logic
20%
Note that in print_map, the loop which iterates over ghosts does not need to be implemented until you begin subset 3.
This assignment is split into four subsets. Later subsets will involve more complex translation.
| Subset | Functions | Performance Weight |
|---|---|---|
| Subset 0 |
| 5% |
| Subset 1 |
| 45% |
| Subset 2 |
| 30% |
| Subset 3 |
| 20% |
Note that in print_map, the loop which iterates over ghosts does not need to be implemented until you begin subset 3.
Running & Testing
To run your MIPS code, simply enter the following in your terminal:
1092 mipsy pacman.s
Once you have finished your translation, to test your implementation, you can compile the provided C implementation, run it to collect the expected output, run your assembly implementation to collect observed output, and then compare them.
The game takes a lot of input, so it's a good idea to write a file with the input you want to test, then pipe that into your program.
You have been given a file called input.txt as an example.
dcc pacman.c -o pacman
cat input.txt | ./pacman | tee c.out
cat input.txt | 1092 mipsy pacman.s | tee mips.out
diff -s c.out mips.out
Files c.out and mips.out are identical
Try this for different sequences of inputs.
To run your MIPS code, simply enter the following in your terminal:
1092 mipsy pacman.s
Once you have finished your translation, to test your implementation, you can compile the provided C implementation, run it to collect the expected output, run your assembly implementation to collect observed output, and then compare them.
The game takes a lot of input, so it's a good idea to write a file with the input you want to test, then pipe that into your program.
You have been given a file called input.txt as an example.
dcc pacman.c -o pacman cat input.txt | ./pacman | tee c.out cat input.txt | 1092 mipsy pacman.s | tee mips.out diff -s c.out mips.out Files c.out and mips.out are identical
Try this for different sequences of inputs.
Hints
You should implement all the functions from one subset before moving onto the next.
You may find the provided get_seed and random_number function implementations to be useful guidance for your implementations including comments, label names, indentation and register usage.
You should implement all the functions from one subset before moving onto the next.
You may find the provided
get_seedandrandom_numberfunction implementations to be useful guidance for your implementations including comments, label names, indentation and register usage.
Simplified C code
You are encouraged to simplify your C code to remove any loop constructs and if-else statements, and testing that your simplified code works correctly before translating it to MIPS, in a separate file pacman.simple.c.
This file will not be marked - you do not need to submit it.
In order to allow you to ensure that your simplified code works correctly, we have provided a series of automated tests.
You can run these tests by running the following command:
1092 autotest pacman.simple
You are encouraged to simplify your C code to remove any loop constructs and if-else statements, and testing that your simplified code works correctly before translating it to MIPS, in a separate file pacman.simple.c.
This file will not be marked - you do not need to submit it.
In order to allow you to ensure that your simplified code works correctly, we have provided a series of automated tests.
You can run these tests by running the following command:
1092 autotest pacman.simple
Assumptions, Clarifications, and Restrictions
Like all good programmers, you should make as few assumptions as possible.
Your submitted code must be hand-written MIPS assembly, which you yourself have written.
You may not submit code in other languages.
You may not submit compiled output.
You may not copy a solution from an online source. e.g. Github.
Your functions will be tested individually. They must exactly match the behaviour of the corresponding C function and they must follow MIPS calling conventions.
The C code defines constants using #define. Your MIPS translation should use the corresponding provided named constants, in the places where a #define is used in the C code. You should not use a #define constant in your MIPS translation if it is not used in the corresponding part of the C code.
In the get_direction function, you may assume that all user input consists of either empty lines, or lines with exactly one ASCII character. You do not need to handle end-of-file.
There will be a correctness penalty for assignments that do not follow standard MIPS calling conventions including:
Function arguments are passed in registers $a0..$a3.
Function return values are passed in register $v0
Values in registers $s0..$s7 are preserved across function calls.
If a function changes these registers, it must restore the original value before returning.
The only registers' values that can be relied upon across a function call are $s0..$s7, $gp, $sp, and $fp.
All other registers must be assumed to be have, an undefined value after a function call, except $v0 which has the function return value.
If you need clarification on what you can and cannot use or do for this assignment, ask in the class forum.
You are required to submit intermediate versions of your assignment. See below for details.
Like all good programmers, you should make as few assumptions as possible.
Your submitted code must be hand-written MIPS assembly, which you yourself have written.
You may not submit code in other languages.
You may not submit compiled output.You may not copy a solution from an online source. e.g. Github.
Your functions will be tested individually. They must exactly match the behaviour of the corresponding C function and they must follow MIPS calling conventions.
The C code defines constants using
#define. Your MIPS translation should use the corresponding provided named constants, in the places where a#defineis used in the C code. You should not use a#defineconstant in your MIPS translation if it is not used in the corresponding part of the C code.In the
get_directionfunction, you may assume that all user input consists of either empty lines, or lines with exactly one ASCII character. You do not need to handle end-of-file.There will be a correctness penalty for assignments that do not follow standard MIPS calling conventions including:
Function arguments are passed in registers
$a0..$a3.Function return values are passed in register
$v0Values in registers
$s0..$s7are preserved across function calls.
If a function changes these registers, it must restore the original value before returning.The only registers' values that can be relied upon across a function call are
$s0..$s7,$gp,$sp, and$fp.
All other registers must be assumed to be have, an undefined value after a function call, except$v0which has the function return value.
If you need clarification on what you can and cannot use or do for this assignment, ask in the class forum.
You are required to submit intermediate versions of your assignment. See below for details.
Change Log
Assessment
Testing
We have provided some automated tests to help you check the correctness of your translation. To run all the provided tests, execute the following command:1092 autotest pacman
Some of these tests check only a specific function, and some test your whole program. To run run all the tests for a specific function, pass the name of the function to autotest. For example, to run all the tests for the print_welcome function, run the command:1092 autotest pacman print_welcome
You can also run all the autotests for a particular subset. For example, to run all the autotests for subset 0, run the command:1092 autotest pacman S0
To run the autotests which test your program as a whole, run the command:1092 autotest pacman whole_prog
To run all the subset 2 autotests for print_map (not involving ghosts):1092 autotest pacman print_map_S2
1092 autotest pacmanSome of these tests check only a specific function, and some test your whole program. To run run all the tests for a specific function, pass the name of the function to
autotest. For example, to run all the tests for the print_welcome function, run the command:1092 autotest pacman print_welcomeYou can also run all the autotests for a particular subset. For example, to run all the autotests for subset 0, run the command:
1092 autotest pacman S0To run the autotests which test your program as a whole, run the command:
1092 autotest pacman whole_progTo run all the subset 2 autotests for
print_map (not involving ghosts):1092 autotest pacman print_map_S2
Submission
When you are finished working on the assignment, you must submit your work by running give:
give dp1092 ass1_pacman pacman.s
You must run give before Week 8 Monday 23:59:59 (midnight) to obtain the marks for this assignment. Note that this is an individual exercise, the work you submit with give must be entirely your own.
You can run give multiple times.
Only your last submission will be marked.
If you are working at home, you may find it more convenient to upload your work via give's web interface.
You cannot obtain marks by emailing your code to tutors or lecturers.
You can check your latest submission on CSE servers with:
1092 classrun check ass1_pacman
You can check the files you have submitted here.
Manual marking will be done by your tutor, who will mark for style and readability, as described in the Assessment section below. After your tutor has assessed your work, you can view your results here; The resulting mark will also be available via give's web interface.
When you are finished working on the assignment, you must submit your work by running give:
give dp1092 ass1_pacman pacman.s
You must run give before Week 8 Monday 23:59:59 (midnight) to obtain the marks for this assignment. Note that this is an individual exercise, the work you submit with give must be entirely your own.
You can run give multiple times.
Only your last submission will be marked.
If you are working at home, you may find it more convenient to upload your work via give's web interface.
You cannot obtain marks by emailing your code to tutors or lecturers.
You can check your latest submission on CSE servers with:
1092 classrun check ass1_pacman
You can check the files you have submitted here.
Manual marking will be done by your tutor, who will mark for style and readability, as described in the Assessment section below. After your tutor has assessed your work, you can view your results here; The resulting mark will also be available via give's web interface.
