here is some code I wrote for an A* pathfinding algorithm. However as soon as I make the start and end nodes slightly far away, the program takes minutes to run. Why is this? The code below ran in 2 minutes yet the start and end node are so close. Thanks for the help. I feel like it has to do with the part of getting the lowest f value in the open list, however I am not sure.
import cProfile
class Node(object):
def __init__(self, parent = None, position = None):
self.position = position
self.parent = parent
self.g = 0
self.h = 0
self.f = 0
def euclidean_distance(self, x_end, y_end):
return math.sqrt(abs(self.position[0]-x_end)**2 + abs(self.position[1]-y_end)**2)
def pos(self):
return self.position
maze = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
def astar():
openlist = []
closed = []
current = Node(None,[0,0])
destination = [4,8]
openlist.append(current)
adjacent = [[1,0],[0,1],[-1,0],[0,-1]]
while len(openlist) > 0:
cur_index = 0
for index in range(len(openlist)):
if openlist[index].f < openlist[cur_index].f:
cur_index = index
current = openlist[cur_index]
openlist.pop(cur_index)
closed.append(current)
if current.pos() == destination:
print("ok")
path = []
current_node = current
while current_node is not None:
path.append(current_node.position)
current_node = current_node.parent
return path
for candidate in adjacent:
x = candidate[0]+current.pos()[0]
y = candidate[1]+current.pos()[1]
if x > (len(maze) - 1) or x < 0 or y > (len(maze[len(maze)-1])-1) or y < 0:
continue
if maze[x][y] != 0:
continue
next = Node(current,[x,y])
neighbour = next
if neighbour not in closed:
temp = current.g + 1
if neighbour in openlist:
if neighbour.g > temp:
neighbour.g = temp
else:
neighbour.g = temp
openlist.append(neighbour)
neighbour.h = math.sqrt(abs(neighbour.pos()[0]-destination[0])**2 + abs(neighbour.pos()[1]-destination[1])**2)
neighbour.f = neighbour.g + neighbour.h
# for val in openlist:
# if neighbour == val and neighbour.g > val.g:
# continue
# openlist.append(neighbour)
cProfile.run('astar()')
path = astar()
new = []
for r in range(len(maze)):
temp = []
for g in range(len(maze[r])):
if maze[r][g] == 1:
temp.append("#")
elif [r,g] in path:
temp.append("^")
else:
temp.append(".")
new.append(temp)
print(" ".join(temp))