Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
INFS 2042 Data Structures Advanced
Assignment 1 – Pathfinding
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 map, performing tasks with non-player characters and defending against
attacks from enemies. The type of map you want to use will feature different elevations, visualized as a height
map where blue is a low elevation and red is a high elevation. As this is a strategy game, moving between
different elevations has the added difficulty of being more costly for characters.
As this is your first foray into game development, you want to start with a very simple map—a 10 × 10
square grid where the player can move in eight directions: 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 elevations 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 position on the graph being the centre of a 1x1 square. Each node contains information about the node’s
position in the map, as well as its elevation. 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 between elevations. The Dijkstra algorithm takes into account the
weight and so more accurately provides a path that is both short and least costly, or difficult to travel.
3Figure 1: The GUI before completing the connect Nodes method.
GUI is helpful for understanding how your graph searching algorithm implementations are functioning. Not
much will happen at this stage, but you will see an animation played as you complete the assignment tasks are
completed (such as shown in Figure 2). You are now ready to start working on the assignment tasks described
in the following sections.
Figure 2: The GUI after completing the connect Nodes method.
45
3
Part A
In this section you will complete some methods that are necessary for building and utilizing the graph structure
that you will build in section 4, Part B.
3.1 Position
The Position 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 Position object
has two class variables:
public double x;
public double y;
The Position class has the following method that you need to implement:
public double distance(Position v2)
This method should calculate the Euclidean distance between two points. The method should be called on one
Position object, and passed the second Position object v2 as the parameter. The distance should be returned as
a double. The algorithm for calculating the Euclidean distance is as follows:
𝑑(𝑝, 𝑞) = √(𝑞𝑥 − 𝑝𝑥) 2 + (𝑞𝑦 − 𝑝𝑦) 2
3.2 PositionTest
PositionTest will assign marks as shown in Table 2. You can run the test by running the project as JUnit Test,
instead of Java Application. As mentioned in the introduction, these are just provided as a reference for you to
test your own solution. Actual marking will vary based on the quality and solidity of your code.
Table 2: PositionTest mark allocation
Test
Marks
distance
5
Total:
5
3.3 Edge
The Edge class represents a connection from one node to another. An Edge object has three class variables:
private Node fromNode; // source node
private Node toNode; // destination node
private double weight; // weight6
The Edge class has the following method that you need to implement:
void calculateWeight()
The weight of an Edge should be calculated using this method upon creation of the Edge. The weight is calculated
as the Euclidean distance between the two nodes multiplied by the absolute difference between the two nodes’
elevations, plus a factor 0.01. This can be represented mathematically as follows:
w(e) = d(p1, p2) × ( 0.01 + |e1 – e2| )
Where e1 is the elevation of the from node, and e2 is the elevation of the to node. d is a function that calculates
the Euclidean distance between two 2D points, p1 and p2, that are positions of the two nodes.
3.4 EdgeTest
EdgeTest will assign marks as shown in Table 1.
Table 1: Edge Test mark allocation
Test
Marks
constructor
5
calculateWeight
5
Total:
10
4 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. As you go through these steps it will be useful the use the GUI
to visualise how your algorithms are working. Using the GUI for testing is further explained in section 5.
4.1 Graph
The graph structure that you must build in this assignment forms a 10×10 grid, with all edges between the
nodes being undirected. Due to the way in which our graph is built, node pairs have mirrored edges—node 1
has an edge to node 2, node 2 has an edge to node 1. The Graph class has no class variables. The graph
representation used in this assignment is neither adjacency matrix nor adjacency list, but rather a node having
a list of edges that connects to another node. Details are provided below.
4.1.1 void connectNodes(Node[] nodes)