Data Structures and Algorithms

Lab 9: Inroads

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

Overview

In this lab, you will apply graph-based algorithms to implement a single-player game called Inroads. The objectives of this lab include

  • implementing graph algorithms,

  • applying those algorithms to solve graph-based problems, and

  • designing software according to given specificiations.

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

Inroads

Inroads is a graph-based single-player game about repairing a community’s aging roads. The player is presented with a map of the existing road network and tasked with selecting which roads to improve. The player scores points based upon how much of the community is able to access services via the newly-improved roadways.

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

inroadsGUI turn1

Your task will be to use this GUI to write the game. As part of this process, you will need to implement some of the graph algorithms we discussed in class.

Rules of Inroads

In order to write a program that allows a user to play Inroads, you will need a formal description of gameplay. The rules for the game are provided here.

Setup

Inroads is played on a map of a region represented by a graph. Vertices in the map represent these locations and are named by strings; the first letter of the vertex’s name indicates what kind of location it represents. There are four kinds of locations:

  • Residential areas, starting with the letter R, are places that people in this community live.

  • A library, guaranteed to be unique on the map, starts with the letter L.

  • Stores, starting with the letter S, represent grocery stores, and other places to buy essential goods.

  • Medical locations, starting with the letter M, include urgent care facilities and hospitals.

Edges on the map represent existing roads between these locations. Throughout the game, each edge is either "improved" (meaning that it is fast and safe to travel) or "unimproved" (meaning that it cannot be used both safely and efficiently). At the beginning of the game, the region’s roads are badly in need of repair: all edges are unimproved.

Edges on the map are weighted in terms of how much time it takes to travel them. Some roads are bumpier or curvier than others or deal with difficult terrain, so this is not a simple Euclidean distance.

Playing the game

A game of Inroads consists of twenty turns. On each turn, the player clicks a single unimproved edge in the graph; that edge becomes improved. The player then gains points based upon how locations are connected to other locations using only improved roads:

  • For each residential location, \(15\) points if that location can reach the library.

  • For each residential location, \(10\) points for each store which is at most two locations away.

  • For each residential location that can reach a medical location, \(\lfloor \frac{420}{n} \rfloor\) points where the shortest route to a medical location takes \(n\) time to travel.

Note that these points are scored at the end of each turn; this means that, if a residential location is connected to the library on the first turn, that residential location will score \(15\) points for its connection to the library on each of the twenty turns in the game.

Example

Consider the following opening to the game. Initially, the game starts with all roads unimproved:

inroadsGUI turn1

We might choose to connect the residential location R03 to the library L toward the center of the map. At the end of this turn, R03 is connected to the library and so scores 15 points. Note that the message box at the bottom of the GUI gives a summary of the points earned from the last turn.

inroadsGUI turn2

We might then choose to connect the library to the store S2. This also connects R03 to that store. At the end of the second turn, R02 can reach both the library (for 15 points) and the store (for 10 points). These 25 points are added to the 15 points from the first turn for a total score of 40 points.

inroadsGUI turn3

Our next choice is to connect R02 to R03. This connects R02 to the library and the store, but the store is more than two steps from R02 and so is too far away to be worth any points. At the end of this turn, we score

  • 15 points because R03 can reach the library

  • 15 points because R02 can also reach the library

  • 10 points because R02 is two steps away from the store S2

We now have a score of 80 points.

inroadsGUI turn4

Gameplay continues until twenty turns have been taken, leading to a result like the one below:

inroadsGUI gameOver

Starting Code

For this lab, you will add code to the following files:

  • graphAlgorithms-inl.h - implementation of graph algorithms

  • inroadsGame.h, inroadsGame.cpp - the inroads gameplay

  • main.cpp - initial code that starts the game

Additional code is provided for you. In particular, 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.

Also, 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.

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 Inroads 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.

Inroads Code

As usual, you can find a link to your GitHub repository on Teammaker.

The InroadsGUI class (inroadsGUI.h/inroadsGUI.cpp) will, when instantiated, produce a window containing whatever information you provide. The resulting object allows you to update the graph, the player’s score, and other displayed information. You can also ask the InroadsGUI object for the user’s next input. Look at main.cpp for some code to get you started and make sure to read the comments both in main.cpp as well as in inroadsGUI.h.

The InroadsGame class (inroadsGame.h/inroadsGame.cpp) has been left empty. You should use this class to represent the idea of a game of Inroads: it should contain the current graph, the player’s current score, and so on. Part of the work of this assignment is making decisions about what helper methods, fields, and other declarations you need to make the game work.

By the time you are finished, you should have a game that implements the rules of Inroads as described above. To earn full credit, your program should

  • Work correctly (no crashes or freezes)

  • Correctly implement the game (don’t let the player pick the same road twice, score according to the rules, etc.)

  • Have no memory leaks or errors

  • Display the player’s score and current turn

  • Use the message log at the bottom of the GUI to explain the player’s score at the end of each turn

Note that the player might choose an edge that has already been improved. If this happens, you should simply ignore that input.

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

./inroads test_data/greybury.map

The argument test_data/a.map specifies a file containing map data to use during gameplay. To make things easier, we’ve included a map of Testington, a town designed to simplify some tests. You can use that map by running this comment instead:

./inroads test_data/testington.map

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

inroadsGUI Testington

Advice

blueprints

OpenClipArt.org

This lab is more open-ended than the previous labs: you are responsible for 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 starting implementation. Make a list of the information you need to keep (graph, player’s score, etc.) and where you plan to keep it (e.g. the graph might be a field of InroadsGame). 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 type of the gui variable in main. Your application should never need a pointer to an InroadsGUI. If you find yourself doing this, stop and ask the course staff to talk with you about your design.

  3. 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.

  4. Make sure to read the documentation of InroadsGUI! It clarifies what kind of data structures are expected by its methods. For instance, the graph representing the map uses a boolean label to indicate whether a road is improved or not: true means improved while false means unimproved.

  5. 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.

  6. 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.

  7. 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. Each time you complete a new feature, commit and push your code!

Coding Style Requirements

As usual, you will also be required to observe good coding practices:

  • Your C++ code must have proper and consistent indentations.

  • You must have proper and consistent usage of spacing & braces for if, else, for, and while conditions as well as class definitions and code blocks.

For more information about good style, please see the course style guide.

Summary of Requirements

When you are finished, you should have

  • An implementation of the three graph algorithms

  • A working Inroads game!

  • No memory errors

  • No memory leaks

  • Code which conforms to the style requirements

  • A completed lab assignment survey from each student