Main Objectives

[Isinlor]

From the Red Book: In Block 1.2 we want you to build a computer application with a user-friendly interface to play a simple game based on computation of chromatic number. This phase links to skills you will learn in (in particular) Introduction to Computer Science 2 (ICS2).

The core of the game is as follows. There is a common core to ensure comparability between project groups. Beyond the core you are free to customize and extend the game as you see fit.

• It is a game for one, human player.

• The computer generates a random graph which is shown on the screen. (The user should be able to specify some basic characteristics of the graph beforehand e.g. number of vertices, number of edges etc.) Alternatively, the user should be able to read in a graph from a file.

• The player is challenged to colour the graph with as few colours as possible. He/she does this by (for example) clicking on vertices and indicating which colour they should have. The computer should warn the user if their current colouring is not valid i.e. if there exist two adjacent vertices that have the same colour.

There are three different game modes possible. All three should be implemented.

• To the bitter end. The player simply has to colour the graph as quickly as possible. The computer does not allow the player to finish until the minimum number of colours has been reached. (This, of course, means that your code should be able to internally compute the chromatic number…)
• Best upper bound in a fixed time frame. The player is given a fixed amount of time and they have to find a colouring with as few colours as possible in the given time. (Here it is not necessary that the user finds the minimum number of colours).
• Random order. Here the computer generates a random ordering of the vertices and the player has to pick the colours of the vertices in exactly that order. Once the colour of a vertex has been chosen, it cannot be changed again. (Note that the player can never get stuck, because they are always allowed to introduce a new colour.) The goal for the player is to use as few colours as possible.

In each game mode there must be a ‘hint’ button which, when pressed, gives the user some computer-assisted help. For example, the computer might propose which vertex should be coloured next, or indicate a subset of colours that should be considered (or avoided) for a given vertex. More sophisticated hint functions will contribute to a higher grade.

Also, there is a document from Introduction to Computer Science: Project Requirements 2018

I have made a list of tasks that need to be done in order to finish this project:

• [ ] Everyone needs to learn how to use GitHub
• [x] A theme for the game? Or just color the graph?
• [ ] GUI Prototype, there is common part that 3 game modes share:
  • selection of the game modes
  • asking for graph specification
  • displaying graph (vertices and edges, arrangement in space)
  • selecting a vertex and color of the vertex
  • warning about wrong coloring
  • hints
  • timer for bitter end and best upper bound
  • score and back to selection of the game modes
• [x] Graph generation (do we limit users to graphs that we can actually solve?)
• [x] Loading a graph from a file
• [ ] Building each of the mode "game flows" i.e. steps in the game
• [ ] "The bitter end" flow:
  1. Specification of the graph and user interaction
  2. End of the game condition (lowest chromatic number found)
  3. Score and back to mode selection
• [ ] "Best upper bound in a fixed time frame" flow:
  1. Specification of the graph and user interaction
  2. End of the game condition (timeout)
  3. Score and back to mode selection
• [ ] "Random order" flow:
  1. Specification of the graph
  2. Guiding user trough the vertices
  3. End of the game condition (all nodes colored)
  4. Score and back to mode selection

Other related tasks from Project Requirements 2018:

• [ ] some schema for automated program testing - there should be some easy enough way to do it
• [ ] building class diagrams (it should be easy and fast, so that we don't waste time on it)

Additionally, we need to prepare:

• [ ] presentation

[Isinlor]

The big question for me is how to organize the work so that we don't block each other.

Three are multiple issues:

1. None of us have experience with whatever GUI library we will need to use
2. You don't have too much experience with Object Oriented Programming (OOP)
3. The main difficulty here is actually building the user interface. User interfaces are quite interconnected. E.g. you need to have a vertex to click on vertex to select a color. So, person doing graph displaying would be blocking person doing color selection.

In my opinion we should start with prototyping, so that everyone can get hang of GUI and OOP. Everyone could try to pick one part of GUI and try to build something that works independently from everyone else. We could later on stitch it together or rewrite based on gained experience, whatever will be easier.

In my opinion there is couple of GUI parts that are easy and amendable to independent work:

• selection of game modes i.e. display window with three buttons, that's all
• asking for graph specification i.e. display window with three inputs # vertices, # edges
• displaying score and button with "back to game modes selection"
• displaying a very simple graph i.e. 2 vertices and an edge (more challenging than the previous ones)

Then there is the issue of creating backbone of the application i.e. we need to have a graph class that keep track of the graph. This class will have no knowledge of GUI, but will be used by other parts of the game.

It needs to provide easy to use interface for:

• displaying a graph
• specifying color of a vertex
• retrieving list of already added colors
• computing chromatic number
• checking coloring correctness
• computing hints

Getting all above done IMO will give use smooth path to finishing the project.

[Isinlor]

Project timekeeping: https://docs.google.com/spreadsheets/d/1np752UbjdXQngAB3N8CpQkXrkS8FtnJw7NpbkqnJLCI/edit#gid=0