Stanford University
Computer Science 244b: Spring 2014

Assignment 1 - Mazewar: A Multiplayer Computer Game

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

The maze is presented graphically in a window. There are three parts to the window: Only your own rat appears in the bird's-eye view. In the status view, rats that are visible in the rat's-eye view are highlighted.

2. The Rules

The rules of the game are as follows.

3. Keyboard and Mouse Commands

Input of Rat Gesture or Action
AAbout face (180 deg turn)
SLeft turn (270 deg turn)
DForward
FRight turn (90 deg turn)
SpaceBack one space
Mouse LeftPeek left
Mouse RightPeek right
Mouse MiddleThrow projectile

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 4, 2014, 11:59pm
    Jointly submit this form. You will be provided with your team's UDP port. Team Registration
  2. 40% Design: due April 10, 2014, 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 21, 2014, 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 April 21, 2014, 11:59pm
    Individually answer the questions in the last section of this document.

1. Protocol Design and Specification

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

2. Game Implementation:

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:

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.

3. Questions:

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