Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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