Background
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.
Issue
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.
Troubleshooting
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
- Euclidean distance is not negative
- Adjacent nodes are not out of bounds
- Other smaller troubleshoot
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)
