Find and draw shortest path on Google Maps Custom Overlay with Dijkstra's algorithm
Short post about its development: https://yzahk.in/android-google-maps-custom-path-finder/
I needed to make a custom path finder map application. It was faster to use Google Maps API so I have the awesome rotate, zoom and most importantly GPS features without me inventing the wheel again. But this presented some problems: most importantly I had to map the overlay image pixel values to Google maps coordinates, to draw points and lines (nodes and edges) precisely. This was a really fun way to learn C# and Android Development.
In a later version I managed to hook up the GPS part too. I am not releasing that here, but as the real coordinates of the building is rotated and smaller than the overlay custom map image I had to make my own GPS marker that is transformed to be at the right place. Something for you to think about if you want to use this. Its simple math.
A fast way to set up the Google Maps part of it is to create a new Google Maps Activity. It will set up your project to be compatible with Maps API.
Before you run your application, you need a Google Maps API key. You have to put the API key in the google_maps_api.xml file. Read the comment there for more information. Without it you will not see the image overlay on the map.
After you have API key from Google and you put it in the google_maps_api.xml file you have a working Android Maps application. This contains a custom map I drawn in paint, with 26 nodes and 28 edges. Select a starting and ending node, experiment with the avoidable path function to see how the path changes so you get an idea about the workings of Dijkstra's algorithm.
If you put in your own image you should use image that has width and height both sized to powers of two (it doesn't have to be a square: 1024x512 is good too, but most devices prefer this rule. Some will show any image). Put it in the drawable folder and modify the MapsActivity.java file accordingly.
In the MapsActivity.java file you should change the
private static final int overlayImageWidth = 1024;
private static final int overlayImageHeight = 1024;
lines to represent your image's size and the
bitmap = BitmapFactory.decodeResource(context.getResources(),R.drawable.maps_f1);
line if you use another file name.
In the nodes.csv file you have to list all of the points that you might visit on the map.
Example line:
1,173,160,First Node,1,1
Explanation:
Node ID,position X on the image, position Y on the image, Node Name, Level, Importance
- Node ID: An Unique identifier for the node.
- position X and Y: you have to write the X and Y pixel value on the image. I use paint for this as it shows this value on the bottom left corner. It is a good idea to use the same x values for nodes that are next to each other and same y values for the ones above each other.
- Node Name: do not use "," in it without escaping it
- Level: if you want a multiple level map (for example you do a interior map for a building with floors) you can specify which level this node is on the code is ready to avoid nodes that are not on the selectedLevel (you can try this by changing this value to other than one on some nodes)
- Importance: this is a value for a future feature, also maybe for using the A* algorithm that might be faster. Not used at this time.
In the edges.csv file you have to make connections between all the nodes. Loose nodes crashes the algorithm if you target them. Same is true for loose node networks. You need to connect everything in one network OR make start and endpoint selection so you can only select nodes in given networks (or rework the code so this is not a problem).
Example line:
1,1,2,100,First Edge
Explanation:
Edge ID,From Node ID,To Node ID,Length,Edge Name
- Edge ID: An Unique identifier for the edge.
- From Node ID and To Node ID: specify the nodes that are the two ends of this edge
- Length: this specifies the length of the edge. You should be mindful about this so the algorithm give you really the shortest path
- Edge Name: do not use "," in it without escaping it
The menu_edges.csv, menu_from_nodes.csv and the menu_to_nodes.csv are list for the MainActivity spinners. As there is no point in making selectable all the nodes (lot of them are just there to make the path easier to navigate) you can list important nodes here. Same with edges. For example maybe you want the user to start from 3-4 different nodes (building has 3 entrances for example) but you want them to find 15 different places you list the respective nodes that way (Node IDs and names intact, order doesn't matter)
Set up working avoid edges functionality: After you built your node-edge system (you have a graph) you should come up with a longest possible distance for the whole. For example you have 3 nodes, with two edges (basically imagine a line with 3 points) and those two edges have a length of 10 and 20, then your longest possible distance is 30. In the Edge.java file's
private final static int maxEdgeLength = 11111;
line you have to specify a number higher than the longest possible path. This is needed for the "avoid edges" functionality. If the avoided edge is smaller than the longest possible path the algorithm will still take that edge in some cases. We can't delete edges so we have to give them such a length that it doesn't worth putting in the path.
P.S. I know I left an API key in the google xml file. I left it there as an example, it was turned off before I uploaded this.