CS302-Project 4 Solved

Overview
The fourth project is to implement a path finding component of a game, either online (web application) or on your
computer. You are allowed to work with a single partner (group of 2) but this will not required.
Big picture
Consider the following text and graphical representation of a 2D landscape:
Text Tiles Map
hfmrhghfmr
mg hmhhGgGm
mrgfmG rmrG
ff rGGghmf r
g rh rhGmfGh
mGGG r rg rfG
mg rmgGmhgf
G rf rmhmmmm
rmfGGgfgGh
hhh rmffmhm

f(3)
g(1)
G(2)
h(4)
m(7)
r(5)

I III milk 11
s t"greMlk

II

Each tile has a symbol (e.g., a forest has "f", river has "r") and can be assigned a specific cost, i.e., forest has a cost of 3 and river has a
cost of 5. Your mission, which you must choose to accept, is to help the runner (orange guy above) go from cell (x,y) to cell (i, j) with the
lowest overall cost.

https://web.eecs.utk.edu/-semrich/ds20/assignments/proj04.html 2/6
10/18/2020Project 04: Path Finding
Dijkstras
For this project, you will need to implement Dijkstra's Algorithm (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) in the src/dijkstras.cpp file.
The dijkstras path finding component will be given the specification of the tile information, the map layout, the runner's location, and the target location
via standard input (https://en.wikipedia.org/wiki/Standard_streams#Standard_input_.28stdin.29) in the following format:
TILES_N
TILE_NAME_O TILE_COST_O
 • •
TILE_NAME_N -1 TI LE_COST_N -1
MAP_ROWS MAP_COLUMNS
TILE_EL0. . .
 • •
RUNNER_START_ROW RUNNER_START_COL
RUNNER_END_ROW RUNNER_END_COL
The first TILES_N indicates the number of different tiles. This is followed by the specified number tiles, where each line has the tile name and then its
corresponding cost.
Next, the number of rows and columns in the map is given in MAP_ROWS and MAP_COLUMNS . This is followed by all the tile symbols where each row is
separated by a newline and each column is separated by a space.
Finally, you are given the runner's starting and ending map coordinates.
Here is an example of this input:

https://web.eecs.utk.edu/—semrich/ds20/assignments/proj04.html3/6
10/18/2020Project 04: Path Finding
6
f 3
g 1
G 2
h 4
m 7
 5
10 10
G rggmmmrfm
G grGGGGmf
h
mrfmmfGrhh
G
mGfhrgmgg
gggmhmhfmf
hrgfffghrh
mGf rmmGrgf
mrhhhhGmmr
 rgfGrrmf r
G grggrhmmr
m 0
7 6
Once this information is read in and parsed, the dijkstras application should perform Dijkstra's Algorithm
(https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) to determine the shortest path from the runner's starting location to the target ending
position. The result of this computation should be printed to standard output
(https://en.wikipedia.org/wiki/Standard_streams#Standard_output_.28stdout.29) in the following format:
Cost
ROW_0 COL _0
• • •
That is, the first item to be printed is the total path cost, followed by the tiles to travel starting from the runner's starting position to the target
destination. Here is the output your program should emit given the example input above:

https://web.eecs.utk.edu/-semrich/ds20/assignments/proj04.html 4/6
10/18/2020Project 04: Path Finding
27
0 0
m 1
m 2
m 3
1 3
1 4
1 5
1 6
2 6
3 6
4 6
5 6
6 6
7 6
To test your program, you can use make test , which will run dijkstras against 4 different maps.
Note, as we will discuss in class, and similar to SuperBall -- there may be multiple valid shortest paths if different paths have the same total
weight. Because of this, if the tests fail, let us know and we will verify if it is a false negative or not.
Calculating Path Cost
To calculate the total cost of the path and to determine the tiles to travel, you will need to reconstruct the path backwards as discussed in
class. In computing the total cost, remember to only include the cost of leaving a tile. This means, we should include the cost of leaving the
starting tile but not out of the destination (because we never leave it).

Additional questions
When you are finished implementing your dijkstras implementation answer the following questions in your README . md :
1. Write a program, generate_map , that given N generates a NxN map of random tiles. Use this program to generate random maps with
the following values of N :
10, 20, 50, 100, 200, 500, 1000
Benchmark your dijkstras path finding component on each of these map sizes and record the elapsed time and memory usage in a Markdown
(https://github.comiadam-p/markdown-here/wiki/Markdown-Cheatsheet) table as demonstrated below:

https://web.eecs.utk.edu/—semrich/ds20/assignments/proj04.html5/6
10/18/2020Project 04: Path Finding

N Elapsed Time Memory Usage
10

• •

20


• •


•
•

50 
•
• 
•
•

100 
•
• 
•
•

200 
•
• 
•
•

500 
•
• 
•
•

1000 
•
• 
•
•

Note: You should run multiple trials (e.g 5 ) and average the results.
Note: You should choose the top-left and bottom-right corners as the starting and ending points respectively.
In addition to the table above, each member must provide a brief summary of their individual contributions to the project and each member must
independently answer the following questions based on the shared table above:
1. How did you represent the map as a graph?
Explain which graph representation you used and how you determined the relationship between vertices include the edges and their weights.
2. What is complexity of your implementation of Dijkstra's Algorithm
(https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)? Explain this by describing which data structures you used and how
you used them to implement path finding.
3. How well does your implementation scale?
Explain what effect did N (ie. the size of the map) have on the performance of your dijkstras path finding component in terms of execution time
and memory usage?