Why is my A* implementation slower than floodfill?

Question

I have a blank grid of 100, 100 tiles. Start point is (0,0), goal is (99,99). Tiles are 4-way connections.

My floodfill algorithm finds the shortest path in 30ms, but my A* implementation is around 10x slower.

Note: A* is consistently slower (3 - 10x) than my floodfill, no matter what kind of size of grid or layout. Because the floodfill is simple, then I suspect I'm missing some kind of optimisation in the A*.

Here's the function. I use Python's heapq to maintain a f-sorted list. The 'graph' holds all nodes, goals, neighbours and g/f values.

import heapq

def solve_astar(graph):

    open_q = []

    heapq.heappush(open_q, (0, graph.start_point))

    while open_q:

        current = heapq.heappop(open_q)[1]

        current.seen = True # Equivalent of being in a closed queue

        for n in current.neighbours:
            if n is graph.end_point:
                n.parent = current
                open_q = [] # Clearing the queue stops the process

            # Ignore if previously seen (ie, in the closed queue)
            if n.seen:
                continue

            # Ignore If n already has a parent and the parent is closer
            if n.parent and n.parent.g <= current.g:
                continue

            # Set the parent, or switch parents if it already has one
            if not n.parent:
                n.parent = current
            elif n.parent.g > current.g:
                remove_from_heap(n, n.f, open_q)
                n.parent = current

            # Set the F score (simple, uses Manhattan)
            set_f(n, n.parent, graph.end_point)

            # Push it to queue, prioritised by F score
            heapq.heappush(open_q, (n.f, n))

def set_f(point, parent, goal):
    point.g += parent.g
    h = get_manhattan(point, goal)
    point.f = point.g + h

Can you show us `remove_from_heap`? That might be your bottleneck. — templatetypedef, Jan 20 '14 at 01:21
@templatetypedef It's `heap.remove((f_value, tile))` - but even when there are no removals, it doesn't run noticeably faster. — cyrus, Jan 20 '14 at 02:21
The heap remove operation runs in linear time, which could completely eat up all the efficiency gains you'd get from an intelligent A* search. Are you sure that this isn't your problem? — templatetypedef, Jan 20 '14 at 02:22
@templatetypedef Yes, it is still ~10x slower, even when that function is never called. — cyrus, Jan 20 '14 at 02:27
What is your `set_f` function? Perhaps you have a bad heuristic? — templatetypedef, Jan 20 '14 at 02:28
Did you try using using [cProfile](http://docs.python.org/3/library/profile.html)? `python -m cProfile myscript.py` This will at least tell you where your program is spending all its time. — mojo, Jan 20 '14 at 02:46
@mojo Wow, that's very helpful. It looks like it's examining every node - not sure why it would do that. I assume it's the heuristic, but not sure why - it's just a simple Manhattan distance? — cyrus, Jan 20 '14 at 02:55

cyrus · Accepted Answer · 2014-01-20T21:24:48.843

It's a tie-breaker issue. On an empty grid, starting at (0,0) and going to (99,99) produces many tiles with the same f-score.

By adding a tiny nudge to the heuristic, tiles that are slightly closer to the destination will get selected first, meaning the goal is reached quicker and fewer tiles need to be checked.

def set_f(point, parent, goal):
    point.g += parent.g
    h = get_manhattan(point, goal) * 1.001
    point.f = point.g + h

This resulted in around a 100x improvement, making it much faster than floodfill.

Why is my A* implementation slower than floodfill?

1 Answers1