I want to implement an A-Star Algorithm with a GUI for user input to set the start and end node, and draw obstacles. However, I have spent a great deal of time pondering why the Algorithm isn't working.
The path goes in the opposite direction of the end node and to the corner of the matrix. For example, if start: 2,2 and end: 8,8 the path will map to the origin: 0,0 and vice versa.
I have already checked all the areas that I could possibly think is going wrong and even referring to source code from a medium article: A-Star Algorithm by Nicholas Swift
The obstacles on the graph have not yet been implemented because I was trying to get the path to map correctly before adding additional complexity to the motivating problem.
I simply cannot see where I am going wrong. I come from a Java background so there could be some basic Python syntax that is escaping me and making everything break. Any suggestions will be appreciated.
Source code:
class Node:
def __init__(self,x,y,nodeType):
self.xPos = int(x)
self.yPos = int(y)
self.nodeType = str(nodeType)
self.h = 0
self.g = 0
self.f = 0
def __eq__(self,node):
if((self.xPos == node.xPos) and (self.yPos == node.yPos)):
return True
else:
return False
def __str__(self):
return "(" + str(self.xPos) + "," + str(self.yPos) + "," + self.nodeType + ")"
class Graph:
def __init__(self,size,startX,startY,endX,endY):
self.graph = [[Node(x,y,"open") for y in range(size)] for x in range(size)]
self.graph[startX][startY].nodeType = "start"
self.graph[endX][endY].nodeType = "end"
self.startNode = self.graph[startX][startY]
self.endNode = self.graph[endX][endY]
def displayGraph(self):
for x in range(len(self.graph)):
for y in range(len(self.graph[x])):
print(self.graph[x][y],end=" ")
print("")
def getAdj(self,node):
adjNodes = []
x = int(node.xPos)
y = int(node.yPos)
if(self.inRange(x,y+1)):
adjNodes.append(self.graph[x][y+1])
if(self.inRange(x+1,y+1)):
adjNodes.append(self.graph[x+1][y+1])
if(self.inRange(x+1,y)):
adjNodes.append(self.graph[x+1][y])
if(self.inRange(x+1,y-1)):
adjNodes.append(self.graph[x+1][y-1])
if(self.inRange(x,y-1)):
adjNodes.append(self.graph[x][y-1])
if(self.inRange(x-1,y-1)):
adjNodes.append(self.graph[x-1][y-1])
if(self.inRange(x-1,y)):
adjNodes.append(self.graph[x-1][y])
if(self.inRange(x-1,y+1)):
adjNodes.append(self.graph[x-1][y+1])
for node in adjNodes:
print(node,end=" ")
print("")
return adjNodes
def inRange(self,x,y):
if(x > -1 and x < len(self.graph) and y > - 1 and y < len(self.graph[0])):
return True
else:
return False
def findShortestPath(self):
openList = []
closedList = []
openList.append(self.startNode)
count = 0
while(len(openList) > 0):
minNode = openList[0]
minIndex = 0
for i in range(len(openList)):
if(minNode.f < openList[i].f):
minNode = openList[i]
minIndex = i
openList.pop(minIndex)
closedList.append(minNode)
if(minNode == self.endNode):
"""
Taken from article
path = []
current = minNode
while current is not None:
path.append(current.position)
current = current.parent
return path[::-1] # Return reversed path
"""
return closedList
adjNodes = self.getAdj(minNode)
for node in adjNodes:
for closedNode in closedList:
if(node == closedNode):
continue
node.g = minNode.g + 1
node.h = ((node.xPos - self.endNode.xPos)**2) + ((node.yPos - self.endNode.yPos)**2)
node.f = node.h + node.g
for openNode in openList:
if((node == openNode) and (node.g > openNode.g)):
continue
openList.append(node)
class Driver:
size = int(input("Enter the size of the graph: "))
startX = int(input("Enter the x value of the start node: "))
startY = int(input("Enter the y value of the start node: "))
endX = int(input("Enter the x value of the end node: "))
endY = int(input("Enter the y value of the end node: "))
graph = Graph(size,startX,startY,endX,endY)
graph.displayGraph()
graph.findShortestPath()
Output when looped stopped at 20 iterations
Enter the size of the graph: 10
Enter the x value of the start node: 2
Enter the y value of the start node: 2
Enter the x value of the end node: 9
Enter the y value of the end node: 9
(0,0,open) (0,1,open) (0,2,open) (0,3,open) (0,4,open) (0,5,open) (0,6,open) (0,7,open) (0,8,open) (0,9,open)
(1,0,open) (1,1,open) (1,2,open) (1,3,open) (1,4,open) (1,5,open) (1,6,open) (1,7,open) (1,8,open) (1,9,open)
(2,0,open) (2,1,open) (2,2,start) (2,3,open) (2,4,open) (2,5,open) (2,6,open) (2,7,open) (2,8,open) (2,9,open)
(3,0,open) (3,1,open) (3,2,open) (3,3,open) (3,4,open) (3,5,open) (3,6,open) (3,7,open) (3,8,open) (3,9,open)
(4,0,open) (4,1,open) (4,2,open) (4,3,open) (4,4,open) (4,5,open) (4,6,open) (4,7,open) (4,8,open) (4,9,open)
(5,0,open) (5,1,open) (5,2,open) (5,3,open) (5,4,open) (5,5,open) (5,6,open) (5,7,open) (5,8,open) (5,9,open)
(6,0,open) (6,1,open) (6,2,open) (6,3,open) (6,4,open) (6,5,open) (6,6,open) (6,7,open) (6,8,open) (6,9,open)
(7,0,open) (7,1,open) (7,2,open) (7,3,open) (7,4,open) (7,5,open) (7,6,open) (7,7,open) (7,8,open) (7,9,open)
(8,0,open) (8,1,open) (8,2,open) (8,3,open) (8,4,open) (8,5,open) (8,6,open) (8,7,open) (8,8,open) (8,9,open)
(9,0,open) (9,1,open) (9,2,open) (9,3,open) (9,4,open) (9,5,open) (9,6,open) (9,7,open) (9,8,open) (9,9,end)
(2,3,open)
(3,3,open)
(3,2,open)
(3,1,open)
(2,1,open)
(1,1,open)
(1,2,open)
(1,3,open)
(1,2,open)
(2,2,start)
(2,1,open)
(2,0,open)
(1,0,open)
(0,0,open)
(0,1,open)
(0,2,open)
(0,1,open)
(1,1,open)
(1,0,open)
(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)
(0,1,open)
(1,1,open)
(1,0,open)
(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)
(0,1,open)
(1,1,open)
(1,0,open)
(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)
(0,1,open)
(1,1,open)
(1,0,open)
(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)
(0,1,open)
(1,1,open)
(1,0,open)
(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)
(0,1,open)
(1,1,open)
(1,0,open)
(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)
(0,1,open)
(1,1,open)
(1,0,open)
(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)
(0,1,open)
(1,1,open)
(1,0,open)
(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)
(0,1,open)
(1,1,open)
(1,0,open)
(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)
As pointed out by user @Ghoti the issue was a simple comparison error in the algorithm. With the current comparison statement in the code above the first node in the adjNode list is always selected.
if(minNode.f < openList[i].f):
minNode = openList[i]
minIndex = i
Instead, it is as simple as flipping the inequality to compare the other way. A simple elementary algebra mistake. The correct comparison would be: minNode.f > openList[i].f