I have an A* search algorithm which crashes the program because of a memory error, and I don't know why. These are the relevant bits of code:
def __init__(self, graph):
self.graph = graph
def search(self, start, end):
openset = set()
closedset = set()
current = start
openset.add(current)
while openset:
print current
current = min(openset, key=lambda o:o.g + o.h)
if current == end:
path = []
while current.parent:
path.append(current)
current = current.parent
path.append(current)
return path[::-1]
openset.remove(current)
closedset.add(current)
for node in self.graph[current]:
if node in closedset:
continue
if node in openset:
new_g = current.g + current.move_cost(node)
if node.g > new_g:
node.g = new_g
node.parent = current
else:
node.g = current.g + current.move_cost(node)
node.h = self.heuristic(node, start, end)
node.parent = current
openset.add(node)
return None
The graph passed to it is generated at the start of the program:
def make_graph(self, size, impassable):
nodes = [[astar_gridnode(x, y) for y in range(size)] for x in range(size)]
graph = {}
for x, y in product(range(size), range(size)):
node = nodes[x][y]
graph[node] = []
for i, j in product([-1, 0, 1], [-1, 0, 1]):
# Check that we are inside the grid area.
if not (0 <= x + i < size): continue
if not (0 <= y + j < size): continue
# Check if the target area is impassable.
if (x + i, y + j) in impassable: continue
# All looks good. Add target space as reachable from current (x, y) space.
graph[nodes[x][y]].append(nodes[x+i][y+j])
return graph, nodes
And here is how the search is called:
def find_path(self, agent, target_coords, impassable, graph, nodes):
paths = astar_grid(graph)
start = nodes[agent.grid_pos[0]][agent.grid_pos[1]]
end = nodes[target_coords[0]][target_coords[1]]
path = paths.search(start, end)
This all works like it's supposed to the first time a search is done, and it works if a search is done with start, end variables and a path which doesn't intersect the previous path. It also works if a new graph is generated before each search, but that's not possible because the graph object is huge and causes the program to freeze for a couple seconds when it's being created.
If a search is made which intersects with a previous path the program freezes for a minute, and I get this error:
File "C:\...\pathfinding.py", line 16, in find_path
path = paths.search(start, end)
File "C:\...\astar.py", line 19, in search
current = current.parent
MemoryError
What is the reason for the crash and how can we fix it? I don't understand why it would crash, as it seems to me that the original graph is not modified in a search, and that a new search object is created each time a search is called, which leaves me mystified as to why it works when it works, and crashes when it does.
I agree with hughdbrown — you very likely have a cycle in the parent chain, and printing out current immediately before you assign current = current.parent is likely to tell you whether this is true.
You say that the original graph is not modified in a search, but it is. You are modifying the .parent pointer. At first, all the .parent pointers are set to None, but after you've run the search, some of them are non-None. Since it should be None and it isn't, the while current.parent: condition is failing to find the end of the path, and it's branching off into previously computed paths.
Try setting start.parent = None at the beginning of the search. Or clear the parent pointers after the search finishes (more expensive but cleaner) (you only have to clear them for things in openset and closedset).