Project 05: Path Finding

Overview

The fifth project is to implement the path finding component of a web application using Dijkstra's Algorithm in C++.

This project is to be done in groups of 1 - 3 and is due midnight Wednesday, November 30, 2016.

Web Application

The web application is shown in the screenshot below:

On the left is a text field for defining the tiles in the two-dimensional map used by the application. Each letter in the map corresponds to one of the following six tiles:

Tile	Description	Symbol	Cost
	Forest	f	3
	Grass	g	1
	High Grass	G	2
	Hill	h	4
	Mountain	m	7
	River	r	5

The cost of each tile defines how much it costs to leave the tile. For instance, the "runner" in the image above is starting on a hill tile (as specified by the h in the text field. Leaving this tile to move to any of its neighbors would cost 4 as specified in the table above.

Beneath the text field is a Generate Random button that when clicked will generate a random map with the specified rows and columns.

In the middle of the application is a graphical visualization of the map and of the runner. Clicking on the a tile will cause the application to compute the shortest path from the runner's location to the target tile. Once the path is determined, the runner will move tile by tile to the destination, highlighting its path along the way.

Moreover, the path cost and exact tiles will be shown on the right side of the application.

Architecture

As noted previously, this application is a multi-lingual project that uses JavaScript for the front-end interface, Python for the back-end web service, and C++ for the core path finding as shown below:

Users interact with the application through the web interface (ie. index.html), which is powered by JavaScript, which processes inputs (ie. clicking on buttons or tiles) and sends requests to the Python web server. The Python back-end (ie. gwen.py), services any file requests and acts as the intermediary between the JavaScript front-end and the C++ implementation of Dijkstra's Algorithm.

When a user clicks on a tile, the JavaScript front-end will send the tile information, the map layout, the runner's position, and the target tile position to the Python web service, which in turn forwards this information to the C++ path finding application. After performing Dijkstra's Algorithm on the given input, the C++ program returns the total path cost along with the sequence of map tiles back to the Python web server, which then passes these results back to the JavaScript front-end.

For this project, you only need to focus on the C++ path finding component; the front-end JavaScript and back-end Python is provided to you.

Reference

You can find a reference implementation of the web application at http://xavier.h4x0r.space:9001.

A reference implementation of the C++ path finding component, dijkstras can be found on AFS:

/afs/nd.edu/user15/pbui/pub/bin/dijkstras

GitLab

To start this project, you must form a group of 1 - 3 people. One group member should fork the Project 05 repository on GitLab:

https://gitlab.com/nd-cse-30331-fa16/project05

Once this repository has been forked, follow the instructions from Reading 00 to:

1. Make the repository private

2. Configure access to the repository

   Make sure you add all the members of the team in addition to the instructional staff.

As with the programming challenges in this course, the project repository contains a Makefile for automated building and testing of your program.

In addition to these files, the repository should also contain the following:

1. data/*.txt: These are the input and output files that are used to test your dijkstras path finding component.

2. src/dijkstras.cpp: This contains the implementation of Dijkstra's Algorithm in C++.

3. src/gwen.py: This is the Python web service code.

4. src/measure.cpp: This is the measure utility required for testing.

5. www/*.png: These are the images that correspond to the tiles described above.

6. www/index.html: This is the file that contains the JavaScript front-end.

Further descriptions of these files and what you need to implement is described below.

Dijkstras

For this project, you will need to implement Dijkstra's Algorithm in the src/dijkstras.cpp file. Unlike previous projects, very little scaffolding is provided to you as the scope of the project is much smaller than normal.

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 in the following format:

TILES_N
TILE_NAME_0 TILE_COST_0
...
TILE_NAME_N-1   TILE_COST_N-1

MAP_ROWS MAP_COLUMNS
TILE_0_0    ...
...

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:

6
f 3
g 1
G 2
h 4
m 7
r 5
10 10
G r g g m m m r f m
G g r G G G G m f h
m r f m m f G r h h
G m G f h r g m g g
g g g m h m h f m f
h r g f f f g h r h
m G f r m m G r g f
m r h h h h G m m r
r r g f G r r m f r
G g r g g r h m m r
0 0
7 6

Once this information is read in and parsed, the dijkstras application should perform Dijkstra's 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 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:

27
0 0
0 1
0 2
0 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 discussed in class, there may be multiple valid shortest paths if different paths have the same total weight. Because of this, if the tests fail, let the instructors know and they will verify if it is a false negative or not.

Questions

When you are finished implementing your dijkstras application answer the following questions in the project05/README.md:

1. Verify that the web application works by running:

   ./src/gwen.py
   

   By default the web application uses port 9001. You can modify this by passing the -p flag:

   ./src/gwen.py -p 9999
   

   Once the application is running, open your web browser and type in the appropriate URL. You should now be able to generate random maps and click on tiles to move the runner.

   Backend Configuration

   To have the web application talk to your backend, you will need edit the following line in the www/index.html file:

   xhr.open('post', 'http://xavier.h4x0r.space:9001', true);
   

   Change http://xavier.h4x0r.space:9001 to the machine and port you are using. For instance, if you are testing on your local machine and port 9999, you can do:

   xhr.open('post', 'http://localhost:9999', true);
   

   To get around a "Cross Site" permissions issue in some browsers, you can use http://lvh.me/ instead of localhost:

   xhr.open('post', 'http://lvh.me:9999', true);
   

   Finally, if you are using a student machine, you can do something like:

   xhr.open('post', 'http://student00.cse.nd.edu:9999', true);
   

2. 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 table as demonstrated below:

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

3. After you have performed your benchmarks:

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

   • What is complexity of your implementation of Dijkstra's Algorithm?

     Explain this by describing which data structures you used and how you used them to implement path finding.

   • 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?

In addition to the questions, please provide a brief summary of each individual group members contributions to the project.

Rubric

Your project will be scored based on the following metrics:

To test your programs, simply run make test. Your programs must correctly behave correctly and have no memory errors.

Submission

To submit your project, simply push your changes to your Project 05 repository. There is no need to create a Merge Request. Make sure you have enable access to your repository to all of the instructional staff.