CS35: Data Structures and Algorithms

Lab 9: Railway

Due on Sunday, May 5 at 11:59 PM. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

We will be using Teammaker to form teams. You can log in to that site to indicate your preferred partner. Once you and your partner have specified each other, a GitHub repository will be created for your team. If you have any trouble using Teammaker, contact your instructor.

Overview

This lab concerns the application of graph data structures to create an interesting program. The objectives of this lab include implementing graph algorithms, applying them to a graph-based problem domain, and performing some amount of design in the development of a piece of software. 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! :-D

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 by building a continuous path between two cities.

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

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. It may help to watch a video of the game in action before reading below. You should understand how the game works before beginning your design.

Terminology

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, using tracks to “pay” for route.

Setup

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.

Each player begins with a score of 0. The game begins with Player 1’s turn.

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 (each vertex connected to one of their edges).

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

If the requirements are met, the player must pay a number of tracks equal to the route cost. A player who places a route does not gain any tracks that turn. If a player attempts to claim a route but does not meet the requirement, the move is rejected and the player must make a different move.

Ending the game

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 city to which they have connected with a route. Completed goals are scored by calculating the shortest 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:

Observe the following:

Starting Code

Your starting repository includes quite a few files. You will be modifying the following ones:

You will also want to read much of the other code that has been provided so that you understand the interface to the Railway game. 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 first and connect them to our discussions about graphs from lecture.

There are two implementations of the graph ADT in the main lab directory: 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.

We have also added an implementation of a min-heap priority queue STLMinPriorityQueue and a hash table implementation STLHashTable in the adts folder.

Graph Algorithms

As part of this lab, you will implement graph algorithms to solve the following problems:

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 GUI

The RailwayGUI class (railwayGUI.h/cpp) implements the graphical user interface. When a RailwayGUI object is created, it produces a window containing whatever information you provide. This 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. Important methods provided by this class include:

You should read the comments in railwayGUI.h for much more detailed descriptions of how these methods work. You should also read through the code and comments in main.cpp for examples and suggestions on how to get started.

Railway Game

The RailwayGame class (railwayGame.h/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/cpp) that you can use to encapsulate information about each route goal. This class does not directly communicate with the GUI - you should primarily focus on using this class to maintain the state of the game.

The main program

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 (turns alternate correctly, players can’t steal each other’s routes, goals are scored correctly, etc.). Your UI must also provide the following features:

Note: you should not pass the GUI object into your RailwayGame class. Instead, main should be responsible for passing data between the GUI and the game class.

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 work with whatever data set you tell it to use. 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

See the discussion about testing your code below.

Advice

Blueprints
Source: 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! 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 keep (player’s score, graph, etc.) and where you plan to keep it (e.g. the graph can be a field of RailwayGame). Only after you have a plan should you start coding.
  2. You may wish to create additional classes to help keep track of certain information. For example, a Player class could store and handle the updates for one player’s information. If you do so, you can either add the class declaration(s) and definition(s) alongside the RailwayGame class or you can create new files, like player.h and player.cpp. If you choose to create new files, make sure to update the Makefile, for example adding player.o to the OFILES variable; otherwise you will get linker errors!
  3. 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.
  4. 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

Use tests.cpp to verify that your graph algorithms are working correctly. You should not begin your railway implementation until all tests are passed.

make tests ./tests

To test your railway game, 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:

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, “still reachable” memory is acceptable; “lost” memory should not occur in large amounts (e.g. millions of bytes).

Coding Style Requirements

You are required to observe good coding practices. You have seen these requirements many times, and should know them by now. If you’re unsure, check previous labs where the style requirements were stated explicitly.

In this lab, you are taking on much more of a design role than on previous assignments. You are expected to adhere to good object-oriented design principles. Most importantly, this means that an object’s data members should be private, and the object’s should handle all of the work that depends on those data members. Also recall the lessons of top-down design from CS21: first start by planning the high-level structure of your program and the tasks it will need to accomplish. Then start breaking those tasks down into manageable pieces you can implement and test one at a time.

Summary of Requirements

When you are finished, you should have

When you are finished with your lab, please fill out the post-lab survey. You should do this independently of your partner. The completion of these forms is part of your participation grade.