1

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.

1
  • Try writing out the nodes in your loop that traverses up the parents to the start. Maybe you have an infinite loop because your parentage is not constructed correctly.
    – hughdbrown
    Apr 15, 2013 at 3:01

1 Answer 1

1

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).

2
  • Also, if you're running into performance issues, consider using a different implementation of a priority queue, such as a binary heap (Python's heapq module might be of use here). Amitp's site has a discussion of data structures to implement your priority queue here theory.stanford.edu/~amitp/GameProgramming/…
    – IceArdor
    Nov 22, 2013 at 15:39
  • Other possible performance improvements that I'll add to the site eventually: Fringe search and ALT bidirectional search.
    – amitp
    Nov 22, 2013 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.