Whoever is gonna solve this I can send him the zip file with the needed classes (including getter,setters, methods etcc..) and pdf. I already did the code for calculateWeight, distance, getEdge, connectNodes and calculateCost, I only need help in the searching methods please, its due tomorrow.

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.

2 Part A 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;

3 3 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.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).