Data Structures and Algorithms

Lab 9: Inroads

Due on Wednesday, December 7th at 11:59 PM. There is a checkpoint for this lab due on Wednesday, November 30th 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 Courselore forum or reach out to the course staff. 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

practicing top-down design
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

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 top-down design must have:

function stubs for public and private methods of the InroadsGame class
code in main.cpp that uses the InroadsGame object to play the game

Your function stubs include return type, function name, parameters, and a lengthy comment describing what the function does. (For an example of appropriate comments, see the .h files in the adts/ directory of your labs.) The functions declared in inroadsGame.h should be implemented in inroadsGame.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. Note that this means that the game will not work properly (e.g. the player’s score might always be -4). However, something will run.

Note that we are not writing throw runtime_error("…") in these stubs. Our goal is to get the skeleton of the program to run even if it does not behave the way we ultimately want. We encourage you to leave comments to help keep track of which functions are not yet implemented correctly. For instance, the InroadsGame class in your top-down design might have a getScore method that looks like this:

int InroadsGame::getScore() {
    // TODO: implement
    return -4;
}

Later, when you implement getScore, you would delete the comment to help track which functions you had not implemented yet. You could then search your whole project for the string “TODO” to see if you forgot to complete anything.

For the second part of the assignment, you will implement your top-down design. You are allowed to modify your design as you implement it, so your early design decisions are an outline, not a rigid structure. 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 will help you to spend your time writing code that you’ll eventually use in the finished program.

Submitting Your Top-Down Design

To submit your top-down design, we will use a Git feature called a "branch". A branch is essentially a name associated with part of your Git repository’s history. Once you have committed your top-down design — be sure you have run git commit and that git status does not show changed files! — you should run the following commands:

git branch tdd
git push origin tdd

This will create a new branch called “tdd” in your Git repository. We will use this to provide you feedback on your top-down design. You don’t need to wait for that feedback if you’re comfortable with your design; you can start filling in your stubs and making changes immediately. The “tdd” branch will not change even if you make further commits and pushes to your main branch.

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:

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:

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.

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.

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.

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

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.

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.

Work out how you’re going to solve this problem before you write any code! You must perform top-down design in this assignment to build stubs for your functions and create a semi-functional prototype of your program. One way to start, for instance, is to 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). Only after you have a plan should you start coding!
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.
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.
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.
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.
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.
Although you should plan your lab before you start writing your code, you should complete the code for 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.

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

Questionnaire

Once you have submitted your lab, please make sure to complete its corresponding questionnaire. The questionnaire will typically take less than a minute and helps us to understand how much work the labs are so we can adjust appropriately. Completing the questionnaire is part of your participation grade, so don’t forget to fill it out!