CS35 Lab 09: Railway

Due 11:59pm Sunday, May 6 2018

The main goals for this lab are to understand graphs and graph algorithms, and to gain experience with more open-ended development. To that end, you will:

  1. Implement an undirected graph using adjacency lists.
  2. Implement three graph algorithms using your graph classes.
  3. Design an implementation of a simple train game called Railway.
  4. Carry out your design by implementing the Railway game.

As with most assignments this semester, you will be working with a partner. Both partners should be present and working on the code together. You will both be responsible for understanding all concepts, so dividing and conquering is not an option. The academic integrity policy applies to the entire pair; you cannot work or share code with anyone outside your partner.

You and your lab partner will share the same git repository, which is named lab09-<user1>-<user2>.git. Please access your lab by cloning the appropriate git repository, e.g.:

$ git clone git@github.swarthmore.edu:CS35-S18/lab09-lmeeden1-mgagne1.git

Railway Game

Railway is a two-player route-building train game designed by Zach Palmer, inspired by the board game Ticket To Ride. Two players are given a map of possible train routes and take turns laying tracks between them. Players attempt to complete route goals while trying to connect as many cities as possible.

The GUI (graphical user interface) of Railway has been provided for you. When you launch the GUI, it will display something like:

Your job will be to use this GUI to write the game. Along the way, you wil need to implement some of the graph algorithms that we're discussing in class and apply them to the game.

Railway Game Rules

Setup. Railway is played on a map represented by a graph.The vertices of the graph are cities; the edges on the graph are potential railway routes. Routes have a cost in tracks, the resource used to build railway routes. Routes may also have an owner but, at the start of the game, neither player owns any route. Players take turns acquiring routes in order to complete goals while simultaneously connecting as many cities as possible.

Each player starts with a initial number of tracks. Player 1 starts with 35 tracks. Player 2 starts with 50 tracks (to compensate for the disadvantage of making the second move). Routes cost varying numbers of tracks to build.

Each player also starts with three randomly-chosen goals. Each goal instructs the player to connect two cities on the map; these cities are always at least three edges/routes apart.

Playing the game. Players alternate taking turns. Each turn, a player must do one of the following two actions:

  1. Claim a route. A player claims a route by selecting that edge on the game map. In order to claim a route, the following requirements must be met:
    • The route must be unowned.
    • All routes owned by a player must be connected.
    • The player must pay a number of tracks equal to the route's cost.
  2. Pass. A player passes by clicking on the pass button. When a player passes, she gains one track for each city connected by her rail network.

Scoring. The winner of the game is the player with the highest score. A player receives one point for each connected city. The value of each goal equals the length of the shortest path between the two cities, dividing by four, and rounding down.

Example. Consider the following image of a game in progress:

Observe the following:

Starting Code
Your starting repository includes a large amount of code this lab.

The Graph Classes

  • CS35 ADTs folder: a directory containing the C++ declarations of all the ADTs seen in CS35 so far, including graph.h, our Graph ADT as well as edge.h, a declaration of an Edge class. It also contains C++ implementations of the List, Queue, Stack, Dictionary, Priority Queue and Hash Table ADTs using the C++ Standard Template Library (STL). You can use any of them by writing a line like the following in your code
    #include <cs35/stlHashTable.h>
    This directory is in /usr/local/include/cs35 and the compiler automatically looks there for header files.
  • adjacencyListGraph* contains a directed graph implementation using an adjacencyList. You are responsible for understanding this code but should not need to change it.
  • adjacencyListUndirectedGraph* contains a partial implementation of an undirected graph. This class is a subclass of adjacencyListGraph.h and uses the parent class for most of the implementation, by treating each undirected $(u,v)$ edge as two directed edges $(u,v)$ and $(v,u)$. You will complete the removeEdge and getEdges methods.

    Graph Algorithms

    As part of this lab, you will write implementations of the following graph algorithms:
    • Breadth-First Search (BFS)
    • Depth-First Search (DFS)
    • Dijkstra's Algorithm.
    These algorithms are declared in graphAlgorithms.h. Implement them in graphAlgorithms-inl.h.

    Railway Code

    The RailwayGUI class (railwayGUI.h, railwayGUI.cpp) will, when created, produce a window containing whatever information you provide. The resulting object allows you to update the graph on the map, change the message displayed at the bottom of the window, update each player's score, and so on. You can also ask the RailwayGUI class for the next command that the user has sent: pass, place a route, or close the window. Look at main.cpp for some code to get you started, and make sure to read the comments in both main.cpp and railwayGUI.h. We also say more about how to get information from the RailwayGUI in the section Getting Started and Advice below.

    The RailwayGame class (railwayGame.h, railwayGame.cpp) is essentially empty. You should use this class to manage all of the game state in Railway. It should contain information about whose turn it is, what the map looks like (e.g. as a Graph*), information about each player, and so on. We've also given you a Goal class (goal.h,goal.cpp); you're welcome to modify this class in any way you like.

    The starting code for railwayGame.h/railwayGame.cpp is intentially sparse. It is up to you to effectively design this class to facilitate the game play. Spend some time on design before doing any coding of this class. Then implement this incrementally, making sure each piece of code works before moving onto the next. Use the Top-down design skills you learned in CS21.

    The role of the RailwayGame class is to enforce the game logic and to keep track of the current state of the game. For example, it should keep track of whose turn it is, routes claimed by each players, scores, etc. It does not communicate with the RailwayGui object directly, information from the GUI should be passed to the RailwayGame by main. So the RailwayGame class should have methods that will enable it to receive information from main and pass information back to main.

    By the time you are finished, you should have a game that implements the rules of Railway as described above. To earn full credit, your program should function with no crashes or freezes, and play the game correctly (e.g. don't let players take multiple turns in a row, score the goals correctly, etc.) Your UI must also provide the following features:

    • If a goal has not yet completed but is still possible, you must show its value
    • You must indicate when a goal has been completed or when a goal is now impossible to complete
    • If a player makes an incorrect move, you must use the message bar at the bottom of the GUI to explain the problem. (e.g. Player 1: that route has already been taken)

    Running the Game

    Part of the main function (the part that reads graph data from a file and creates the GUI) has already been written for you. You can run your code by runnint make and then

    $ ./railway test_data/Europe 

    The game can take different graphs than Europe. We've included another map for a mystical land called Testaria, the mystical island of tests. Use this map with the command:

    $ ./railway test_data/Testaria

    Once the game has started, main should only pass information back and forth between the RailwayGame object and the RailwayGUI object. main does not really need to know anything about the current state of the game -- for example, it does not need to know whose turn it is, that is the role of the RailwayGame object.

    Getting Started and Advice
    This lab is, by design, more open-ended than in previous labs---you are responsible for part of the design of your railway game code, as well as the actual code itself. Here are some suggestions to get you started.
    1. Workout how you're going to solve this problem before you write any code!. It may help for you to write your plan down or discuss it before you start implementation. Make a list of the information you need to maintain (e.g. player scores, graph,...) and where you plan on keeping it (e.g. the graph class can be a data member of RailwayGame) Do not start coding before you have a design plan
    2. You may wish to create a Player class. If you do, either add its declaration and definition alongside the RailwayGame class, or create new files player.h, player.cpp. If you choose to create new files, make sure to add player.o to the OFILES variable in the Makefile, or you will get some compilation errors.
    3. When writing Dijkstra's algorithm, you will need a minimum priority queue. The priority queue implementation you've seen this semester has been a maximum priority queue. One way to get a minimum-priority queue is to use a maximum-priority queue and invert the priorities. For example, if you have elements with priorities 6, 10, 15, then add them with priorities -6, -10, and -15. That way, when you call removeMax, you'll get the "maximum" priority of -6.
      Alternatively, you could use the implementation of a minimum priority queue we have put at your disposal. Look in the CS35 ADTs folder for details.
    4. You can select a random number using the rand function from cstdlib. For instance, rand()%10 will give you a random number between 0 and 9. You will need randomness when picking goals at the start of the game.
    5. In the game GUI, the label of the edge determines ownership of the edge. Edges with label 0 are unclaimed, while edges with labels 1 and 2 are owned by Players 1 and 2, respectively.
    6. The methods getEdge and getEdges return copies of edges in the original graph. Modifying, e.g., the label of these copies will NOT modify the original graph. If you want to change the label of an edge, you should remove the original edge, and insert a new Edge with the new label and/or weight.
    7. Use the RailwayGUI class to communicate between the game logic designed and implemented by you and the GUI provided by the instructors. For example, one sample turn might have the following sketch:
      /* show current status */
      gui.updateRailwayMap(graph);
      gui.updatePlayerStatus(...);
      
      /* get move from GUI as indicated by mouse click */
      vector<string> move = gui.getNextMove();
      if(move[0] == "close"){
         /* user quit game */
      } else if ( move[0] == "pass"){
         /* handle pass move for current player */
      } else if ( move[0] == "edge") {
         /* current player clicked on edge from 
            move[1] to move[2]. Implement game rules */
      }
      
      If your RailwayGame is designed well, the full game logic can be similar to the code above and placed in main.cpp with a few calls to methods in RailwayGame to manage the game status.

    We strongly recommend getting the graph and graph algorithms implemented and tested before coding the Railway Game. However, it might be helpful to work on the game design while or even before you implement the graph class and algorithms.

    Memory Management

    Your program is required to run without memory errors; run valgrind to eliminate them. For this lab, memory leaks are not a priority. Small memory leaks are acceptable and will not significantly affect your grade. While "lost" memory should not occur in large amounts (e.g. millions of bytes), we encourage you to not spend hours and hours tracking down every last memory leak.

    Commenting and Coding Style Requirements
    Graders will assign minor penalties for poor commenting and coding style.
    Please review the CS35 Coding Style for good C++ style.
    Survey
    When you have completed your lab, answer a few short survey questions in the file README.md.
    Summary

    When you have completed your lab, you should have

    • A working undirected graph implementation using adjacency lists.
    • Implementations of BFS, DFS, and Dijkstra's algorithm.
    • A working Railway game!
    • No memory errors
    • Code which conforms to the style guide above.
    • A completed survey in README.md
    Submit

    Once you are satisfied with your code, hand it in using git. Remember the add, commit, push development cycle. You can push as many times as you like, but only the most recent submission will be graded. You may want to run git status to confirm all modifications have been pushed.