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

Answer 1

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.