CS35: Lab 9: Railway Game

Due Friday, April 28 at 11:59pm. There is also a checkpoint for this lab due on Wednesday, April 19 at 11:59pm.

Overview

This lab concerns the application of graph data structures to create an interesting program. The objectives of this lab include:

  • practicing top-down design

  • designing software according to given specifications

  • implementing graph algorithms

  • applying these algorithms to solve graph-based problems

This lab should reinforce the graph algorithms you learned in lecture and improve your programming skills. In order to complete the above objectives, we’re going to write a game!

As usual, you can select your partner using Teammaker.

The URL for your repository will be

git@github.swarthmore.edu:cs35-s23/lab09-<your-teamname>

Top-down design

There are two due dates for this lab. For the first due date you will complete a top-down design for your program. Your design must have:

  • data members of the RailwayGame class

  • function stubs for public and private methods of the RailwayGame class

  • code in main.cpp that uses the RailwayGame object to play the game

If you decide to create additional classes in your solution, then these additional classes should also contain data members and function stubs for all methods.

Your function stubs should include return type, function name, parameters, and a thorough comment describing what the function does. For examples of appropriate comments see the .h files in the /adts directory of your labs. The functions declared in railwayGame.h should be implemented in railwayGame.cpp as placeholders that do nothing, and only return dummy values. Your completed top-down design should be compileable and runnable code, so all return types should match what is expected. Your game will not work yet, however, something will run.

Note that you should not be throwing errors from within these stubbed out functions. Our goal is to get the skeleton of the program to run even if it does not behave the way we ultimately want.

For the second part of the lab you will implement your top-down design in an incremental fashion, working on gradually adding working features into the game. You are allowed to modify your design as you implement it. Your early design decisions provide an outline, not a rigid structure that must be followed at all costs. The purpose of working on the design first is to make sure that you have thought about which methods and data you will need, and how you will use them before you dive into the specific implementation details. This up-front design work will make your coding more efficient in the long run.

To submit your top-down design be sure to add, commit, and push your code prior to the first deadline. If you finish your design early, send an email to your lab instructor. We will try to reply with feedback as we receive designs.

To give you a sense of the incremental development that we are expecting, you can try out the railway game at different stages during one of our implementations. 

cd /home/meeden/public/cs35/railway_stages
There are several different versions here that you can try:

  • railway_just_TDD This is a top-down design that runs, but does not actually implement anything yet.

  • railway_connected_gui This connects clicking an edge to change what each player owns, however, there is no checking of whether the selected edge is legal.

  • railway_but_goals_not_checked This adds the goal generation, restricts players to only taking edges that are already connected to their graph and ensures that they have enough tracks to claim it. Goal values are not yet calculated correctly.

  • railway_completed This is a completed implementation.

For example to try running the top-down design do: 

./railway_just_TDD test_data/Testaria

Railway

Railway is a two-player route-building game. The players are presented with a map of possible train routes and take turns laying tracks between them. Players are attempting to complete route goals while trying to connect as many cities to their rail lines as possible.

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

railwayGUI

Your task will be to use this GUI to write the game. In the process, you will need to implement some of the graph algorithms that we discussed in class and apply them to the game.

Rules of Railway

To write a program to allow users to play Railway, you will need a formal description of gameplay. The rules of the game are provided here.

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 has a number of "tracks", the resource used to build railway routes. Routes cost varying numbers of tracks to build. Player 1 starts with 35 tracks. Player 2 starts with 50 tracks (to compensate for the disadvantage of making the second move).

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

Playing the game

Players alternate taking turns. A player must take one of two actions each turn: either pass or place a route. A player who passes gains one track for each city connected by that player’s network.

To place a route, the following requirements must be met:

  • The route must be unowned.

  • All routes owned by a player must be connected.

  • The player has a number of tracks equal to or greater than the route’s cost.

To place a route, the player must pay a number of tracks equal to the route cost. The route must be unowned; a player cannot place a route owned by the other player. A player who places a route does not gain any tracks that turn.

The winner is the player with the highest score once all of the routes have been claimed.

Scoring

Each player’s score can be determined entirely by the state of the game board. A player receives one point for each connected city. Goals are scored by calculating the lowest cost path between the two cities (even if this is not the route the player took to connect them), dividing by four, and rounding down.

Example

Consider the following image of a game in progress:

railwayGameInProgress

Observe the following:

  • Player 1 (green) is out of tracks and will be forced to pass. This will give Player 1 a total of 6 more tracks (one for each of AMS, FRK, BRN, FLC, ROM, and CAT).

  • Player 2 (purple) could acquire the route from MAD to SEV next turn (8 tracks) but cannot afford the route from MAD to LIS.

  • Player 2 cannot acquire the route from WAR to MIN next turn, since that route is not next to a city that Player 2 has already connected.

  • Player 1 has completed the goal "AMS to CAT" using the cheapest possible path (in terms of edge weight). This is worth (5+7+11+5+12)/4 which is 10 points. Player 1 has also connected six cities, for a total score of 16 points.

  • Player 2 cannot complete the goal "BRN to CAT" because Player 1 owns the only route that connects CAT to the rest of the map.

Starting Code

Your starting repository includes quite a few files this time around. The following sections discuss these files and what you should do with them.

Graph ADT

As usual, the adts/ directory contains the ADT declarations and implementations for you to use in this assignment. The graph.h and edge.h files are new; take a look at them.

There are two implementations of the graph ADT in your starter code: AdjacencyListGraph and AdjacencyListUndirectedGraph. The latter is a subclass of the former which changes the insertEdge and removeEdge methods to simulate an undirected graph: each time an edge is added with insertEdge, for instance, another edge is also added in the opposite direction. Both of these classes have been implemented for you, but you may wish to examine them.

Graph Algorithms

As part of this lab, you will write implementations of the following graph algorithms:

  • Depth-first search

  • Breadth-first search

  • Dijkstra’s algorithm

These algorithms are required even if you can avoid using one of them in your Railway implementation. You will implement these algorithms in graphAlgorithms-inl.h. The provided unit tests in tests.cpp are designed to verify the correctness of these algorithms.

Railway Code

The RailwayGUI class (railwayGUI.h/railwayGUI.cpp) will, when instantiated, 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 object 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 that file as well as in railwayGUI.h.

The RailwayGame class (railwayGame.h/railwayGame.cpp) has been left empty. You should use this class to represent the idea of a game of Railway: it should contain information about whose turn it is, what the map looks like (as a Graph*), information about each player, and so on. You have also been provided with a Goal class (goal.h/goal.cpp); you are welcome to modify this class in any way you like. Part of the work of this assignment will be making decisions about what helper methods, fields, and classes you need to make the game work.

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 (no crashes or freezes) and play the game correctly (don’t let players take each other’s routes, score goals correctly, etc.). Your UI must also provide the following features:

  • If a goal has not yet been completed but is still possible, you must show its point value.

  • You must indicate when a goal has been completed.

  • 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.").

It is optional for you to implement the feature that your game will recognize when a goal has become impossible to achieve. If you successfully implement this feature, you can receive extra credit on the lab.

Running the Game

Part of the main function — which reads the graph data files and creates the GUI — has been written for you. You can run your code (or even the initial starting code) by running make and then

./railway test_data/Europe

The game will use test_data/Europe to find the files it will use to run your game. To make testing easier, we’ve included a map of Testaria, the Island of Tests, which you can use by running the following command instead:

./railway test_data/Testaria

This will load a considerably simpler map to use for testing as shown below.

Testaria

See the discussion about testing your code below.

Advice

blueprints

OpenClipArt.org

This lab is more open-ended than the previous labs: you are responsible for part of the design of the application as well as the code. Here are some suggestions to get you started.

  1. Work out how you’re going to solve this problem before you write any code! Make a list of the information you need to keep (player’s score, graph, etc.) and where you plan to keep it (e.g. the graph can be a field of RailwayGame). Use [top-down design](https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design), which you may have learned in CS21. Only after you have a plan should you start coding!

  2. Do not change the gui variable in main to be dynamically allocated. You should not have to pass the GUI to any of the other routines that you write. If you find yourself doing this, stop and ask one of the course staff to talk with you about your design.

  3. You may wish to create a Player class. If you do so, you can either add its declaration and definition alongside the RailwayGame class or you can create new files player.h and 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 linker errors!

  4. You can select a random number using the rand function from the stdlib.h library. For instance, rand()%10 will pick a random number between 0 and 9, inclusive. You will need this when picking goals at the start of the game.

  5. When writing Dijkstra’s algorithm, you will need a min-heap. Although we haven’t used it before, such a heap is provided in the adts directory.

  6. In the game GUI, the label of an edge determines who owns it. Edges with label 0 are unclaimed; edges with label 1 or 2 are owned by the corresponding player.

  7. Note that the Graph class’s getEdge and getEdges methods return copies of the edges in the graph. Modifying the values they return will not change the graph; you will need to add and remove edges from a graph directly if you want to change it.

  8. You may create as many Graph objects as you like. For some parts of the game, you may find it easiest to

    • copy the graph by getting all of the vertices and edges, creating a new graph and inserting the vertices and edges,

    • make changes to the copy,

    • run one of the graph algorithms on that copy,

    • and then delete the copy, leaving the original graph unchanged.

  9. Although you should plan your lab before you start writing your code, you should code one feature at a time! First, get the game working without objectives or the pass option: just allow players to claim routes. Then, add features one by one until you have a working game. And each time you complete a new feature, commit and push your code!

Testing

As stated above, you can launch your game on a smaller, more predictable test map by running the following:

./railway test_data/Testaria

This map is designed to help you track down bugs. It has four vertices on each side of the map and one vertex in the middle which connects them. If your game is working properly, then the following should be true:

  • Every legal goal connects an L vertex with an R vertex (because all of the other vertices are too close to be a legal goal). The MID vertex never appears in a goal.

  • If either player acquires one of the edges touching the MID vertex, the other player’s goals immediately become impossible.

  • The map always loads correctly. If loading the Testaria map sometimes causes the application to freeze, you probably need to think carefully about how you’re choosing goals at the start of the game.

Although the above does not guarantee that your code is correct, it gives you a means to determine if your code is generating and handling goals correctly.

Memory

Your code must run without any memory errors; make sure to use valgrind to find them. Memory leaks, on the other hand, are acceptable in small amounts and will not significantly impact your grade. In particular, your application should not leak more memory the longer the game is played; applications which leak constant memory will not be penalized, while applications that leak non-constant memory (e.g. more memory after each move) will be penalized slightly.

Summary of Requirements

When you are finished, you should have

  • Implementations of the three graph algorithms

  • A working Railway game!

  • No memory errors

  • Code which conforms to the style requirements, which includes commenting all methods and data members for any classes that you create