With the SnakeOS Operating System in place, you can now construct Snake. Similar to last time, we've broken the task into parts and given you the pseudocode for each part. This is a big project, so make sure to start early!
Important files:All of the files you'll need for the assignment are available in a hw7code.zip Zip archive. You can also view the snake.asm template file.
History: Snake is an old game recently popularized by Nokia cell phones. You control a snake which can move up/down/left/right, and your goal is to collect as many apples as you can. When you eat an apple, however, the snake grows larger, making it more difficult as the game progresses. As a further complication, you are facing off against an evil snake. The game continues until one of the snakes collides with a wall, the other snake, or itself.
Game Basics: Each segment of the snake is a 4x4 square, and thus, as it grows n times, it will consume n x 4 x 4 pixels on the screen. The game will start by drawing the initial heads of both of the snakes, along with the wall and the floor, then begin the main game loop. In any iteration of the loop, two things could happen. First, if the player presses a key to change the direction of the snake, the snake will note the change in direction. Second, a timer will tell the game to advance the snakes at a fixed interval.
Physics and Movement: Each snake is able to move in one of four directions, up, down, left, and right. Thus, at every clock tick, each snake's head position should be displaced by (0,-1), (0,1), (-1,0), or (1,0), respectively. We will need to track each segment of each snake's body so that we may erase the segment when the snake moves (without growing). If either snake collides with anything (except an apple), the game ends immediately.
Snake Object: If you recall from Java, we often used objects as a data structure to capture the state of a given system. Although the implementation of these classes was unimportant to you as a Java programmer, in this assignment, we will actually implement a simple class to capture the state of a snake object. The object will have several member variables (state), and several methods (procedures). Here is a Java-like prototype of the class:
class
Snake {
// State
int HeadOffset; //offset to current Head position in PositionQueue
int TailOffset; // offset to current Tail position in PositionQueue
int GrowCount; //# of segments left to grow (inc'd when apple consumed)
int Direction; //current direction of snake (0=left,1=up,2=right,3=down)
int Color; //color to draw snake
int PositionQueue[2*MAX_SIZE]; //queue positions of snake segments
// Methods
void EnqueuePosition(int x, int y); //enqueue x,y into PositionQueue
int, int DequeuePosition(); //dequeue from head of PositionQueue
bool QueueFull(); //1 if PositionQueue is full, 0 otherwise
int, int GetNext(); //get the next x,y position of the snake
int CheckCollision(); //determine if the snake is about to collide with an object
void AdvanceSnake(); //move the snake
void EvilSnakeAI(); //determine if the snake should change direction
}
The snake objects are pre-initialized and laid out in memory in LC-3 assembly as:
GOOD_SNAKE:
.FILL x0000 ; HeadOff (+0)
.FILL x0000 ; TailOff (+1)
.FILL x4 ; GrowCount (+2)
.FILL x3 ; Direction (+3)
.FILL x8AA8 ; Color (+4)
.FILL 20 ; Start of Position Queue (+5)
.FILL 10
.BLKW 254 ;2x128-2 MAX_SIZE is 128
This encapsulates all of the state from our Snake class. Notice also that instead of specifying the position array as 256 words, we fill in the inital values for x,y and then allocate the remaining 254 words of memory uninitialized (for a total of 256 words).
The data fields of this object can be written by using a LDR instruction. For example, if the pointer to the start of the snake object is in R6, "LDR R0, R6, 4" would load the color of the snake into R0. See the beginning of MAIN for an example.
Queue Data Structure: In order to erase the snake's tail, we need to keep track where the snake has been. We'll use a queue data structure that contains x,y location pairs. When the snake moves, the new location of the snake's head is inserted into the queue; the location of the snake's tail is removed from the queue, which is then erased. Note: in a standard queue, elements are inserted at the "tail" and removed from the "head"; however, in this assignment, we're inserting at the "snake's head" and removing from the "snake's tail", so because of the context the words head and tail are inverted from there usual meaning
Queue Implementation: A Circular Queue: To avoid any sort of memory allocation, the snake object includes only a limited amount of storage for tracking the position of its segments (in our case, 64 x,y pairs). If we continually incremented our position in the queue, we would inevitably run out of memory. We will thus need to be more clever with our usage of allocated memory. A circular queue is an elegent solution to this problem. As with any queue structure, it is first-in first-out. This is implemented by having a contiguous segment of memory and two references into that memory, a head and a tail. A dequeue operation simply advances the head pointer to reference the next element in the array; an enqueue simply advances the tail pointer to reference he next location. However, what happens when the end of the array is reached? When either the head or tail pointer reaches the end of the array it "wraps around" to point back to the zero-th element of the array. As long as the total number of elements in the queue doesn't exceed the capacity of the queue, this approach allows an unbounded number of enqueue and dequeue operations even though the queue is bounded in size.
For example, if we have 8 blocks of space, and we enqueue 8 items, we certainly can enqueue no more. But if we dequeue, the head will now reference the second location (making the first location free). Thus, if we wish to enqueue, the logical place would be at the first location. We can now continually dequeue one peice of data and re-enqueue another without ever running out of space.
Each element of the queue for the snake contains a 16-bit x coordinate and a 16-bit y coordinate, so when the queue advances it is incremented by two.
Global Constants: In some of the subroutines, you'll need some large constant values. These values are stored as global constants. These are already placed within snake.asm, so you need not put them in yourself.
SNAKE_MAX_MASK: .FILL x7F ; 0000000001111111 BACKGROUND_COLOR: .FILL x0000 APPLE_COLOR: .FILL x07B0
Call Graph: To see how the various methods and subroutines interact, see the following call graph (an arrow from "Main" to "Advance Snake" means that the "Main" function calls the "Advance Snake " function):
Register Saving: As in the previous assignment, we will be using callee saving to save and restore registers. This needs to be done at the start of a subroutine or a trap since the caller may expect register values to be preserved when the subroutine returns. Also as before, the save and restore code has been included in snake.asm.
Background Image: We've created a background image to save you the trouble of drawing the walls. They are included in the zip above as the snakebg.obj file. You may simply load this along with the other files when you get to test out the game as a whole. See the snake.lcs script file as a way of loading all the files easily.
Location of Parts: Due to load range concerns, the parts within snake.asm will not actually be in the same order as listed below. Hence, the best way to search for a certain part is to do a find text on the name of the subroutine.
Location of Constants: You might have noticed that within the code stub we provided, the location of constants and other globals seem quite arbitrary and scattered. The reason this is done is because loads and stores have limited range, so these values are placed where they might have the least chance of exceeding that range. If you find yourself with range issues, feel free to move these to other locations in the code that might be better. Just don't put them in the middle of a subroutine or they'll be executed as code!
Solution to Homework 6: Sorry, we won't be handing out a solution to homework 6. If you're having trouble implementing it, please see Prof. Martin or one of the TAs for help.
Testing: Once again, test scripts are included in the zip file above. Note: the test scripts are not yet ready, so they are not yet in the .zip file. You should certainly test the individual routines in this assignment, using both the tests that we give you and your own additional tests (using our tests as a template). Of course, once you get the whole game going, it is much more fun to test by actually playing it. You're also welcome to post on the forums if you have any questions.
Turnin: The only file you need to turn in is your version of the snake.asm file. Similar as before, do the following:
turnin -c cse240 -p hw7 snake.asm
To build the Snake game you will need to write a number of functions, which we describe here. Each part, below, corresponds to a function you need to write. Again, please refer to the call graph for a high-level view of the relationship between these functions. The stub for each of these functions (in snake.asm) clearly defines the function signature (arguments and returned value).
Important: the following pseudocode isn't specific enough to be translated without first understanding what the code is trying to accomplish. As the notation of the pseudocode is ambiguous, you'll need to interpret what we've given you; just don't take it too literally. Of course, you can always ask us if you have any jettisons.We will begin with a routine that is fairly simple yet will produce a crisp result. Place random apple will generate two random numbers and, after ensuring they map to valid coordinates on the screen, draw a green apple at that location. We will need to perform two checks: (1) that the apple's y-coordinate is 30 or less (the x-coordinate can go up to 32 and thus we will limit it purely by an AND) and (2) that the tile we wish to draw the apple on is clear (i.e. background color).
void PlaceRandomApple(void)
do
do
apple_x := RandomNumber()& x1F
apple_y := RandomNumber()& x1F
while apple_y > 30
while GetBlockColor(apple_x,apple_y) != BACKGROUND_COLOR
DrawBlock(apple_x, apple_y, APPLE_COLOR)
You will need the following definitions (provided):
BACKGROUND_COLOR: .FILL x0000 APPLE_COLOR: .FILL x07B0
The code for implementing the circular queue is suprisingly simple. We need to find the address of the beginning of the queue, add pre-incremented head offset, and store the data into that position. To wrap around (in a circular fasion), we are able to AND the head offset by the max size (since it is a power of 2). Notice, however, that we do not check if the queue is full (see Part 4), and thus will overwrite the tail of the queue if there is no more space.
void EnqueuePos(Snake s, int x, int y) s.HeadOffset := (s.HeadOffset+2) & SNAKE_MAX_MASK queue_location = s+5 //see Snake class implementation MEMORY[queue_location+s.HeadOffset] := x MEMORY[queue_location+s.HeadOffset+1] := y
This code is nearly identical to enqueue, except that now we retreive the data from the tail of the queue (wrapping the tail pointer if necessary) and increment the tail pointer. Again, we do not check if the queue is empty, and thus we will retrieve invalid data if it is.
int, int DequeuePos(Snake s) // R5<-x and R6<-y queue_location = s+5 //see Snake class implementation R5 := MEMORY[queue_location+s.TailOffset] R6 := MEMORY[queue_location+s.TailOffset+1] s.TailOffset := (s.TailOffset+2)&SNAKE_MAX_MASK
Finally, we must be able to check if the queue is, infact, full (and then not permit the snake to grow any longer if it is). We will perform a simplistic approach to this and check if incrementing the head position (as performed in enqueuing) will truncate over the current tail position. That is, we are simulating to see if an enqueue would be harmful and returning true (queue is full) if so.
boolean QueueFull(Snake s) // R5 <- 1 if true, 0 if false R5 := (s.TailOffset == ((s.HeadOffset+2) & SNAKE_MAX_MASK))
Each snake has a queue to determine it's current position and a member variable to determine the direction it is moving. With these two pieces of information, we can determine the next location the snake should be (the purpose of this function). We simply need to peek at the current position of the head from the queue and then modify the value based on the current direction of the snake.
int,int GetNext(Snake s)
// R5<-x` and R6<-y`
queue_location = s+5 //see Snake class implementation
R5 := MEMORY[queue_location+s.HeadOffset] // x
R6 := MEMORY[queue_location+s.HeadOffset+1] // y
if s.direction == 0 //left
R5 := R5 - 1
else if s.direction == 1 //up
R6 := R6 - 1
else if s.direction == 2 //right
R5 := R5 + 1
else if s.direction == 3 //down
R6 := R6 + 1
It is important to know what's about to happen to a snake. Is it going to hit a wall? an apple? another snake? itself? This function is going to see where the snake is about to move to and report the status to the caller. We will use the GetNext() function we just created and compare the color of that tile with the possible tile-colors (the subtract instruction, SUB, will come in handy for these comparisons).
int CheckCollision(Snake s)
// >0 if collision at location, 0 if no collision, <0 if apple
x,y := GetNext()
color := GetBlockColor(x,y)
if (color == BACKGROUND_COLOR)
R5 := 0
else if (color == APPLE_COLOR)
R5 := -1
else
R5 := 1
This is one of the most complex functions of the assignment. This function is first going to check to see if the snake is about to collide with a dangerous object (and thus die). If not, then it will check to see if it's about to collide with an apple, and if so, increment the grow count and place a new apple on the screen. Finally, it will enqueue the new position of the snake in the snake's position queue and erase the tail of the snake (if it is not growing). That is, if the snake's grow count > 0, it will not erase the tail of the snake- it'll simply decrement the grow count. Don't be too scared of this code, most of the difficult parts you've already coded!
void AdvanceSnake(Snake s)
collision_flag := CheckCollision(s)
if collision_flag > 0 //collision
HALT
end if
if collision_flag < 0 //apple
s.GrowCount := s.GrowCount + 4 // snake grows by 4 each time
PlaceRandomApple()
end if
x,y := GetNext()
EnqueuePosition(s, x, y)
DrawBlock(x, y, s.Color)
if (s.GrowCount > 0 && !QueueFull(s))
s.GrowCount := s.GrowCount - 1
else
x,y := DequeuePos(s)
DrawBlock(x,y,BACKGROUND_COLOR)
end if
We are now ready to write the main loop. Although we still have to write the AI routine for the evil snake, we may safely ignore that call for now and determine if our 'hero' snake is working properly. We will need to draw the initial head position for the snakes on the board, along with all of the apples. Then we will simply enter a loop of calling GetEvent(), waiting for a response and acting accordingly. If the event was a timer tick, we will call AdvanceSnake() on both the good and evil snakes. Please examine the GOOD_SNAKE and EVIL_SNAKE defintions in snake.asm to help understand the snake object.
void main(void)
//Initialize heads on screen
DrawBlock(GOOD_SNAKE + 5, GOOD_SNAKE + 6, GOOD_SNAKE + 4) // x, y, color
DrawBlock(EVIL_SNAKE + 5, EVIL_SNAKE + 6, EVIL_SNAKE + 4) // x, y, color
PlaceRandomApple();
PlaceRandomApple();
PlaceRandomApple();
PlaceRandomApple();
PlaceRandomApple();
while (true)
event_type := GetEvent()
if (event_type<0) // quit
HALT
else if (event_type>0) // direction
good_snake.Direction = event_type - 1
else // timer
AdvanceSnake(good_snake)
EvilSnakeAI(evil_snake) // comment out for initial testing
AdvanceSnake(evil_snake) // comment out for initial testing
do loop
The final part of the assignment. The evil snake needs to be more intelligent (instead of just running into the wall). Here we will do two things. First, we will randomly have the snake turn (with a 1 in 8 chance). Because the chance of the last three bits of a binary number being 000 is 1/8 (think of all eight possibilities for 3-bits, one of these is 000), we will take a random number, examine the lower 3 bits ( &111b ), and turn the snake if these are zero (thus giving the snake about ~12.5% chance of turning). Next, we will see if the snake is going to collide with anything (regardless of whether we've specified a new direction), and if it is about to hit a wall, we will try to turn it in any direction that will prevent the collision. It might be simple, but it's rather good at surviving!
void EvilSnakeAI(Snake s)
rand = RandomNumber() & 0x7
if (rand == 0 || CheckCollision(s) > 0)
s.Direction = RandomNumber() & 0x3
counter = 4
while ((CheckCollision(s) > 0) && (counter > 0))
s.Direction = s.Direction + 1
s.Direction = s.Direction & 0x3
counter = counter - 1
do loop
If you are a master LC-3 hacker and you finish HW 7 early, you might want to add some more features to the game. For example, you might want to display a score to the text display (or maybe to the graphical display!). BUT... Make sure your code works according to the above specifications before you embark on anything extra. Also, please make sure any extra features you add do not change the behavior of the program as we have specified (i.e., make sure you don't confuse our testing process).
Note: We know some of you may be enthusiastic, but don't go nuts on extra features and miss out on other important work!