Data Structures and Algorithms

Lab 9: Railway

Due on Tuesday, December 11th 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

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

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:

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

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:

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.

See the discussion about testing your code below.

Advice

Blueprints

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). Use top-down 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,
    • 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:

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.

Coding Style Requirements

You are required to observe some good coding practices:

Well-dressed people (style)

Summary of Requirements

When you are finished, you should have