Hey Everyone, if you are facing any difficulties to implement A* algorithm in python, then you came at right place. A-Star Algorithm Python Tutorial will help you to understand A* algorithm easily and in a better way. So let’s gets started.
Contents
A-Star Algorithm Python Tutorial – Basic Introduction Of A* Algorithm
What Is A* Algorithm ?
- A* is the most popular choice for pathfinding, because it’s fairly flexible and can be used in a wide range of contexts.
- It is an Artificial Intelligence algorithm used to find shortest possible path from start to end states.
- It could be applied to character path finding, puzzle solving and much more. It really has countless number of application.
- Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968.
- The A* algorithm uses both the actual distance from the start and the estimated distance to the goal.
How It Works ?
Now let’s see how A* algorithm works. It based on following concepts –
- START GOAL States – Where the program begins and where it aims to get.
- How you measure progress towards goal.
- How you generate Children or all possible Paths towards solution.
At each iteration of its main loop, A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes
-
123f(n)=g(n)+h(n)
where,n = next node on the path
g(n) = the cost of the path from the start node to n
h(n) = a heuristic function that estimates the cost of the cheapest path from n to the goal
A* Algorithm
Now you will see algorithm of A* algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 |
# A* Algorithm 1. GENERATE A LIST of all possible next steps towards goal from current position 2. STORE CHILDREN in priority queue based on distance to goal, closest first 3. SELECT CLOSEST child and REPEAT until goal reached or no more children |
A-Star Algorithm Python Tutorial – Implementing A* Algorithm In Python
So guys, now you will see how can you implement A* algorithm in python. So lets get’s started without any delay.
We will do it step-wise for understanding easily, because the program is very lengthy and may be you get stuck in between.
Creating Base Class
First of all import PriorityQueue from queue. then you have to define a class named as State or whatever you want. This class is basically the base class.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# PriorityQueue is a data structure. It organize items based on priority iset. from queue import PriorityQueue #This is the base class that is to be used to store all the important steps that are #used for A* algorithm class State(object): def __init__(self, value, parent, start = 0, goal = 0): self.children = [] #Children is a list of all membering possibilities self.parent = parent #store current parent self.value = value #store current value self.dist = 0 #store current distance, dist is not actually gonna be set #here, it is just a placeholder. It actually meant to be set to sub state #or subclasses of State class #Now Check the parent is plucked in #if the parent is plucked in do following if parent: self.start = parent.start # store start state self.goal = parent.goal # store goal state self.path = parent.path[:] # copy the parent path to your path. [:] is actually # allows to make a copy of that list(self.path) into our own list. # if [:] will be not here then self.path will have same value as parent.path # That's why [:] is important. self.path.append(value) #Store all values into our path. This path is basically #building own self and keeping track to where we at. #check for if there is no parent else: self.path = [value] # set a path with list of objects started with our current value self.start = start # store start state self.goal = goal # store goal state # create two empty functions that would be later defined in sub class. def GetDistance(self): pass def CreateChildren(self): pass |
Creating Sub Class
Now we will create a subclass that will contain two methods GetDistance() and CreateChildren( ) method. So write the following code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
class State_String(State): def __init__(self, value, parent, start = 0, goal = 0 ): super(State_String, self).__init__(value, parent, start, goal) # create constructor self.dist = self.GetDistance() # override distance variable by calling GetDistance() method def GetDistance(self): # first check to see if we have reached to our goal, and if we have then simply return 0 if self.value == self.goal: return 0 dist = 0 #Define a loop to go through each letter of the goal for i in range(len(self.goal)): letter = self.goal[i] # get the current letter dist += abs(i - self.value.index(letter)) #find index of letter in current value #This will give the distance of letter is from its target p return dist # simply return distance #Define function to generate our children def CreateChildren(self): #if there are no children then go ahead and generate the children # this is just an extra precaution that we don't want to children twice if not self.children: for i in range(len(self.goal)-1): # go through every possibilities or every possible arrangement of the letter. val = self.value # switching the second letter and the first letter of every pairs of letters # and we track on the beginning and track on the end and then we have a new arrangement of letter in val. val = val[:i] + val[i+1] + val[i] + val[i+2:] # create a child and store the value of the child and pass self to store the parent of the child child = State_String(val, self) self.children.append(child) # finally add this child to our children list |
Creating A_Star_Solver Sub Class
Now we will create a class where the real magic would be happened. So lets write the following code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class A_Star_Solver: def __init__(self, start, goal): self.path = [] # store final solution from start state to goal state self.vistedQueue =[] #it keeps track all the children that are visited self.priorityQueue = PriorityQueue() self.start = start # store start state self.goal = goal # store goal state def Solve(self): startState = State_String(self.start,0,self.start,self.goal) # it doesn't have any parent state. count = 0 # priorityQueue.put() is used to add children, you have to pass a tuple inside it. # The tuple contain 0, count and startState. 0 is priority number that we want self.priorityQueue.put((0,count, startState)) # this while loop contain all the magic that is to be happenend while(not self.path and self.priorityQueue.qsize()): closesetChild = self.priorityQueue.get()[2] # getting topmost value from the priority queue closesetChild.CreateChildren() self.vistedQueue.append(closesetChild.value) # it keep track all the children that we are visited for child in closesetChild.children: if child.value not in self.vistedQueue: count += 1 if not child.dist: self.path = child.path break self.priorityQueue.put((child.dist,count,child)) if not self.path: print("Goal Of is not possible !" + self.goal ) return self.path |
Creating Main Function
Now we will create a final code that actually calls everything that exists. So write the following code.
|
1 2 3 4 5 6 7 8 9 10 |
if __name__ == "__main__": start1 = "hema" goal1 = "mahe" print("Starting....") a = A_Star_Solver(start1,goal1) #Initializing object a.Solve() # call Solve() method for i in range(len(a.path)): #printing the result print("{0}){1}".format(i,a.path[i])) |
A* Algorithm Python Complete Program
So guys, let’s place entire code together.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
from queue import PriorityQueue #Creating Base Class class State(object): def __init__(self, value, parent, start = 0, goal = 0): self.children = [] self.parent = parent self.value = value self.dist = 0 if parent: self.start = parent.start self.goal = parent.goal self.path = parent.path[:] self.path.append(value) else: self.path = [value] self.start = start self.goal = goal def GetDistance(self): pass def CreateChildren(self): pass # Creating subclass class State_String(State): def __init__(self, value, parent, start = 0, goal = 0 ): super(State_String, self).__init__(value, parent, start, goal) self.dist = self.GetDistance() def GetDistance(self): if self.value == self.goal: return 0 dist = 0 for i in range(len(self.goal)): letter = self.goal[i] dist += abs(i - self.value.index(letter)) return dist def CreateChildren(self): if not self.children: for i in range(len(self.goal)-1): val = self.value val = val[:i] + val[i+1] + val[i] + val[i+2:] child = State_String(val, self) self.children.append(child) # Creating a class that hold the final magic class A_Star_Solver: def __init__(self, start, goal): self.path = [] self.vistedQueue =[] self.priorityQueue = PriorityQueue() self.start = start self.goal = goal def Solve(self): startState = State_String(self.start,0,self.start,self.goal) count = 0 self.priorityQueue.put((0,count, startState)) while(not self.path and self.priorityQueue.qsize()): closesetChild = self.priorityQueue.get()[2] closesetChild.CreateChildren() self.vistedQueue.append(closesetChild.value) for child in closesetChild.children: if child.value not in self.vistedQueue: count += 1 if not child.dist: self.path = child.path break self.priorityQueue.put((child.dist,count,child)) if not self.path: print("Goal Of is not possible !" + self.goal ) return self.path # Calling all the existing stuffs if __name__ == "__main__": start1 = "hema" goal1 = "mahe" print("Starting....") a = A_Star_Solver(start1,goal1) a.Solve() for i in range(len(a.path)): print("{0}){1}".format(i,a.path[i])) |
Checking Output
So we have written our code successfully and now its time to run the code check the output. So without any delay, let’s check.
Related Articles :
- Python Zip File Example – Working With Zip Files In Python
- Convert Python To exe Tutorial
- Data Backup Methods That Can Work for Your Business
- Linear Search Python – Learn Linear Search With Example