A* for non grid network

Question

For my specific case, I am trying to find a path finding implementation similar to what described here.

I could see reference implementation for A* and HPA*, but I wonder how to extend A* to simple roadmaps (say 20 nodes). I am not sure how to extend A* to use non-grid network. Any examples would be useful.

Thanks.

Answer 1

A* doesn't really care about the shape of the graph you're using.

Let's see the pseudocode for A*, stolen from Wikipedia:

function A*(start,goal)
    closedset := the empty set    // The set of nodes already evaluated.
    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    came_from := the empty map    // The map of navigated nodes.

    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while openset is not empty
        current := the node in openset having the lowest f_score[] value
        if current = goal
            return reconstruct_path(came_from, goal)

        remove current from openset
        add current to closedset
        for each neighbor in neighbor_nodes(current)
            if neighbor in closedset
                continue
            tentative_g_score := g_score[current] + dist_between(current,neighbor)

            if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g_score
                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                if neighbor not in openset
                    add neighbor to openset

    return failure

function reconstruct_path(came_from, current_node)
    if came_from[current_node] in set
        p := reconstruct_path(came_from, came_from[current_node])
        return (p + current_node)
    else
        return current_node

There's nothing in there that specifies that the graph has to have a grid shape. However, there are two points of interest that you have to take into consideration when implementing A*.

The first one is neighbor_nodes(). For a grid shaped graph, the neighbor nodes of a given node are the ones above, below, left and right (and maybe diagonals) of it. For a freeform graph, you have to provide your own implementation of neighbor_nodes(), but I don't think that's too much of a problem.

The second point of interest is heuristic_cost_estimate(). A* relies on you being able to provide an estimation of the distance between an arbitrary node and the goal. For a grid graph, there are many heuristics, but euclidean distance and Manhattan distance are quite commonly used.

However, for an arbitrary shaped graph, you are going to have to provide your own heuristic. For abstract graphs, this may be a little bit difficult, but since your representation also seems to be somewhat geographical, you may be able to get away by using euclidean or Manhattan distance as if you were on a grid.

The advantage of the heuristic is that you can try out several different functions and see which one works the best for you.

Never forget though, that if your graphs are static (they don't change during runtime), you can have optimal solutions by precalculating distances for the entire graph using Dijkstra's or Floyd's algorithm.