Mastering A* Algorithm with Python: Navigate like a Pro in any Situation
Introduction
Are you tired of getting lost in the maze of roads and streets every time you try to reach your destination? Do you want to find the shortest path possible, but all the complicated algorithms and terms are giving you a headache? Well, don’t worry because the A* algorithm has got you covered!
About A* Algorithm
A* algorithm, also known as the “A-star” algorithm, is a pathfinding and graph traversal algorithm that is widely used in navigation systems, video games and other applications.
A* algorithm combines Dijkstra and Best-first search to find the most efficient path by considering the estimated and actual costs.
Now the question is what is Dijkstra and Best-first search?
Dijkstra’s algorithm is a method for finding the shortest path between nodes in a graph. It works by repeatedly visiting the node with the lowest distance from the start point until it reaches the endpoint.
Best-first search is an algorithm that prioritizes the most promising node to explore next based on a given heuristic function. It is used to find the shortest path in a graph or tree.
I know it’s too technical and I also blame the algorithm. Hehe! Never mind.
Some Real-world Stuff
Enough with the technical jargon, let’s take a look at a real-world example using Google Maps. Imagine you’re in New Delhi, India (The Capital of India) and you want to visit the India Gate. You could take a long way around, wandering aimlessly for hours (trust me, Delhi is not a small city (Area = 42.7 km2 (16.5 sq mi))), or you could let the A* algorithm be your guide.
By inputting your starting point and ending point, the A* algorithm calculates the quickest route for you, taking into consideration the traffic, one-way streets, and construction detours. It’s like having your own personal tour guide, minus the annoying small talk.
Is A* only limited to GPS (Google Maps)?
The A* algorithm isn’t just limited to Google Maps, it’s used in a variety of other applications as well. From autonomous cars to drones, the A* algorithm helps these machines navigate and make decisions in real-time. And with the advancement of technology, the future possibilities for the A* algorithm are endless. Imagine being able to navigate through a virtual reality world with ease or even sending a robot to Mars to find the best route for the rover.
Future Aspect
Get ready to be the ultimate neighbourhood navigator with a futuristic blueprint of your society or block. No more aimlessly wandering for delivery boys, they’ll reach their destination with ease. And for tourists, it’s like having a personal tour guide showing you the best places and routes to explore. Choose a long scenic route for a leisurely stroll or a short straight shot for a speedy trip. But let’s say, the unexpected happens and a fire breaks out in the building you’re working in. No need to panic, just remember to use the A* & D* application and it’ll guide you to the nearest escape route in real time like a pro!
So, next time you’re lost and feeling like you’re going in circles, remember the A* algorithm. It’s the ultimate guide to getting you where you need to be. And who knows, maybe one day it’ll even help you find that perfect ice cream shop. hehe!
Let’s Build Our Own A* Model
Too theoretical, right?
Don’t worry, I am here.
My name is Aryan, your friendly neighbourhood AI/ML enthusiast and Medium author. Whether you’re a seasoned coder or just starting out, this tutorial is guaranteed to make you learn something new.
Step — 1:
We have to call the necessary libraries:
import folium #To use the MAP Feature without using any API
import math #To make a few calculations about Time and Distance
from geopy.geocoders import Nominatim #To gather the coordinatesIf you get any error like no module found, then use pip install and write the module name. And make sure you are using the updated libraries. To update use the command pip install — —upgrade and write the library name.
Step — 2:
Call the Nominatim to get the latitude and longitude values of starting points and ending points.
Code:
geolocator = Nominatim(user_agent="geoapiExercises")Step — 3:
Define your starting and ending places.
Code:
Place_1 = (input("Enter Place One Name : "))
Place_2 = (input("Enter Place Two Name : "))Output:
I have taken random places.
Step — 4:
Using geocode to get the Latitude and Longitude values.
location_1 = geolocator.geocode(Place_1)
location_2 = geolocator.geocode(Place_2)
long_1 = ("Longitude: ", location_1.longitude)
Lat_1 = ("Latitude: ", location_1.latitude)
long_2 = ("Longitude: ", location_2.longitude)
Lat_2 = ("Latitude: ", location_2.latitude)
#Assigning new variable names
coord_1 = [location_1.latitude, location_1.longitude]
coord_2 = [location_2.latitude, location_2.longitude]Step — 5:
Putting some Time and Distance calculation formulas.
Code:
# set the starting point and ending point
start_point = coord_1
end_point = coord_2
# convert latitudes and longitudes to radians
start_lat, start_lon = math.radians(start_point[0]), math.radians(start_point[1])
end_lat, end_lon = math.radians(end_point[0]), math.radians(end_point[1])
# use the Haversine formula to calculate the distance
a = math.sin((end_lat - start_lat) / 2)**2 + math.cos(start_lat) * math.cos(end_lat) * math.sin((end_lon - start_lon) / 2)**2
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
distance = 6371 * c # 6371 is the radius of the Earth
# assuming an average speed of kmph you can calculate the time
time = distance / 3596.45Step — 6:
Now, the most awaited part. Locating the coordinates and finding the shortest path using A*.
But before proceeding, kindly note that due to limited resources, I found the shortest path using an aerial view.
If you want to use it exactly with roads, you can use a Grid view map. Here I have used the Folium library to directly make a map.
# create a map centered at the starting point
m = folium.Map(location=start_point, zoom_start=50)
# add markers for the starting and ending points
folium.Marker(start_point, popup=Place_1).add_to(m)
folium.Marker(end_point, popup=Place_2).add_to(m)
# draw a line between the two points
folium.PolyLine([start_point, end_point], color='red', weight=3.5, opacity=2).add_to(m)Code:
This will display the Time and the Distance.
print("Distance: {:.2f} km".format(distance))
print("Time: {:.2f} s".format(time))Output:
Here, I have taken the assumption that my speed would be 3,596.45 kmph. Don’t ask about the relevance, it is randomly selected. hehe! :P
Code:
This will Display the Map.
Reminder: Kindly note that due to limited resources, I found the shortest path using an aerial view.
mOutput:
And there you have it folks, the A* algorithm in a nutshell. Now go forth and conquer the world of navigation, one graph at a time! Just remember, when it comes to the A* algorithm, the sky’s the limit.
So, don’t be afraid to get creative and build your own tools to take your navigation skills to new heights. Who knows, you may even discover a new ice cream shop or two in the process. ^_^
Happy coding and happy exploring!
See you soon!
In case of questions, leave a Comment or Email me at aryanbajaj104@gmail.com
ABOUT THE AUTHOR
Passionate about studying how to improve performance and automate tasks. I’m seeking to leverage my data analytics, machine learning, and artificial intelligence skills to improve corporate performance through the optimum utilization of available resources. In other words, I want to use my superpowers to help make the world a better place. Hehe!
Website — acumenfinalysis.com
CONTACTS:
If you have any questions or suggestions on what my next article should be about, please write to me at aryanbajaj104@gmail.com.
If you want to keep updated with my latest articles and projects, follow me on Medium.
Join my Telegram Channel:
SUBSCRIBE TO MY MEDIUM ACCOUNT:
https://aryanbajaj13.medium.com/subscribe
