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:
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 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:
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:
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:
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.
graphAlgorithms.h
. Implement them
in graphAlgorithms-inl.h
.
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:
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.
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.
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.0
are unclaimed, while edges with labels 1
and 2
are owned by Players 1 and 2, respectively.
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.
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.
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.
When you have completed your lab, you should have
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.