Final Project
COMP 250 Fall 2022
posted: Tuesday, Dec. 6, 2022
Copyright By PowCoder代写 加微信 powcoder
due: Tuesday, Dec. 20, 2022 at 23:59
General instructions
• Submission instructions
– Please note that the submission deadline for the final project is very strict. No submissions will
be accepted after the deadline.
– As always you can submit your code multiple times but only the latest submission will be kept.
We encourage you to submit a first version a few days before the deadline (computer crashes
do happen and code post may be overloaded during rush hours).
• These are the files you should be submitting on Ed:
– Tile.java
– 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 files, especially .class files. Any deviation from these requirements may
lead to lost marks
• Starter code is provided for this project. Do not change any of the class names, file names, or method
headers. You can add helper methods or fields if you wish. 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 0.
https://giphy.com/clips/southpark-south-park-episode-3-season-17-a2RIF8lbuRtgGR6rVL
• 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.
• Whenever you submit your files to Ed, you will see the results of some exposed tests. These tests are
a mini version of the tests we will be using to grade your work. If your code fails those tests, it means
that there is a mistake somewhere. Even if your code passes those tests, it may still contain some
errors. We will test your code on a much more challenging set of examples. We highly encourage
you to test your code thoroughly before submitting your final version.
• By next week we will share with you a Minitester class that you can run to test if your methods
are correct. This class is equivalent to the exposed tests on Ed. Please note that these tests are only a
subset of what we will be running on your submissions. We encourage you modify and expand this
class. You are welcome to share your tester code with other students on Ed. Try to identify tricky
cases. Do not hand in your tester code.
• You will automatically get 0 if your code does not compile.
• Failure to comply with any of these rules will be penalized. If anything is unclear, it is up to you to
clarify it by asking either directly a TA during office hours, or on the discussion board on Ed.
Learning Objectives
This project is meant for you to practice working with graphs and solve some practical problems related
to it. You will realize from the starter code and the pdf instuctions, that for this project you have a
little more freedom in your implementation choices compared to previous assignments. You will start
by implementing both a DFS and a BFS traversa. Then you’ll spend sometime implementing two data
structures: one representing a weighted graph, and the other a priority queue. Finally, you will dive into
the implementation of Dijkstra’s algorithm for finding the shortest path on a given graph. You will learn
more about why this algorithm finds the optimal solution in COMP 251.
Project set up
For this project, you would be using a GUI that is programmed in JavaFX, so you need to set up JavaFX
in your IDE properly.
• 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 distribution, you need to
change it to Liberica distribution to support media.
1. open File → Project Structure → SDKs → Add → Download new SDKs → Select Liber-
ica and install it
2. In your run configuration, 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
find proper software. Use ”Add” button, then in ”name” section type ”e(fx)clipse (or any-
thing 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 filter ”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
https://download.eclipse.org/efxclipse/updates-nightly/site/
https://download.eclipse.org/efxclipse/updates-nightly/site/
Introduction
Figure 1: Referred from [1]
In a not-so-distant future, a zombie apocalypse has ravaged the planet and made resources scarce. A few
years post-apocalypse, mother nature has taken its course once more and covered the world in lush green-
ery. Cities turned to ruins and became a hub for zombies to hide during the day while at night they roam
and hunt for new flesh. Resource gathering time is limited and over the years, the use of technology has
dwindled to a select few who are capable. You are among the rare few who are still capable of program-
ming. Luckily, one of the elders has assigned you the task of creating an app, that will help our people
scavenge for resources while also avoiding the zombies. The responsibility now lies on your shoulders as
this app could help all of humanity scavenge and fight against the undead.
Luckily, you do not need to start from scratch, because you accidentally found an old map app in the
computer that can provide a simple graphic interface (GUI). However, the underlying main functionalities
have been corrupted so you need to finish the rest for it to work properly.
Path finding from your infected house to a safe house
Your main task for coding this app is to consider all the different elements of nature like desert, mountains,
etc, and to devise a plan to travel to the safe house.
On the way to the safe house, one might have to gather some supplies, travel through the metro and even
kill some of those pesky zombies. Being able to successfully compute the best route to take in order to
reach the safe house would make the risk of getting out there calculated and worth taking.
Now hurry up and get to coding before the zombies come knocking on your door!!
Luckily for you the GUI of the app is still functional and has the following sections:
• Menu: The menu provides ways to navigate through maps and also supports functionalities to
modify the GUI visual output.
– Control: basic command to manipulate the map.
– Maps: where to initialize maps.
– View: utility functions related to map display:
* Display system log: a toggle whether or not to show the system log.
* Display tile text: a toggle on whether or not to show text for each tile in the map.
* Display grid: a toggle whether or not to show grid border.
• Main map display: Different parts of the city are modeled as maps and are displayed here in a 2D
fashion. The layout of the map, the departure and destination points, and the suggested paths are
displayed here.
• Commanding panel: This is where different commands are issued based on users’ needs. Your
main task would be writing the code for each button and making sure they are executed correctly.
• Console panel: This is where important messages are displayed, including system messages and
user messages.
Figure 2: GUI
The map is 2D grid-based for easy demonstration. It consists of six different base regions, plains, deserts,
mountains, facilities, and zombie-infected ruins. It also labels the location of the departure and the desti-
nation. Mountains are generally hard to cross so they can be treated as a non-travelable obstacle. The rest
of the tiles can be traveled through with a certain cost in the distance, time, and damage. For example,
the desert region may have a straightforward path that is short in distance, but actually traveling through
on foot will take a while. Sometimes, you may want to cut through an abandoned building because it is
shorter and takes less time, but you might run into zombies and put yourself in danger. In this project, you
will try to model these as data and experiment with how this might affect your choice of pathfinding.
(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.
Simulating your travel
To ensure that the path devised by your logic is completely accurate, the app has a functionality called
“simulation”. This would simulate your path and help you visualize your course. To start a simulation,
after generating a path successfully, press the simulation button from the Control menu. Turn on the
volume for some nice sound effects.
Your Tasks
Level 0: Warming up [5pts]
In preparation to solve your pathfinding task, you first need to create all the necessary parts for visualizing
the outside world on a map. Since the putter world can be modeled using six regions, you first need 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.
• neighbours: 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
To 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 [10 pts]
Now that you have made sense of the GUI and you have modeled the world, you are ready to give your
first try at implementing an algorithm that would allow you to find a path to the safe house from a given
tile. Being a resourceful developer, you quickly open the book ”Introduction to Algorithms”[4], a holy
grail of Algorithm design, and remember reading something about Breadth First Search(BFS) and Depth
First Search(DFS). You decide to implement these two algorithms to see if they do the job.
Open the GraphTraversal class and implement the two following static methods:
• BFS(Tile start) : This method takes a Tile as input which represents the starting point of
the traversal. It will then traverse the map and find all the reachable tiles from the given input tile
using BFS. It returns an ArrayList containing the Tiles in the same order as they have been
• DFS(Tile start) : This method takes a Tile as input which represents the starting point of
the traversal. It will then traverse the map and find all the reachable tiles from the given input tile
using DFS. It return an ArrayList containing the Tiles in the same order as they have been
NOTE: Some tiles are not designed to be traveled through, thus you can use the method isWalkable()
from the Tile class to avoid these obstacle tiles in your traversals.
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.
Level 2 [15 pts]
Your initial intuition for using BFS and DFS was a good one. However, it has one major flaw: the path
obtained traverses through all the points around the world to get to the safe house. You quickly notice that
this might not be sustainable, as the complexity(O(n2)) increases.
Hence, you go back once again to your trusted textbook and this time you find a better algorithm for
the task at hand: Dijkstra’s algorithm. You remember learning from class, that this algorithm is used to
find the shortest path from point A to point B on a positively weighted graph. 1 In a couple of sections
you’ll finally get to implement it yourself!
To get there though, you first need to think about how to implement the two data structures the algo-
rithm needs. Let’s start by implementing a weighted graph. Open the class Graph. This class defines a
data type to represent a weighted graph. This is also a double directed graph, where the cost of travelling
between two tiles connected by an edge is determined by where we are headed. That is, the edges of the
graphs are directed, and their weight depends on the destination Tile:
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 so that you can use it to represent a map of the outer world on which
you’d like to eventually build paths with minimum weight. The details of the implementation are left up
to you. In order for us to assign points for this task, we require you to implement at least the following
methods (for which you cannot change the header). You are welcome to add as many fields and methods
(public or private) as you see fit (this includes also overloading any of the methods listed below if
this is what you’d like to do).
• Graph(ArrayList
taining all of its vertices.
• addEdge(Tile origin, Tile destination, double weight) : a method adds to
the graph 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 the graph.
• getNeighbors(Tile t): a method that takes a Tile as input and returns an ArrayList
containing all the Tiles adjacent to it.
• computePathCost(ArrayList
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).
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):
1For additional details on Dijkstra’s algorithm see here.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
• Three fields:
– 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 ob-
ject of type Edge.
• getStart() and getEnd(): two getters used to access the corresponding Tiles.
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 [15 pts]
The other data structure that you need to implement before tackling Dijkstra’s algorithm, is a priority
queue. You remember from class that the best way to implement a priority queue is to use a min heap. You
also remember that since heaps are complete binary tree, you had learned a wonderful trick that allowed
you to implement the entire data structure using an array! Open the TilePriorityQ class. This class
is meant to represent 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. Like for the Graph, you will have some freedom in
your decisions of how to implement the priority queue. In order to assign points for this task, we will
require the following methods to be implemented. You are welcome to add as many fields and methods
(public or private) as you see fit (this includes also overloading any of the methods listed below if
this is what you’d like to do).
• TilePriorityQ (ArrayList
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.
You are highly encouraged to test that your priority queue works as expected before starting to implement
the code from the next section.
Level 4 [25 pts]
Let’s now look into 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
• 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 me
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com