Calculate optimal path between 2 locations on Map using A-Star path finding algorithm.
This repo contains the code for the implementation of the A-Star Best-first-search algorithm. This algorithm calculates the optimal route present between 2 locations (BITS Hyderabad and RGIA Airport in this example) and shows them on map using google maps API.
The algorithm is made independant from the map code so that others can find it easily if required. This Code uses a running Postgres database instance which has a map of Hyderabad (fetched from here) from which all roads are fetched.
This repo provides 2 files to calculate the distance matrix. The first file calcDist.py
uses
the data from the osm database to get road distances. There is also another file getDist.py
which uses the Bing Maps server to calculate the distances between nodes(API key required).
To run this project, we need a postgres database with postgis installed. There are many articles on google which can be used to setup postgres with gis support.
Load the file present in datasets/hyderabad_india.osm.pbf
with osm2pgsql tool to postgis database
Create a file in src
folder with name APIKeys.json
to store all your API keys (for bing and google maps).
These can be freely created. Bing Maps in optional, but Google Maps is required to draw path on map. In case
if you do not want to create any keys, the path is still stored in csv file src/FinalPath.csv
with the
optimal path which can be used for other purposes.
{
"BingMapsKey": "Your-Bing-Maps-Key-Here",
"GoogleMapsKey": "Your-Google-Maps-Key-Here"
}
This is an list of dependencies present/used in the project. If not present, use conda/pip to install the necessary.
- json
- heapq
- pickle
- gmplot
- pandas
- pickle
- numpy
- psycopg2
- tqdm
- Clone the repo
git clone https://github.com/RikilG/Optimal-Map-Routing.git
cd Optimal-Map-Routing/src
- Start your postgres server if it is not running
- Generate the Distancce Matrix
python calcDist.py
- Run A-Star algorithm and display result
python AStar.py
Repo folder structure
Repo Root
├── datasets
│ └── hyderabad_india.osm.pbf
├── images
│ └── route.png
├── src
│ ├── other
│ │ ├── roads_sql_queries.txt
│ │ └── wardNames.txt
│ ├── APIkeys.json
│ ├── AStar.py
│ ├── calcDist.py
│ ├── getDist.py
│ └── point.py
├── LICENSE
└── README.md
Distributed under the MIT License. See LICENSE
for more information.
Project Link: https://github.com/RikilG/Optimal-Map-Routing