Settler of Catan

Introduction

Many modern board games can be represented as graphs. This is especially true of games where the board is made of tiles (normally squares or hexagons) connected together to form a semi-random board.

In this assignment you will implement part of the game “Settlers of Catan.” Familiarity with this game is not required for the assignment; any necessary information will be given below.

Part 1 – Graph Implementation

You must implement an unweighted, undirected graph where very vertex and every edge has a colour. Colours are represented by an integer, using the following rules: See image.

This means that if the edge between vertices i and j is red then adjacencyMatrix[i][j] = 1. If vertices p and q are not connected then adjacencyMatrix[p][q] = 0. And so on.... You will need to store the colours of each vertex in an array. i.e. if vertex k is coloured green then vertexColours[k] = 3.

You may implement your graph using adjacency lists or an adjacency matrix. The constructor for your graph should accept two parameters: an adjacency matrix indicating the colours of all the edges and an array of the colours of each vertex.

Part 2 – Input parsing

You will be provided with an input file that looks like this:

4
0 1
1 7
2 7
3 2
0 1 1
1 3 7
0 2 7
2 3 2

The first line indicates the number of vertices in the graph (n). The next n lines indicate the colour of each vertex. Finally, the rest of the lines indicate the endpoints and colours of each edge: start, end, colour. Only non-zero edges will be listed.

The example above represents this graph: See image.

Vertex 0 and edge (0,1) are both red, vertex 3 and edge (2,3) are yellow, and all other edges and vertices are uncoloured (shown as grey above).

Part 3 – Settlers of Catan Road and Settlement Placement

In Settlers of Catan players may build roads and settlements to expand their domain. You must implement the necessary methods to check that a player’s desired road/settlement placement is legal and then update the graph. See image.

Figure 1: Road Placement Condition 1: The red player may place a road on any of these edges: (0,3)(1,3)(1,4)(2,4)(3,5)(3,6)(4,6)(4,7). The yellow player may place roads on any of these edges: (0,1)(0,3)(3,5)(5,6). No player may build roads along the edges (1,2)(2,7)(6,7).

Road Placement

Roads are placed along the edges of the graph. When a player places a road the colour of that edge changes to match the player’s colour. To place a road on an edge the edge must exist and be uncoloured, and one (or more) of the following conditions must be met:

• The player must have either a settlement at one endpoint of the edge (i.e. the vertex at one end must be of the player’s colour)(see figure 1)
• The player must already own a road segment that connects to an uncoloured vertex at one endpoint of the edge (see figure 3)

The following images illustrate these conditions: You must implement the following method to allow players to build roads:

public boolean buildRoad(int playerID, int endpoint1, int endpoint2) { // if player #playerID can build a road between the endpoints // then colour that edge and return true // otherwise return false }

Settlement Placement

Settlements are placed on vertices of the graph. When a player places a settlement the colour of that vertex changes to match the player’s colour. See image.

Figure 2: Road Placement Condition 2: Red may build a road along edge (0,5) because it already owns the edge (5,6) and vertex 5 is uncoloured. Red may not build a road along edge (0,3) because vertex 3 is coloured yellow, even though red owns edge (3,6). Both red and yellow may build a road along edge (2,7)

To place a settlement on a vertex the certex must be uncoloured and all of the following conditions must be met:

• The player must own at least one edge connecting to that vertex
• The vertex must be a minimum of two edges away from any other settlement

You must implement the following method to allow players to build settlements:

public boolean buildSettlement(int playerID, int vertex) { // if player #playerID can build a settlement on the given vertex then // change that vertex’s colour and return true // otherwise return false }

Main Method

Implement a main method that asks the user to enter the name of a text file containing the initial graph. The program should then loop through each player and ask the user to enter that player’s action. Allowed actions are:

• pass: do nothing and move to the next player
• settlement i: build a settlement at vertex i and move to the next player See image.

Figure 3: Red may place a settlement at either vertex 2 or vertex 4; both have red edges leading into them and are at least 2 edges away from any other settlement. Yellow may only place a settlement at vertex 4. Vertices 3 and 5 are both too close to another settlement, and no other vertices have yellow roads leading to them.

• road i j: build a road along the edge (i,j) and move to the next player
• print: print out the graph’s adjacency matrix and the colours of each vertex. Do not move to the next player
• end: stop the main loop and print out the same information as the print command

If the player tries to perform an illegal action (i.e. building a road along a claimed edge, or building a settlement too close to another they should be asked again for an action). All input should be done through System.in (aka “standard input” or “stdin”). You may use Scanner, BufferedReader, or any other useful class in java.io.* to help you parse the input. Your program’s output should look like this (with the user’s input included):

John Smith 1234567
COMP 2140 Assignment 4
Enter the name of file to load:
> foo.txt
Reading file "foo.txt"...
Done
Player 1: road 0 1
Building a red road on edge 0,1
Player 2: road 0 1 Cannot build on edge 0,1
Player 2: road 0 2
Building a yellow road on edge 0,2
Player 3: pass
Player 4: settlement 7
Building a blue settlement on vertex 7
Player 5: end
Orange player ended the game.

Vertices:
0: uncoloured
1: red
2: yellow
3: blue
4: uncoloured
5: uncoloured
6: uncoloured
7: blue