FacebookTwitterDiggDeliciousStumbleuponGoogle BookmarksRedditLinkedin

Up

A* Pathfinding Algorithm Example

A* Pathfinding Algorithm Example
File Size:
76.74 kB
Version:
0.1
Date:
16 May 2014
Downloads:
13 x

Algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes.

Notes
 
A* Algorithm Pseudocode
 
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 current_node in came_from
        p := reconstruct_path(came_from, came_from[current_node])
        return (p + current_node)
    else
        return current_node

 

Rating: 0 / 0 vote  
Only registered and logged in users can rate this file
 
 
 
 

Freedom Code

All existing content on this site can be used and modified to pleasure the developer who implements it. 

There are full and complete freedom to use the code. Developers can collaborate on this projects or recommend changes for improve it.

Contact