代写COMP 250、代做java编程语言

日期：2024-12-09 08:54

Final Project

COMP 250 Fall 2024

posted: Wednesday, Dec. 4, 2024

due: Sunday Dec. 15, 2024, at 23:59 for a chance to receive Mastery, OR

Friday, Dec. 20, 2024 at 23:59

General Instructions

• Submission instructions

– Please note that the submission deadline for the ffnal project is very strict. No submissions

will be accepted after the deadline of Dec 20th. And no submissions received after Dec. 15

will receive Mastery.

– We encourage you to start early. As always you can submit your code multiple times (submissions

will be capped at 100) but only the latest submission will be kept. We encourage you to submit

a ffrst version a few days before the deadline (computer crashes do happen and code post

may be overloaded during rush hours).

– Your task is to complete and submit the following ffle:

* DesertTile.java

* FacilityTile.java

* MetroTile.java

* MountainTile.java

* PlainTile.java

* ZombieInfectedRuinTile.java

* Graph.java

* GraphTraversal.java

* TilePriorityQ.java

* PathFindingService.java

* ShortestPath.java

* FastestPath.java

* SafestShortestPath.java

Do not submit any other ffles, especially .class ffles. Any deviation from these requirements

may lead to lost marks.

– Do not change any of the starter code that is given to you. Add code only where instructed,

namely in the “ADD YOUR CODE HERE” block. You may add private helper methods to

the class you have to submit (and in fact you are highly encouraged to do so), but you are not

allowed to modify any other class.

1• The project shall be graded automatically. Requests to evaluate the project manually shall not be

entertained, so please make sure that you follow the instruction closely or your code may fail to pass

the automatic tests. Note also that for this project, you are NOT allowed to import any other class

(all import statements other than the one provided in the starter code will be removed). Any failure

to comply with these rules will give you an automatic Inconclusive.

• Whenever you submit your ffles to Ed, you will see the results of certain exposed tests along with

the competency level you have achieved. A small subset of these tests will also be shared with you

to help with debugging. We highly encourage you to write your own tests and thoroughly test your

code before submitting your ffnal version. Learning to test and debug your code is a fundamental

skill to develop.

You are welcome to share your tester code with other students on Ed and collaborate with others in

developing it.

• Your submission will receive an “Inconclusive” if the code does not compile.

• Failure to comply with any of these rules may result in penalties. If something is unclear, it is your

responsibility to seek clariffcation, either by asking during offfce hours or posting your question on

the Ed.

• IMPORTANT: Do NOT wait until you have ffnished writing the entire project to start testing your

code. Debugging will be extremely difffcult if you do so If you need help with debugging, feel free

to reach out to the teaching staff. When asking for help, be sure to mention the following:

– The bug you are trying to ffx.

– What steps have already taken to resolve it.

– where you have isolated the error.

Learning Objectives

This project provides an opportunity to practice working with graphs and tackle practical problems involving

graph traversal and pathffnding. Unlike previous assignments, this project offers greater ffexibility in

your implementation choices, allowing you to exercise creativity and decision making to solve complex

tasks.

Through this project, you will:

1. Implement both Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms to explore

and analyze graphs.

2. Construct two essential data structures, a weighted graph and a priority queue, using object-oriented

principles.

3. Develop a functional implementation of Dijkstra’s algorithm to ffnd the shortest path on a positively

weighted graph.

The skills gained in this project will prepare you for deeper explorations in graph algorithms and

optimization in COMP 251, while reinforcing core concepts of data structures and algorithms.

2Project set up

For this project, you can use a GUI (provided) that is programmed in JavaFX, so you need to set up JavaFX

in your IDE properly. Please note, that the use of the GUI is not necessary to successfully complete the

project.

• For Intellij user (recommended):

– Windows user: It should be already included in the SDK if you are using Java 1.8 or higher.

– Mac user: By default you laptop might be using Amazom Correto distribution, you need to

change it to Liberica distribution to support media.

1. open File → Project Structure → SDKs → Add → Download new SDKs → Select Liberica

and install it

2. In your run conffguration, select Liberica as your build SDK and build the project

• For Eclipse user:

– Windows user: You need to install JavaFX library manually

1. In Help menu, in Install new software wizzard you should add the new site location to

ffnd proper software. Use ”Add” button, then in ”name” section type ”e(fx)clipse (or anything

you want, it does not matter). In ”location” section type: https://download.

eclipse.org/efxclipse/updates-nightly/site/

2. Search downloadable package by applying a fflter ”e(fx)clipse” you should see a list of

options (such as JavaFX SDK)

3. Install them all, after that Eclipse will restart

4. In Eclipse select the project, run Project → Preferences → Java Build Path → Add Library

→ Select JavaFX SDK, then rebuild the project, all errors should go away

– Mac user: switch to Intellij

3Introduction

Figure 1: Referred from [1]

In a not-so-distant future, a zombie apocalypse has ravaged the planet, leaving resources scarce. A few

years post-apocalypse, mother nature has reclaimed much of the world, covering it in lush greenery. Cities

have turned to ruins, serving as hubs for zombies to hide during the day while they roam and hunt for new

ffesh at night. Resource-gathering time is limited, and over the years, the use of technology has dwindled

to a select few who are still capable.

You are among these rare survivors - one of the few still capable of programming. Luckily, one of

the elders has entrusted you with a critical mission: to create an app that will help humanity scavenge

resources while avoiding the zombie threat. The responsibility now lies on your shoulders, as this app

could be a turning point for humanity in its ffght for survival.

Thankfully, you do not need to start from scratch. While exploring an old computer, you stumbled upon

a map app that provides a simple graphical interface (GUI). However, the core functionalities of the app

have been corrupted, and it is now up to you to restore and complete them to ensure its full functionality.

Pathffnding from Your Infected House to a Safe House

Your main task in coding this app is to account for all the different elements of nature, such as deserts,

mountains, and more, to devise a plan to safely travel to the safe house.

4On your journey, you may need to gather supplies, navigate through metro stations, and even face off

against pesky zombies. Successfully computing the best route to the safe house will ensure that the risk of

venturing out is calculated and worthwhile.

Now hurry up and get to coding before the zombies come knocking on your door!

GUI

Luckily for you, the GUI of the app is still functional and consists of the following sections:

• Menu: The menu provides options to navigate through maps and supports functionalities to modify

the GUI visual output:

– Control: Basic commands to manipulate the map.

– Maps: Options to initialize maps.

– View: Utility functions related to map display:

* Display system log: A toggle to show or hide the system log.

* Display tile text: A toggle to show or hide text for each tile in the map.

* Display grid: A toggle to show or hide grid borders.

• Main map display: Displays different parts of the city in a 2D grid-based format. This section

shows the layout of the map, the departure and destination points, and any suggested paths.

• Commanding panel: This section allows users to issue commands based on their needs. Your main

task is to write the code for each button and ensure their correct functionality.

• Console panel: Displays important messages, including system and user-generated messages.

Figure 2: GUI

5Map

The map is designed as a 2D grid for easy visualization and demonstration. It consists of six different base

regions: plains, deserts, mountains, facilities, metro tiles, and zombie-infected ruins. It also identifies the

locations of the departure and destination tiles.

Mountains are generally hard to cross and are treated as non-travelable obstacles. The other tiles can be

traversed, but each type incurs specific costs in terms of distance, time, and damage. For example:

• The desert region may offer a straightforward path that is short in distance but slow to travel on foot.

• Cutting through an abandoned building may provide a shorter and quicker route but poses a high

risk of encountering zombies.

In this project, you will model these regions as data and experiment with how the associated costs influence

your choice of pathfinding strategies.

(a) Plains (b) Building (c) Zombie (d) Mountains (e) Metro

(f) Desert

Figure 3: Different elements represented in the map[2, 3]

Printing to console

To use the function that shows a message on the GUI, try calling the logMessage() function from the

Logger class. You can use Logger to log messages with the following code:

Logger.getInstance().logMessage(msg:String)

The logger can be accessed anywhere.

6Simulating Your Travel

To ensure that the path devised by your logic is completely accurate, the app includes a functionality called

simulation. This feature allows you to simulate your path and visualize your journey.

To start a simulation, after successfully generating a path, press the simulation button from the Control

menu. Don’t forget to turn on the volume for some immersive sound effects!

Your Tasks

Level 0: Warming up

As the sun rises on the first day of your mission, you begin setting up the foundation for humanity’s survival.

The first step is mapping the world around you—a lush yet dangerous landscape with varied terrains.

Understanding the lay of the land is essential to plan safe travel routes and avoid perilous obstacles.

The outer world can be modeled using six regions, and your first task is to make sure that the data

related to those regions is correctly initializes. The GUI is provided the template for each region as Tile

and each specific tile would be a subclass of the Tile class.

The Tile class has several fields that can be accessed directly from all of the other classes:

• isDestination: A boolean variable indicating whether or not this tile is the destination.

• isStart: A boolean variable indicating whether or not this is the tile where our path begins.

• xCoord and yCoord: This tile’s x, y coordinates in the map, starting from top left. The row is x

and the column is y.

• nodeID: A unique index number for each tile object. The only assumption you can make about

this number is that it is unique. You can also modify it, if you like, as long as you keep it unique.

• adjacentTiles: An array list of all the tiles connected to this tile on the map.

• distanceCost, timeCost, and damageCost: The cost of travelling to this tile in terms of

distance, time, and physical damage respectively.

• predecessor, and costEstimate: two fields which you might find useful when implementing

Dijkstra’s algorithm.

Find all the subclasses representing each region inside the tiles folder, and complete their constructors

using the information from the table below:

name/cost distance time damage(risk)

plain 3 1 0

desert 2 6 3

mountain 100 100 100

facility 1 2 0

metro 1 1 2

zombie infected ruins 1 3 5

7To test that the costs have been initialized correctly, start GUI and open map 1. Each time you click on

an individual tile, the detailed information about that tile should be printed on the console. Fig 3 gives a

pictorial representation of different elements of nature which can be found in the GUI.

Level 1: Basic Pathfinding

With the map prepared, you set out to explore the area using basic strategies. Guided by your knowledge of

Depth-First and Breadth-First Search, you begin scouting paths to the safe house. Though these methods

are rudimentary, they lay the groundwork for your ultimate goal: devising an efficient route.

Open the GraphTraversal class and implement the following static methods:

• BFS(Tile start): This method takes a Tile as input, representing the starting point of the

traversal. It will traverse the map and find all reachable tiles from the given input tile using BFS. The

method should return an ArrayList containing the Tiles in the same order they were visited.

• DFS(Tile start): This method takes a Tile as input, representing the starting point of the

traversal. It will traverse the map and find all reachable tiles from the given input tile using DFS. The

method should return an ArrayList containing the Tiles in the same order they were visited.

NOTE: Some tiles are not designed to be traversable. Use the method isWalkable() from the Tile

class to filter out these obstacle tiles during your traversals.

Testing

To test the correctness of your implementation, open GUI and go to Map 1. Try clicking on BFS traversal

or DFS traversal. You should see a red dotted path that follows the order of visits and visit all reachable

tiles on the map. Fig 4 highlights the expected output for Map 1. Please note that depending on your

implementation of DFS, you might see a different path and that’s ok.

(a) BFS Traversal (b) DFS Traversal

Figure 4: A snapshot of Map 1 for BFS and DFS Traversal

When you work with larger maps, it might be hard to understand the order in which the tiles are reached

just by looking at the path drawn. Try opening [Control]→[Start Simulation] after executing the algorithm,

it may help you visualize the path better.

8Level 2: Building Weighted Graphs

The world is more complex than it seems. The straightforward traversal methods aren’t enough to navigate

this dangerous terrain efficiently. You turn to a better representation—a weighted graph—to capture the

intricacies of the terrain and prioritize paths with minimal risks.

Hence, you return to your trusted notes, and this time you discover a better algorithm for the task: Dijkstra’s

algorithm. You recall from class that this algorithm is used to find the shortest path from point A to

point B on a positively weighted graph. In a couple of sections, you’ll implement this algorithm yourself!

To prepare, you first need to consider how to implement the two data structures required by the algorithm.

Let’s begin by implementing a weighted graph. Open the class Graph. This class defines a data type to

represent a weighted graph. It is a directed graph where the cost of traveling between two tiles connected

by an edge is determined by the destination Tile. Specifically:

weight(Edge(t1, t2)) = cost(t2)

weight(Edge(t2, t1)) = cost(t1)

Depending on the graph you need to build, you will refer to the appropriate cost stored in the Tile object.

Your task is to implement this class to represent a map of the outer world, on which you will eventually

build paths with minimal weight. While the specific implementation details are left up to you, we require

you to implement at least the following methods (note that their headers must remain unchanged). You

are welcome to add as many fields and methods (public or private) as you see fit. You may also

overload the methods listed below if desired.

• Graph(ArrayList<Tile> vertices): A constructor that builds the graph given a list containing

all of its vertices. This graph should NOT contain any edges. The constructor should be

used to initialize the vertices of the graph and any fields you decide to include in this class.

• addEdge(Tile origin, Tile destination, double weight): A method that adds

an Edge with the given weight, connecting origin to destination.

• getAllEdges(): A method that takes no inputs and returns an ArrayList containing all the

Edges from this graph.

• getNeighbors(Tile t): A method that takes a Tile as input and returns an ArrayList

containing all the Tiles connected to it in this graph.

• computePathCost(ArrayList<Tile> path): This method takes as input a list of Tiles

representing a path. It computes and returns a double indicating the total weight of the path (i.e.,

the sum of weights for all edges along the path). You can assume that the input represents a valid

path in this graph.

Please note that inside the Graph class you can find a static nested class called Edge. This class

is meant to represent a directed edge connecting two Tiles in the graph. This class must contain the

following methods/fields (as with Graph you are welcome to add anything that you might find useful for

your own implementation):

• Three fields:

9– origin : a Tile indicating where the edge is originating from.

– destination : a Tile indicating where the edge is directed to.

– weight: a double indicating the weight associated to this edge.

• Edge(Tile s, Tile d, int cost): A constructor that uses the inputs to initialize an object

of type Edge.

• getStart() and getEnd(): two getters used to access the corresponding Tiles.

Testing

To be able to test your code for this section using the GUI, you will first need to implement Dijkstra’s

algorithm. You are encouraged to test your code on your own before moving forward.

Level 3: Priority Queue Construction

To navigate the ever-changing dangers of the world, prioritizing your moves is essential. By leveraging

your knowledge of heaps, you will construct a priority queue to dynamically evaluate and select the safest

and most efficient paths. This tool will be critical as you progress to more advanced strategies. Since

heaps are complete binary trees, you can take advantage of a clever trick you learned to implement the

entire data structure efficiently using an array.

Open the TilePriorityQ class. This class represents a priority queue where the elements are Tiles,

and they are compared based on the cost estimated to reach each tile from a source tile. Similar to the

Graph class, you have some flexibility in deciding how to implement the priority queue.

To earn full points for this task, you must implement the following methods. You are welcome to add any

additional fields and methods (public or private) that you find necessary. Overloading any of the

methods listed below is also permitted if it aligns with your design choices.

• TilePriorityQ (ArrayList<Tile> vertices): a constructor that builds a priority queue

with the Tiles received as input.

• removeMin() a method that takes no inputs and removed the Tile with highest priority (i.e.

minimun estimate cost) from the queue.

• updateKeys(Tile t, Tile newPred, double newEstimate): a method that takes

as input a Tile t. If such tile belongs to the queue, the method updates which Tile is predicted

to be the predecessor of t in the minimum weight path that leads from a source tile to t as well as

the estimated cost for this path. Note that this information should be stored in the appropriate fields

from the Tile class, and after these updates, the queue should remained a valid min heap.

Testing

You are highly encouraged to test that your priority queue works as expected before starting to implement

the code from the next section.

10Level 4: Dijkstra’s Algorithm

Now equipped with the tools to dynamically assess paths, you are ready to implement Dijkstra’s algorithm—a

powerful technique for computing the shortest route to safety. Every decision you make brings

humanity one step closer to survival.

Open the PathFindingService class. This class contains the following public methods:

• A constructor that takes a Tile as input, representing the starting point of the paths we’d like to

compute.

• An abstract void method called generateGraph(). This method, which you’ll need to

override in the PathFindingService’s subclasses, is supposed to build a graph connecting all

reachable tiles (i.e. ignoring the obstacle tiles) from the source tile. It should then use this graph

to initialize the corresponding Graph field. This will be the graph on which our algorithm will

compute the path with a minimum weight.

In addition to the latter, there are the following three methods which will be discussed throughout the

next few sections. As with the previous two classes, you are welcome to add any additional method you

see fit.

• findPath(Tile startNode)

• findPath(Tile start, Tile end)

• findPath(Tile start, LinkedList<Tile> waypoints)

You are finally ready to implement Dijkstra’s algorithm. You have been provided with a class named

ShortestPath that extends the

Complete the following tasks to get the shortest distance path

• Step 1: In ShortestPath, implement generateGraph(). The method creates a weighted

graph using the distance cost as weight. This graph should be then stored in the appropriate field.

To make sure that the graph is generated each time a ShortestPath object is created, you should

add a call to this method inside the constructor.

Note: You can use BFS or DFS to help you get a list of all reachable tiles. Remember also that the

graph you want to build should only connect tiles that are designed to be travelled through. You can

use the method isWalkable() to help you figure out which tiles are not just obstacles.

• Step 2: Implement Dijkstra’s algorithm in PathFindingService (Fig 5). Use the algorithm to

implement the findPath(Tile startNode) method. The method uses Dijkstra’s algorithm

on the Graph stored in the field g to find a minimum weight path to the destination from the

input Tile. Note that the result of running Dijkstra’s algorithm is that each node in the graph will

contain the information needed to find the minimum weight path from the source to this node. So,

after running the algorithm you will need to use the information stored in the predecessor field

to backtrack and find the list of Tiles that make up the path to be traversed from the start node to

the destination.

11DIJKSTRA(V, E,w,s):

INIT-SINGLE-SOURCE(V,s)

S ← Q ← V

while Q do

u ← REMOVE-MIN(Q)

S ← S {u}

for each vertex v Adj[u] do

RELAX(u,v,w)

Figure 5: Pseudo-code for Dijkstra’s algorithm

INIT-SINGLE-SOURCE(V,s)

for each v V do

d[v]←

[v]← null

d[s]← 0

Figure 6: Pseudo-code for the initialization

RELAX(u,v,w)

if d[v] > d[u]+w(u,v) then

d[v] ← d[u]+w(u,v)

[v] ← u

Figure 7: Pseudo-code for the relaxing operation

The reason why we are implementing the path-finding algorithm in the PathFindingService

class is that when later creating the second strategy for the time cost you would be using the same Dijkstra’s

algorithm so it is much cleaner to write the code in the parent class. However, you need to write

your own graph generation method in the subclass because it is essentially the difference between these

path-finding strategies.

Testing

To test this code, you can open either Map 1 or Map 2 and click on the button “Shortest Path”. A track

will be highlighted in red that will show you the shortest way to reach the safe house. You can click on the

Simulate button to simulate your path. Fig 8 highlights the expected output for both the maps (please note

that the shortest path is not unique. There might be more than one path with the same minimum weight!

Your code does not have to generate the same path as in the figure as long as its weight is minimal).

12(a) Map 1 (b) Map 2

Figure 8: Shortest path for both maps

Level 5: Waypoints

The journey is not just about reaching safety—survival also depends on gathering critical supplies along

the way. By integrating waypoints into your algorithm, you can account for these essential stops while

still optimizing the overall route.

The app includes a functionality called ”Add Waypoints”, allowing you to manually place waypoints using

the GUI. To place waypoints, click on the ”Add Waypoints” button and select supply locations on the map.

To accommodate these changes, you will need to modify the code by implementing the remaining two

findPath methods in the PathFindingService class. Follow these steps to complete the implementation:

•

Step 1: Implement the findPath method that takes the start and end Tiles as its input. This method

is very similar to the one implemented in Level 4. The only change would be to generate the path to

the specific destination tile received as input. For this purpose, notice that Dijkstra’s algorithm will

never visit each node in the graph (reachable from the source) exactly once. This means that once

a node has been visited by the algorithm, one is already able to figure out what is the shortest path

from the source to this node.

• Step 2: Implement the last and final findPath method, which takes a starting node and a list of

waypoints as input. This method builds the shortest paths from the source to the destination, making

sure to visit the each of the waypoints in the order in which they have been provided as input. Use

the other methods that you have already implemented to help you find such path. Please note that:

the destination tile will not be provided within the list of waypoints. You can figure out which one

is the destination tile by accessing the field isDestination from the Tile class.

13Testing

For testing this code, you can open Map 1 or Map 2. You can click on ”Add Waypoint” and add waypoints

anywhere on the map. Then, you can click on ”Shortest Path” to get a path traversing through your supply

pointa and going to the final destination. Fig 12 gives a graphical example of sample output. In the figure,

we have added two waypoints(W1, W2) and the path traverses through both of them.

(a) Shortest path with waypoints for Map 2 (b) Fastest path with waypoints for Map 2

Level 6: Fastest Path

Sometimes speed is more important than caution, especially at night when zombies are most active. You

adapt your tools to prioritize time efficiency, ensuring a swift escape in the darkest hours.

To find the fastest path, you are provided with a class called FastestPath that extends

PathFindingService. Thankfully, you have already implemented your algorithms to find a minimum

weight path inside PathFindingService, so all you need to do is generate a graph with the

appropriate weights, since in this case you want the algorithm to run on a graph that is weighted by the

time cost. Override generateGraph() in the class FastestPath (similarly to how you did before)

to achieve this.

Testing

To test the code, you can open Map 1, and Map 2 and click on the button ”Fastest Path”. The path should

be highlighted using a red line. You can simulate the path by going into [Control] →[Start Simulation], to

get a sense of the simulation. You can get a sense of the path by looking at the figure below.

14Figure 10: Expected output for the fastest path on Map 2

Level 7: Metro Integration

The ruins of the metro system offer a glimmer of hope for faster travel. By incorporating metro tiles into

your pathfinding algorithm, you leverage these remnants of technology to enhance your routes and outpace

the undead.

To integrate the subway in your logic, you would need to make a few modifications in your code. The

following are the steps to add the subway logic in your code

• You have been supplied with a class named MetroTile. You have already initialized a constructor

that declares all the variables. Your first task is to implement another method called fixMetro

that assigns different distance and time costs to metro tiles. This method takes a Tile as input.

If such tile is another metro tile, then the time and distance costs (i.e. metroTimeCost and

metroDistanceCost) to travel between these two tiles should be computed based on how far

the two tiles are. The following are the formulae for calculating the time and distance cost going

from one metro station to another:

metroT imeCost = M(t1, t2) ∗ metroCommuteF actor

metroDistanceCost = M(t1, t2)/metroCommuteF actor

where the metroCommuteFactor variable is set to 0.2 for now. M(t1, t2) is the Manhattan

distance between t1 and t2, use Tile class’s xCoord and yCoord to access their 2-D coordinate and

use the formula below:

M(t1, t2) = abs(t1.xCoord − t2.xCoord) + abs(t1.yCoord − t2.yCoord)

15Note that when adding more than 2 metro stations things are getting more complicated because each

pair of metro tiles would have their own cost based on the distance, so to simplify this you can

assume there are only two metro stations in the district (poor public transportation).

• Modify your code, so that the graph generated by generateGraph() in both FastestPath

and ShortestPath class now considers metro weights. That is, whenever you try to add an edge

to the graph, if both the start and the end tile for a edge are MetroTile, then you need to set the

edge’s weight/cost using the corresponding value computed in the previous step. Please note that

which part of the code you will need to modify really depends on your implementation.

Testing

To test this code, you can go to Map 3 and click on the ”Fastest Path” Button. A sample output has been

attached below.

Figure 11: Expected output after integrating metro in Fastest Path

Level 8: Safest Shortest Path

By now, you have implemented Dijkstra’s algorithm and developed two strategies: one for the shortest

distance and another for the fastest time. Despite these efforts, navigating zombie-infested areas remains

a deadly challenge, especially in high-risk districts like those in Map 4. These paths fail to guarantee the

safety of our people.

To address this issue, our post-apocalypse pathfinding service must incorporate a new feature that balances

safety with efficiency. To simulate and evaluate potential risks, agents now have a fixed health (HP) that

decreases when traveling through dangerous areas. If an agent’s HP drops below 0, the path must be

deemed invalid.

Your task is to develop a solution that finds the shortest path while ensuring the agent’s survival.

16This type of problem is called constrained shortest path (CSP) and you will need to implement an

algorithm that is known for solving this problem called LARAC (Lagrangian Relaxation Based Aggregated

Cost) algorithm. In simple words, the algorithm introduces aggregated cost to replace graph

cost (weight) and optimize it through iterations until it finds the optimal cost (weight) that satisfies the

constraint. To know more about the mathematical theory behind it, check out some resources here.

When you first began this project, you have set up various types of costs for each type of tile (region),

including damageCost, which hasn’t been used yet. The field damageCost represents how much

damage our agent takes when walking on this tile.

For this section, you need to complete the SafestShortestPath class which holds the logic for

computing the safest shortest path for our agent. This class has the following fields:

• A integer field health, model and visualize our agent’s life status.

• A Graph called costGraph that uses the distance cost as the edges’ weights.

• A Graph called damageGraph that uses the damage cost as the edges’ weights.

• A Graph called aggregatedGraph that uses the aggregated cost as the edges’ weights.

To complete the class, you need to implement the following methods:

• generateGraph() : like for the other two class, you need to override this method so that it

initializes the three graphs listed above. For costGraph initialize all edges’ weight using the

distance cost. For the riskGraph and aggreatedGraph, initialize them with the damage cost.

To keep it simple, in this class we will not consider time cost.

• findPath : Override the findPath(startNode, waypoints) method from the parent

class. This method implement the LARAC algorithm that finds the optimal path with our limited

HP. Note that the total cost of a path is equal to the sum of the weights of the edges that belong to

the path. Now, the algorithm consists of the following steps:

1. Set the Graph field from the superclass to be equal to costGraph, and find the optimal path

pc with the least distance cost. If the total damage cost for pc is less than our health H, return

pc for we have found the optimal path.

2. Set the Graph field from the superclass to be equal to damageGraph, find the optimal path

pd with the least damage cost. If the total damage cost for pd is bigger than our health H, return

null for no possible path exists.

3. Compute the multiplier λ using the equation:

λ =

c(pc) − c(pd)

d(pd) − d(pc)

where c(p) is the total distance cost for a path p and d(p) is the total damage cost for a path

p. Then update each aggregatedGraph’s edge weight to the latest aggregated cost cλ =

c + λ ∗ d., where c is the distance cost of the edge, and d is the damage cost of the edge.

174. Set the Graph field from the superclass to be equal to aggregatedGraph and compute the

optimal path pr with the least aggregate cost.

– If the total aggregated cost for pr is the same as the total aggregated cost for pc (our

current shortest path without considering any damage factor), then return pd (our current

safest path).

– else if the total damage cost for pr is less than or equal to our HP then assign pr to pd.

– else assign pr to pc.

5. Repeat Step 3 until a path is returned.

Testing

To test it, start GUI and select Map 4, find a safe path by pressing Safety first! button. When you simulate

the path, the traveling agent will flash in red if it takes damage and will die if HP is not enough (which is

very likely to happen if you naively use the shortest/safest path in Map 4). Feel free to adjust the HP limit

using the text field on the screen and see how the resulting path would change based on how much health

the agent has.

Figure 12: Expected output after implementing LARAC algorithm

18REFERENCES REFERENCES