I found the implementation of this algorithm in python online and it works. It searches the best path for reaching a point starting from another one. Here is the code:
from pyamaze import maze,agent,textLabel
from queue import PriorityQueue
def h(cell1,cell2):
x1,y1=cell1
x2,y2=cell2
return abs(x1-x2) + abs(y1-y2)
def aStar(m):
start=(m.rows,m.cols)
g_score={cell:float('inf') for cell in m.grid}
g_score[start]=0
f_score={cell:float('inf') for cell in m.grid}
f_score[start]=h(start,(1,1))
open=PriorityQueue()
open.put((h(start,(1,1)),h(start,(1,1)),start))
aPath={}
while not open.empty():
currCell=open.get()[2]
if currCell==(1,1):
break
for d in 'ESNW':
if m.maze_map[currCell][d]==True:
if d=='E':
childCell=(currCell[0],currCell[1]+1)
if d=='W':
childCell=(currCell[0],currCell[1]-1)
if d=='N':
childCell=(currCell[0]-1,currCell[1])
if d=='S':
childCell=(currCell[0]+1,currCell[1])
temp_g_score=g_score[currCell]+1
temp_f_score=temp_g_score+h(childCell,(1,1))
if temp_f_score < f_score[childCell]:
g_score[childCell]= temp_g_score
f_score[childCell]= temp_f_score
open.put((temp_f_score,h(childCell,(1,1)),childCell))
aPath[childCell]=currCell
fwdPath={}
cell=(1,1)
while cell!=start:
fwdPath[aPath[cell]]=cell
cell=aPath[cell]
return fwdPath
if __name__=='__main__':
m=maze(5,5)
m.CreateMaze()
path=aStar(m)
a=agent(m,footprints=True)
m.tracePath({a:path})
l=textLabel(m,'A Star Path Length',len(path)+1)
m.run()
My question about this code is why he only uses one queue? The priority queue is the OPEN queue, but why he doesn't use the CLOSED queue too? Since in many pseudocodes I find both and it is usually used in a condition , for example like in this pseudocode
OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
current = remove lowest rank item from OPEN
add current to CLOSED
for neighbors of current:
cost = g(current) + movementcost(current, neighbor)
if neighbor in OPEN and cost less than g(neighbor):
remove neighbor from OPEN, because new path is better
if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
remove neighbor from CLOSED
if neighbor not in OPEN and neighbor not in CLOSED:
set g(neighbor) to cost
add neighbor to OPEN
set priority queue rank to g(neighbor) + h(neighbor)
set neighbor's parent to current
First of all, CLOSED
is not a queue, but a set: either a node is in it, or it is not (there is not priority or other order).
This set is practically replaced by the use of infinity in the first script. By initialising with infinity, you indicate the corresponding nodes were not visited yet. The same "unvisited" concept is found in the second script by testing membership in OPEN or CLOSED. The difference is that the second script "unvisits" a node when the currently calculated path-cost is less than the one already known, while the first script makes this check directly -- counting on the fact that all costs are less than infinity.
So in the end it comes down to the same thing.