CS35 Lab 09: Railway

#include <cs35/stlHashTable.h>

Graph Algorithms

• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Dijkstra's Algorithm.

Railway Code

The RailwayGame class (railwayGame.h, railwayGame.cpp) is essentially empty. You should use this class to manage all of the game state in Railway. It should contain information about whose turn it is, what the map looks like (e.g. as a Graph*), information about each player, and so on. We've also given you a Goal class (goal.h,goal.cpp); you're welcome to modify this class in any way you like.

The starting code for railwayGame.h/railwayGame.cpp is intentially sparse. It is up to you to effectively design this class to facilitate the game play. Spend some time on design before doing any coding of this class. Then implement this incrementally, making sure each piece of code works before moving onto the next. Use the Top-down design skills you learned in CS21.

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 with no crashes or freezes, and play the game correctly (e.g. don't let players take multiple turns in a row, score the goals correctly, etc.) Your UI must also provide the following features:

• If a goal has not yet completed but is still possible, you must show its value
• You must indicate when a goal has been completed or when a goal is now impossible to complete
• If a player makes an incorrect move, you must use the message bar at the bottom of the GUI to explain the problem. (e.g. Player 1: that route has already been taken)

Running the Game

Part of the main function (the part that reads graph data from a file and creates the GUI) has already been written for you. You can run your code by runnint make and then

$ ./railway test_data/Europe 

The game can take different graphs than Europe. We've included another map for a mystical land called Testaria, the mystical island of tests. Use this map with the command:

$ ./railway test_data/Testaria

1. Workout 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 maintain (e.g. player scores, graph,...) and where you plan on keeping it (e.g. the graph class can be a data member of RailwayGame) Do not start coding before you have a design plan
2. You may wish to create a Player class. If you do, either add its declaration and definition alongside the RailwayGame class, or create new files player.h, 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 some compilation errors.
3. When writing Dijkstra's algorithm, you will need a minimum priority queue. The priority queue implementation you've seen this semester has been a maximum priority queue. One way to get a minimum-priority queue is to use a maximum-priority queue and invert the priorities. For example, if you have elements with priorities 6, 10, 15, then add them with priorities -6, -10, and -15. That way, when you call removeMax, you'll get the "maximum" priority of -6.
   Alternatively, you could use the implementation of a minimum priority queue we have put at your disposal. Look in the CS35 ADTs folder for details.
4. You can select a random number using the rand function from cstdlib. For instance, rand()%10 will give you a random number between 0 and 9. You will need randomness when picking goals at the start of the game.
5. In the game GUI, the label of the edge determines ownership of the edge. Edges with label 0 are unclaimed, while edges with labels 1 and 2 are owned by Players 1 and 2, respectively.
6. The methods getEdge and getEdges return copies of edges in the original graph. Modifying, e.g., the label of these copies will NOT modify the original graph. If you want to change the label of an edge, you should remove the original edge, and insert a new Edge with the new label and/or weight.
7. Use the RailwayGUI class to communicate between the game logic designed and implemented by you and the GUI provided by the instructors. For example, one sample turn might have the following sketch:

   /* show current status */
   gui.updateRailwayMap(graph);
   gui.updatePlayerStatus(...);
   
   /* get move from GUI as indicated by mouse click */
   vector<string> move = gui.getNextMove();
   if(move[0] == "close"){
      /* user quit game */
   } else if ( move[0] == "pass"){
      /* handle pass move for current player */
   } else if ( move[0] == "edge") {
      /* current player clicked on edge from 
         move[1] to move[2]. Implement game rules */
   }
   

   If your RailwayGame is designed well, the full game logic can be similar to the code above and placed in main.cpp with a few calls to methods in RailwayGame to manage the game status.

We strongly recommend getting the graph and graph algorithms implemented and tested before coding the Railway Game. However, it might be helpful to work on the game design while or even before you implement the graph class and algorithms.

Your program is required to run without memory errors; run valgrind to eliminate them. For this lab, memory leaks are not a priority. Small memory leaks are acceptable and will not significantly affect your grade. While "lost" memory should not occur in large amounts (e.g. millions of bytes), we encourage you to not spend hours and hours tracking down every last memory leak.

When you have completed your lab, you should have

• A working undirected graph implementation using adjacency lists.
• Implementations of BFS, DFS, and Dijkstra's algorithm.
• A working Railway game!
• No memory errors
• Code which conforms to the style guide above.
• A completed survey in README.md

Once you are satisfied with your code, hand it in using git. Remember the add, commit, push development cycle. You can push as many times as you like, but only the most recent submission will be graded. You may want to run git status to confirm all modifications have been pushed.