# A* for non grid network

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.

-

## 1 Answer

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.

-
You forgot to mention the most important part of the heuristic: It must never overestimate the distance between two points. – BlueRaja - Danny Pflughoeft Feb 24 '13 at 22:00
thanks everyone. I am trying to put it in code. The challenge may be correctly capturing the graph (directivity, weight etc) than just x and y for grids. Will accept shortly if no more suggestion. thanks again. – bsr Feb 25 '13 at 1:23
@BlueRaja-DannyPflughoeft I'd change "must" for "should". It's said right there in the link you provided: "With a non-admissible heuristic, the A* algorithm could overlook the optimal solution to a search problem". In other words, it will still "work", it just may overlook the best solution. However, with non-grid graphs, providing an admissible heuristic is not always trivial, or even possible. That is why if you need perfect solutions, you should use entire traversal algorithms, such as Dijkstra or Floyd. – Panda Pajama Feb 25 '13 at 1:34
@Panda: I define an algorithm as "working" if it produces the correct result, not just any result. – BlueRaja - Danny Pflughoeft Feb 25 '13 at 3:15
@BlueRaja-DannyPflughoeft when you choose to use an heuristic algorithm, you are trading completeness, accuracy and/or precision for speed. Using a non-admissible heuristic will not give you an incorrect result (a path that doesn't lead to the goal), it may just not be the shortest path. If you need the actual shortest path, there are other (slower) algorithms to suit your needs like Dijkstra or Floyd. – Panda Pajama Feb 25 '13 at 4:06