Data Structures: Assignment 3

Pathfinding

SP2, 2017

James Baumeister

May 2017

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 map—a 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

node’s 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

Dijkstra’s 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.

Figure 1: Importing the project through File → Import

1See Appendix A to learn how to control the GUI

2

1.1 Importing into eclipse

The assignment has been provided as an eclipse project. You just need to import

the project into an existing workspace. See Figure 1 for a visual guide. Make

sure that your Java JDK has been set, as well as the two jar files that you need

for junit to function. This can be found in Project → Properties → Java Build

Path → Libraries. The jar files have been provided within the project; there

is no need to download any other version and doing so may impact the testing

environment.

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;

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.2 EdgeTest

EdgeTest will assign marks as shown in Table 1.

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:

3

Table 1: EdgeTest mark allocation

Test Marks

constructor 5

calculateWeight 5

Total: 10

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

2.4 VectorTest

VectorTest will assign marks as shown in Table 2.

Table 2: VectorTest mark allocation

Test Marks

distance 5

Total: 5

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.

4

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

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 2. Once all of the edges have been correctly

created, the GUI will display as shown in Figure 3. 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 node’s 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 node’s edge list. Note that a node does not need

a list containing eight edges if it only requires three, but the order must be

maintained—for 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 node’s

list of Edge objects for one that connects the two nodes and return the source

node’s edge. If there is none found, the method should return null.

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.

5

Table 3: Edge list index–direction 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.4 Node[] breadthFirstSearch(Node start, Node target)

The breadthFirstSearch method takes as arguments two Node objects—a

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

length−1). 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 objects—a 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 length−1). This

method should not take into account edge weights.

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

The method should use Dijkstra’s algorithm to search the graph for the shortest

path from start to target while taking into account the cost of travel (i.e. edge

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

2Closely follow the textbook example. Subtle differences in algorithms could impact your

performance against the tests

6

Figure 2: The GUI before completing the connectNodes method

dijkstrasSearch should return the path as a Node array, ordered from start

(index 0) to target (index length−1).

3.1.7 Node[] aStarSearch(Node start, Node target

This method should use the A* algorithm, similar to Dijkstra’s algorithm, to

search the graph for the least costly path. Unlike Dijkstra’s, 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

length−1).

3.2 GraphTest

GraphTest will assign marks as shown in Table 4.

3This is a research task, but this website should be very helpful: http://www.

redblobgames.com/pathfinding/a-star/introduction.html

7

Figure 3: The GUI after completing the connectNodes method

A Using the GUI

A GUI has been provided to aid understanding how your graph searching algorithm implementations are functioning. The window contains a graphical

representation of the graph on the left, and three buttons on the right (see

Figure 3. The buttons labelled ‘Biomes’ and ‘Polygons’ are essentially toggles

for displaying an outline of the node squares (shown in Figure 4. ‘Biomes’ is

activated by default. The button labelled ‘Nodes’ controls whether or not the

red node circles and pink edge lines are shown—click to toggle between the two.

The blue player node will render at the nominated start node and its position

will update if a path is provided.

As the GUI operates independently to the testing suite, there are some

aspects that you must manually control in order to show the desired information.

The GraphRender class has the following constants:

private final int START_NODE = 0;

private final int TARGET_NODE = 9;

private final int ANIMATION_DELAY = 500;

private final String METHOD = "breadthFirstSearch";

You may modify these values. As an example, if you were testing your Dijkstra’s

algorithm implementation and wanted to match one of the unit tests, you could

change START_NODE to 8, TARGET_NODE to 0 and METHOD to "dijkstrasSearch".

ANIMATION_DELAY represents the delay for the blue player circle to jump along

8

Table 4: GraphTest mark allocation

Test Marks

connectNodes 10

getEdge 5

calculateCost 5

breadthFirstSearch 20

depthFirstSearch 15

dijkstrasSearch 20

aStarSearch 10

Total: 85

nodes in the path, in milliseconds; increase to slow the animation, decrease to

请加QQ：99515681 或邮箱：99515681@qq.com   WX：codehelp