Data Structures and Algorithms

Lab 9: Inroads

Due on Wednesday, December 11th at 11:59pm. 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 software design,
implementing graph algorithms, and
applying those 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! :-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:

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, pharmacies, 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, R03 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 R03 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.cpp - 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.cpp. 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/greybury.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. Your starter code has considerably less structure and you will need to make decisions about how to use the tools available to you. To do this, you should perform a top-down design of the project. You may have learned this technique in your introductory programming course. We discuss that topic here as it pertains to this assignment.

Top-Down Design

A top-down design is a plan for how to organize the various responsibilies and information that appear throughout a program. Planning ahead by developing a design makes the work of implementation considerably easier: with a good design, you’ll encounter fewer bugs and your code will be easier to write. You’ll conduct this top-down design by:

Writing declarations for the fields, public methods, and private helper methods for the InroadsGame class and writing documentation for all of these declarations.
Implementing a stub of each method (so that the method compiles).
Writing an implementation of main.cpp that uses an InroadsGame object to play the game.

You’ll write documentation as you write your declarations to describe what you think each method should do and what invariants you expect out of each field. The goal at this stage is to decide at a high level what behaviors your InroadsGame class should be able to exhibit. Just as a Dog object should be able to bark, for instance, an InroadsGame should perhaps be able to tell you whether the game has ended. Think carefully about which methods you pick, what you expect them to do, and whether it’s possible to accomplish those tasks using a method. We do not write full implementations of these methods yet, though, since this would distract us from our design.

Once you’ve written the declarations for these methods, you’ll want to implement stubs for each of them. A stub is an implementation which is incorrect but which satisfies basic requirements like typechecking. Each of your previous labs has contained stubs for the methods you were expected to write; they often contain bodies like throw runtime_error("Not yet implemented"). This behavior is not correct, but it allows you to compile the project without completely implementing the method. This means that you can work incrementally toward your goal, completing and testing one method at a time. If you declare a method isGameOver, for instance, you might write the following stub for it:

bool InroadsGame::isGameOver() {
    // TODO: implement
    return false;
}

This stub method is incorrect because it never allows the game to end, but we can compile it to perform basic tests of other code in our project. The comment // TODO: implement is helpful because it makes clear that this method hasn’t yet been implemented. If you leave a comment containing the text TODO in each stub, you can later identify methods you haven’t yet implemented by searching your project for that text.

After you’ve stubbed your InroadsGame methods, you can then write a first draft of your main.cpp file, which uses the InroadsGame class. As you write main, pretend that the InroadsGame will behave according to its documentation rather than according to the behavior of the stub. By the time you are finished writing your first draft of main, your program won’t be correct, but you’ll have some structure and something will run. This gives you a starting point; you can then work a little at a time from here in order to complete your lab.

Once you have finished your top-down design, you can then proceed to implement and debug your stubs!

Implementation

Here is some advice for the process of implementing Inroads:

Don’t start implementing until you have a design! We can’t emphasize enough that a good design will save you a lot of effort in the long run. If you have any questions about your design, please feel free to ask.
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. A min-heap is a heap where parents are less than or equal to their children. A min-heap implementation 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, for instance, you might make it possible for players to improve roads. Once that’s working, you might consider tracking which turn it is. After you add each feature, you should test it and commit and push your code before moving on to the next one. This way, you’ll be able to roll back to a previous commit if any of your changes go seriously wrong.

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!