I'm still new to Python and this my first ever question on stackoverflow and I've been having trouble for a week to implement an A* algorithm.
The code I've got finds a goal with a straight wall but as you will see, as soon as I extend the wall below the start point and it has to go backwards or around it, it starts looping forever.
I've been banging my head against the wall trying to fix it and how to implement a raise code so it stops looping. Any help will be very much appreciated.
My code:
class Node:
"""A node class for A* Pathfinding"""
def __init__(self, parent=None, position=None):
self.parent = parent
self.position = position
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.position == other.position
def astar(maze, start, end):
"""Returns a list of tuples as a path from the given start to the given end in the given maze"""
# Create start and end node
start_node = Node(None, start)
start_node.g = start_node.h = start_node.f = 0
end_node = Node(None, end)
end_node.g = end_node.h = end_node.f = 0
# Initialize both open and closed list
open_list = []
closed_list = []
# Add the start node
open_list.append(start_node)
# Loop until you find the end
while len(open_list) > 0:
# Get the current node
current_node = open_list[0]
current_index = 0
for index, item in enumerate(open_list):
if item.f < current_node.f:
current_node = item
current_index = index
# Pop current off open list, add to closed list
open_list.pop(current_index)
closed_list.append(current_node)
# Found the goal
if current_node == end_node:
path = []
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
return path[::-1] # Return reversed path
# Generate children
children = []
for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
# Make sure within range
if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (
len(maze[len(maze) - 1]) - 1) or node_position[1] < 0:
continue
# Make sure walkable terrain
if maze[node_position[0]][node_position[1]] != 0:
print("node -", node_position[0],node_position[1], "is blocked")
continue
# Create new node
new_node = Node(current_node, node_position)
# Append
children.append(new_node)
# Loop through children
for child in children:
# Child is on the closed list
for closed_child in closed_list:
if child == closed_child:
continue
# Create the f, g, and h values
child.g = current_node.g + 1
child.h = ((child.position[0] - end_node.position[0]) ** 2) + (
(child.position[1] - end_node.position[1]) ** 2)
child.f = child.g + child.h
# Child is already in the open list
for open_node in open_list:
if child == open_node and child.g > open_node.g:
continue
# Add the child to the open list
open_list.append(child)
def main():
maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 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, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 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]]
start = (0, 0)
end = (1, 8)
path = astar(maze, start, end)
print(path)
main()
You have these two pieces:
# Child is on the closed list
for closed_child in closed_list:
if child == closed_child:
continue
# Child is already in the open list
for open_node in open_list:
if child == open_node and child.g > open_node.g:
continue
The continue will continue the inner for loop. Consequently, it does not have any effect. You are rather looking for something like this:
# Child is on the closed list
is_in_closed = False
for closed_child in closed_list:
if child == closed_child:
is_in_closed = True
break
if is_in_closed:
continue
# Child is already in the open list
is_in_open = False
for open_node in open_list:
if child == open_node and child.g > open_node.g:
is_in_open = True
break
if is_in_open:
continue
Two more comments:
Your distance measure only counts the number of steps. Therefore, a diagonal is as expensive as a horizontal / vertical step. You might want to change this and get the actual length or an approximation of it to find the truly shortest path.
Your heuristic is the squared distance to the target. This is not an admissible heuristic because it over-estimates the actual cost to the target. As a result, you might not find the correct shortest path. For your cost function (number of steps), a better and admissible heuristic would be max(child.position[0] - end_node.position[0], child.position[1] - end_node.position[1]) (you need at least this number of steps to get to the target).