In this assignment, we will be using the characteristics of streets and elevation changes to try to find optimal routes for walking through Dubrovnik. The basic underlying structure will use A* to find the "shortest" path, but it will be up to you to decide how to define shortest, and to make sure your heuristics work with the defintion that you make.
The underlying data will come from two data sets. The first is from OpenStreetMap. I have downloaded the data for the Dubrovnik area, which you can get here. This contains all information to build the map of the area, including many things which are not streets, such as the coastline, cliffs, parking lots, etc. It will be up to you to parse this XML so that your search uses only the relevant pieces. You will probably find it useful to read up on how OpenStreetMap is defined here as well as to use some code to sift through the XML to see what types of features are present here. Note that all nodes should have a latitude and longitude associated with them.
The second data set is elevation data. This file contains a high-density grid of elevation data. Specifically, it contains a 2-byte integer representing height in meters for each cell of a 3601x3601 cell grid. The grid covers the area between 42N and 43N latitude and 18E and 19E longitude, and the data is row by row from north to south. Thus, you should fairly easily be able to determine the (approximate) elevation of any particular node in the OSM database.
You are not required to develop a graphical solution to this problem, however it will probably assist in your debugging process. To assist you in this, here is some code that reads in each of the two data sets and creates a GUI window with some lines and circles.
Your final solution should be able to take (in some form) two OSM nodes and return the shortest path between them along with the expected time to walk along the path. You must use the elevation change and distance between nodes as part of your calculations, but beyond that you may choose your path costs in any way you believe is reasonable. Note that when calculating distances, one degree of latitude is larger than one degree of longitude - the given code has some useful information in this regard.
You will submit your code and a writeup. The writeup will contain discussion and defense of your cost calcuation and associated heuristic function. You should include results from some sample runs and your observations on how well these match your personal experience.
Grades will be assigned as follows:
Your solution must additionally allow for planning for cars and bicycles as well as pedestrians. You should assume that bicycles can travel on any pedestrian road as long as it does not have steps. You must of course have heuristic functions that are correct for each type of planning, and must defend your distinct path cost calculations and heuristics for each type of planning.
Grades will be calculated as follows: