1 Introduction

As a game designer you want to develop your first 2D real-time strategy game. You envision a game where a player is in a procedurally generated terrain map, performing tasks with non-player characters and defending against attacks from enemies. The type of map you want to use will feature several biomes, ranging from deserts to lush rainforests. Each of these biomes will have different characteristics and moving through the different biomes will have different difficulty levels. As this is your first foray into game development, you want to start with a very simple mapa 10 10 square grid where the player can move north, south, east, west, north-east, south-east, north-west, south-west. With these criteria in mind, you decide that a graph is the perfect data structure in which to store all the possible biomes and their connections to each other. In this assignment we will build an undirected graph structure. A node, or vertex, in this graph will represent a terrain biome with its position in the graph being the centre of a 1x1 square. Each node contains information about the nodes position in the map, as well as its terrain features, including the biome, elevation and other locale- and weather-based characteristics. Each node can have up to eight connections, or edges, to other nodes, depending on its position in the map. These edges are what allow travel from one node to another. This assignment consists of two parts. In part A you will complete a number of helper methods that will be useful when implementing search algorithms in the next part. In part B you will generate all the edges between each of the nodes to form them into the 10 10 grid. You will also implement a number of different search algorithms. Depth- and breadth-first searches can both find a path from one node to another, but do it in different ways and can have very different results. They also do not take into account the weight of the edge or, in other words, the difficulty of travelling over particular biomes. The Dijkstras and A* search algorithms both take into account the weight and so 1 more accurately provide a path that is both short and least costly, or difficult to travel. This assignment provides two means by which you can test your code. Running GraphGUI will provide a graphical user interface (GUI) that visualises the graph, the terrains, the nodes and the edges. It also animates the player node, showing the path that your search method calculates. You can use this GUI to view the outcome of your algorithm implementations and troubleshoot1 . There are also unit tests that will give you an idea of the accuracy of your implementations. The tests are not exhaustive and the mark should only be viewed as a guide. Alternative tests will be run by the markers to ensure that your answers are not hard-coded to the tests. Many exception cases are not tested, so you should write your own testing methods. It is suggested that you complete the assignment in the order outlined in the following sections. The later steps rely on the correct implementation of the earlier steps, particularly the connectNodes method.

In this section you will complete some methods that are necessary for building and utilising the graph structure that you will build in section

3. 2.1 Edge

The Edge class represents a connection from one node to up to eight others. An Edge object has three class variables: private Node node1; private Node node2; private double weight;

2.1.1 void calculateWeight()

The weight of an Edge should be calculated using the calculateWeight() method upon creation of the Edge. The weight is calculated as the Euclidean distance between the two nodes multiplied by the average biome weight between the two nodes. This can be represented mathematically as follows: w(e) = d(p, q) ((b1 + b2)/2) where b1 is the biome value of the source node, and b2 is the biome value of the target node. d is a function that calculates the Euclidean distance between two 2D points, p and q.

2.3 Vector2

The Vector2 class represents a 2D point in space and contains an x (horizontal) and a y (vertical) coordinate. For this assignment we are only concerned with finding the distance between two 2D points. A Vector2 object has two class variables: public double x; public double y;

2.3.1 public double distance(Vector2 v2)

This method should calculate the Euclidean distance between two points. The method should be called on one Vector2 object, and passed the second Vector2 object as the parameter. The distance should be returned as a double. The algorithm for calculating the Euclidean distance is as follows: d(p, q) = p (q1 p1)2 + (q2 p2)2

Part B

In this section you will implement a number of methods in the Graph class. First, you will create edges between a given set of vertices. Next, you will implement some helper methods for navigating the graph. Lastly, you will implement several graph searching algorithms.

3.1 Graph

The graph structure that you must build in this assignment forms a 1010 grid, with all edges between the nodes being undirected. Due to the way in which our graph is built, node pairs have mirrored edgesnode 1 has an edge to node 2, node 2 has an edge to node 1. The Graph class has no class variables.

3.1.1 void connectNodes(Node[] nodes)

This method connects all nodes in a given array to form a 10 10 grid-shaped graph. This method must be successfully completed before attempting any other graph searching methods! The provided GUI can help you visualise how well your implementation is functioning. Before completing connectNodes, the GUI should display as shown in Figure 1. Once all of the edges have been correctly created, the GUI will display as shown in Figure 2. Every node in the graph can have up to eight edges, depending on its position. Central nodes will use all eight to connect to all their surrounding neighbours. Think about how many neighbours corner and edge nodes have and how many edges you need to create. In order to develop an algorithm there are some simple constants that you may utilise: The top-left corner of the graph has the 2D coordinate (0, 0). The bottom-right corner of the graph has the 2D coordinate (9, 9). A nodes position is the exact centre of a biome square. In the provided Node[], for every node(i) such that i mod 10 = 0 node(i) is on the left edge. It is very important to adhere to the order of the mappings shown in Table 3 when populating a nodes edge list. Note that a node does not need a list containing eight edges if it only requires three, but the order must be maintainedfor example, east before south, north before south-east.

3.1.2 Edge getEdge(Node source, Node destination)

This methods takes as arguments two Node objects. It should search each nodes list of Edge objects for one that connects the two nodes and return the source nodes edge. If there is none found, the method should return null. 4 Table 3: Edge list indexdirection mappings Edge list index Direction of connected node 0 East 1 West 2 South 3 North 4 North-east 5 South-east 6 North-west 7 South-west

3.1.3 double calculateCost(Node[] vertices)

This method should calculate the total cost of travelling from one node (Node[0]) to a target node (Node[length-1]). The total value should be returned. If the starting and target nodes are the same, the method should return 0.

3.1.4 Node[] breadthFirstSearch(Node start, Node target)

The breadthFirstSearch method takes as arguments two Node objectsa starting node and a target node, respectively. You must implement a breadthfirst search algorithm to find the shortest path from start to target and return that path as a Node array, ordered from start (index 0) to target (index length1). This method should not take into account edge weights.

3.1.5 Node[] depthFirstSearch(Node start, Node target)

The depthFirstSearch method takes as arguments two Node objectsa starting node and a target node, respectively. Unlike the breadth-first search, depthfirst searching will likely not find the shortest path, so you should see drastically different paths being generated. depthFirstSearch should return the path as a Node array, ordered from start (index 0) to target (index length1). This method should not take into account edge weights.

3.1.6 Node[] dijkstrasSearch(Node start, Node target)

The method should use Dijkstras algorithm to search the graph for the shortest path from start to target while taking into account the cost of travel . Visualising this algorithm should show that sometimes the path may not be the most direct route. Rather, it should be the least costly. Your implementation should be a true implementation of the algorithm2 . Your code will be inspected to ensure that an alternative algorithm has not been used. dijkstrasSearch should return the path as a Node array, ordered from start (index 0) to target (index length1).

3.1.7 Node[] aStarSearch(Node start, Node target )

This method should use the A* algorithm, similar to Dijkstras algorithm, to search the graph for the least costly path. Unlike Dijkstras, which searches in all directions, the A* algorithm uses a heuristic to predict the direction of search. The heuristic you should use should be shortest distance, using the distance algorithm you implemented earlier. Your implementation should be a true implementation of the algorithm3 . Your code will be inspected to ensure that an alternative algorithm has not been used. aStarSearch should return a Node array containing the path, ordered from start (index 0) to target (index length1).

In this section you will implement a number of methods in the Graph class. First, you will create edges between a given set of vertices. Next, you will implement some helper methods for navigating the graph. Lastly, you will implement several graph searching algorithms. 3.1 Graph The graph structure that you must build in this assignment forms a 1010 grid, with all edges between the nodes being undirected. Due to the way in which our graph is built, node pairs have mirrored edgesnode 1 has an edge to node 2, node 2 has an edge to node 1. The Graph class has no class variables.

in java, I already did part A and a few from part B im stuck in all 4 search algorithms, its due in a few hours please help.