Introduction | Game Description | Doing the Assignment | Submitting the Assignment | Programming Framework

Introduction

You are to design and implement cs244b Mazewar, a distributed, multiplayer game that is described below. So that you do not have to deal with user interface and other framework issues, you have been provided with a single-player Mazewar game.

Game Description

cs244b Mazewar is a distributed, multiplayer game that allows each player to control a rat in a maze. A player receives points for tagging other rats with a projectile and loses points for being tagged.

The game is based on the X Window System version of Mazewar, which is in turn based on the classic game of Mazewar that ran on the Xerox Alto in the 1970s. It is also based on Amaze, a multi-player game with a distributed implementation on top of the V kernel. Amaze is described in [E.Berglund and D.R.Cheriton. Amaze: a multiplayer computer game. IEEE Software. 2(3):30-39, May 1985].

1. The Interface

• Rat's eye view: The upper section is a perspective view of a rat's view forward.
• Bird's eye view: The top level view of the maze showing the position and orientation of a rat from above. It should also show a missile in flight.
• Status view: The bottom area is reserved for text to be used to report the scores and status of other players.

2. The Rules

• Each instantiation of the program is a separate player.
• Each player controls a single rat in the maze.
• The maze consists of a 32x16 array of cells. Each cell is either occupied by a wall, a rat, or is empty.
• A player sees the top level view of the maze, but only their own rat's position and orientation in the bird's eye view. They must be able to see their own projectile posistion. Your protocol can have them see all projectiles or just their own.
• A player sees any "visible" (not blocked by intervening walls) opposing rats in the perspective view.
• There are commands which allow a rat to peek left and right around corners without exposing itself (perspective view only).
• There are commands to rotate your rat 90, 180, and 270 degrees, move forward or backward by 1 cell, and throw a projectile in the direction your rat is facing.
• Projectiles have a finite speed. (You can choose it, e.g. 1 cell every 200 milliseconds.)
• A rat needs some amount of time to recuperate (your choice of how long) after throwing a projectile. It can do anything except launch another projectile. It is an allowable design decision to limit the number of outstanding "missiles" a rat can own to one, and (i.e., a rat can launch a missile as soon as the earlier one hits a rat or a wall). Alternatively, a rat can recover after, for example, two seconds. Keep this as simple as possible.
• A rat touched by an opponent's projectile is tagged instantly. Projectiles pass through their own rat transparently, without causing any harm. Projectiles are the full width of the corridor, so that if a projectile passes through any cell, it certainly tags the rat in that cell.
• A rat that is tagged loses 5 points. A rat that tags another rat gains 11 points. A projectile that is thrown costs 1 point.
• When a rat is tagged, it reappears at a random position (in a clear cell only, not one occupied by a wall or another rat) with a random orientation (although not facing a wall) in the maze.
• More than one rat can't be in the same square at the same time.
• More than one projectile may be in the same square at the same time.
• One projectile can tag at most one rat.

3. Keyboard and Mouse Commands

These commands are already implemented in the framework.

Doing the Assignment and Deadlines

Students should try to form teams consisting of at least two people but not more than three people (Team Registration). You will then be provided with a unique UDP port number. If you're having trouble forming a group, post a note to the Piazzza discussion forum.

The teams are for the purpose of designing and specifying a protocol for the game, not for jointly writing code. You may not share code; you may not use code from the X version of Mazewar, nor may you use code from the V kernel version of Amaze. The members of a team should not work together to answer the questions in part three; we are interested in your individual answers.

You are each required to write a complete implementation of cs244b Mazewar and demonstrate that your program interacts correctly with those of the other members of your team.

We suggest that you stick to the rules provided in the Mazewar game description, but you are free to make any additions that you think improve the game, as long as

1. you document them clearly,
2. the result is still a distributed system about which you can meaningfully answer the questions below, and
3. you clear all changes with us before you implement them.

What to Submit:

1. Teams: due April 5, 2013, 11.59pm
   Jointly submit this form. You will be provided with your team's UDP port. Team Registration
2. 40% Design: due April 13, 2013, 11.59pm
   Jointly design the distributed game of Mazewar as described in the Mazewar game description. You must submit the Team Registration form before submitting the design.
3. 40% Program: due April 23, 2013, 11.59pm
   Individually implement the game according to the specification you agreed upon in part one, and using the framework provided for you.
4. 20% Questions: due Apr 23, 2013, 11.59pm
   Individually answer the questions in the last section of this document.

Your team is to jointly design the specification of the protocol used by the game. The specification must be complete enough so that all members of the team can independently implement a mazewar program to the specification and have it interoperate with each of the other programs. Programs running on different architectures (e.g. Sun Ultra or HP PA-RISC) need to be able to correctly interact with each other.

The protocol design should specify a distributed game. A single centralized server that treats the nodes as terminals is not acceptable. Using a distinguished node tends to create a centralized single point of failure, so this approach should be avoided if possible, or at least handled (and justified) carefully. You are also not allowed to use broadcast to disseminate state. Sample code for joining a multicast group is provided in the netInit() function.

The description of your specification should have the information that you would expect to find in an RFC for Mazewar. One example you can work off of is the Gnutella Specification, it should give you some idea of what we are looking for. Be concrete and specific in the protocol. The protocol should describe how it meets the requirements and provides sufficient consistency, but don't convolute the specification with justifications; that is the focus of the third part of the assignment.

The protocol specification should include:

• The packet types and formats; a reasonable model to follow is any Internet RFC.
• The sequencing and semantics of the packets, including how a user locates, joins and leaves a game of Mazewar. What happens if a player loses contact with one player? What about losing contact with all of the other players?
• Timings of protocol events, and how they provide for sufficient consistency for the game state.

The team design and specification of the communication protocol will be graded for the group as a whole (i.e., a single grade will be given to all members of the group), based on the following criteria:

1. Correctness: Does the design support a distributed game of mazewar that conforms to the specification in the game description?
2. Clarity/Simplicity: Is it clear enough for independent implementors to implement it consistently? Does it avoid mechanism that does not contribute to the game play? (Lack of clarity and extraneous complexity can increase development time and can further detract from programs in the group interoperating - a further potential penalty.)
3. Performance: Does the protocol minimize the network packet traffic and also avoid extraneous processing load on each node? (We are interested in designs avoiding unnecessary overhead. Extreme optimization is not important.)

A team may revise its specification between the time it is submitted and the final due date as long as the revisions are documented and justified. If you revise your specification, resubmit one copy of it for your team at the time that individuals submit parts two and three of the assignment. Along with the updated specification include a ChangeLog file describing the changes and the reason for the changes. In addition, each individual submission of part two/three should state that the specification has been revised.

Implement Mazewar using the framework provided, conforming to the game description. The protocol used to communicate between the nodes in the game and the behavior of the nodes must obey the specification created by your team in part one.

The implementation will be graded on a demo of the running program as well as the submitted source code. Each group will sign up for a demo in the myth computing cluster during the week of the final due date (signups to be announced later). At demo time, each member of your group should be prepared to run his/her program with those of the rest of the group, and also be prepared to rebuild the program from source code if so requested.

We don't expect you to have to make many changes outside of toplevel.cpp and mazewar.h. However, there are a couple of implementation choices that you might consider that do require such changes:

• If you listen on more than one socket at a time, you need to modify the code in NextEvent(). This function is called by play() in toplevel.cpp and is implemented in winsys.c.
• You should be able to write your program without needing to modify the name of M (class MazewarInstance), the representation of the maze itself, or the slots in M that refer to the location and orientation of the local rat, and the peek, etc. If you decide that you absolutely must change one or more of these things, you must modify the references in the code to the maze (M->maze), to the location of the local rat (M->xloc, M->yloc and M->dir) and to m->MyRatId, M->xPeek, M->yPeek, and M->dirPeek. There are a lot of references in toplevel.cpp (which we expect you modify substantially anyway), none in display.cpp, RepaintWindow(), initMaze(), RandomEvent() in winsys.c, and MazeInit() and getMaze() in init.cpp.

Your implementation must also support setting the rat name, x pos, y pos, and direction (one of {n, s, e, w}) via the command line, in that order, separated by spaces. One-word names are sufficient. If none of these 4 values is provided, you program should start as usual, and ask for a user name and generate a random rat position and orientation. You do not need to do input validation and a single-word name is acceptable.

Answer each of the following questions in the answers.pdf file sent with your code.

1. Evaluate the portion of your design that deals with starting, maintaining, and exiting a game - what are its strengths and weaknesses?
2. Evaluate your design with respect to its performance on its current platform (i.e. a small LAN linked by ethernet). How does it scale for an increased number of players? What if it is played across a WAN? Or if played on a network with different capacities?
3. Evaluate your design for consistency. What local or global inconsistencies can occur? How are they dealt with?
4. Evaluate your design for security. What happens if there are malicious users?

Submitting the Assignment

How to Submit Group Info:

Submit your group information using this form: Team Registration

How to Submit the Protocol Design Document:

Name your protocol design document as follows: "<team-name>_<sunet-id-1>_<sunet-id-2>_pdd.pdf" (e.g. ratpack_aljunied_liuj11_pdd.pdf).

Email your protocol design document to: "cs244b-ta at cs". Please repeat your group information (group name, members, and email addresses) in the email.

How to Submit the Code and Questions:

1. Go into your project directory
2. CLEAN UP TEMPORARY FILES (make clean), do not include extraneous sub-directories etc
3. Include your question answers in the directory as answers.pdf
4. Include your group's protocol document in the directory as protocol.pdf
5. If your group has changed protocol.pdf from your original submission, then include a ChangeLog file describing the changes and the reason for those changes.
6. Run /afs/ir.stanford.edu/class/cs244b/bin/submit

Programming Framework

The game framework is in /afs/ir.stanford.edu/class/cs244b/mazewar. Copy and unzip MazewarSpring2013.tar.gz to your directory. You can make mazewar and run it (the executable is mazewar). The provided code is for a single player - it executes entirely locally, and the throwing of projectiles is not implemented. You can play with a robotic rat by running mazewar -robot (use -time_interval << msec >> to control the speed of the robot).

We assume that all students are familiar with C and Unix and have some programming experience. We expect that you have the ability to write code that sends and receives packets over the network.

The programming assignment will be tested on myth machines, so please make sure they work there.

Some routines that are provided to you are described briefly below. Also, sample code for opening a multicast socket and joining a group is provided in the function netInit() in toplevel.cpp.

1. Utility and Initialization Routines

NewPosition(MazewarInstance::Ptr m) sets x, y, and dir to a random point in the maze, guaranteed to not be inside a wall, and not facing a wall. You will need to modify this in order to guarantee that a randomly placed rat is not placed on top of another rat. (toplevel.cpp)

MazeInit(int argc, char **argv) is called to initialize the maze, the window system etc. Pass in argc and argv as passed to the toplevel program. (init.cpp)

2. Display Routines

The following routines are used to control the display manager. They are not meant to control the state of the game.

SetRatPosition(RatId ratId, Loc xpos, Loc ypos, Direction dir) informs the display manager that the position of rat # ratId is (xpos,ypos), facing in direction dir. (display.cpp)

ClearRatPosition(RatId ratId) informs the display manager that rat # ratId is no longer to be displayed. (display.cpp)

ShowView(Loc x, Loc y, Direction dir) shows the perspective view from position (x,y) in direction dir. Other rats are displayed as set by previous calls to SetRatPosition(). (display.cpp)

ShowPosition(Loc xloc, Loc yloc, Direction tdir) shows the local rat's position as an arrow in the top-down view. (display.cpp)

DrawString(const char* msg, uint32_t length, uint32_t x, uint32_t y) draws a string on the specified location of the screen. You should call this function and display message at the center of the perspective screen when your rat tags other rats or is tagged by others. (winsys.cpp)

3. Input Routines

The following routines are used to interact with the user. They all take an argument, prompt, which is a string used to prompt a user, and they all return their values in the locations pointed to by the other arguments, and all of the returned values are allocated out of the heap by malloc. You can manage the memory accordingly.

getName(char *prompt, char **ratName) returns a user name, if none is given the username (login ID) is determined from the environment. When getName ("Enter foo", &r) returns, r points at the name of the rat. (init.cpp)

getString(char *prompt, char **string) prompts for an arbitrary string. CR alone returns NULL. The string is returned in string. (init.cpp)

NextEvent(MWEvent *event, int socket) returns the next X event, or an arrival of a network packet on socket. If your implementation requires you to listen on more than one socket at a time, you must modify the function NextEvent. (winsys.cpp)